Το θεώρημα της κάλπης

Πλησιάζουν εκλογές στην Ελλάδα. Ας ασχοληθούμε λοιπόν με ένα σχετικό μαθηματικό θεώρημα. Σε μια εκλογική διαδικασία υπάρχουν δύο υποψήφιοι και n ψηφοφόροι. Έστω ότι ο υποψήφιος A έλαβε a ψήφους και ο υποψήφιος B έλαβε b ψήφους, όπου a > b. Ποια είναι η πιθανότητα ο υποψήφιος A να προηγείτο καθ’ όλη την διάρκεια της εκλογικής διαδικασίας; Το θεώρημα της κάλπης μας λέει ότι η πιθανότητα ισούται με \displaystyle \frac{a-b}{n}. Θα δώσω δυο αποδείξεις του θεωρήματος. Προτού όμως δώσω τις αποδείξεις ας δούμε ένα παράδειγμα για να σιγουρευτούμε ότι καταλάβαμε τι λέει το θεώρημα.

Παράδειγμα: Πέντε ψηφοφόροι, με τον A να λαμβάνει τρεις ψήφους και τον B δύο. Το θεώρημα λέει ότι η πιθανότητα ο Α να προηγείτο καθ’ όλη την διάρκεια της εκλογικής διαδικασίας είναι \displaystyle \frac{3-2}{5} = \frac{1}{5}. Ας δούμε με ποιους διαφορετικούς τρόπους θα μπορούσαν να καταμετρηθούν τα ψηφοδέλτια. Έχουμε τρία ψηφοδέλτια που γράφουν A και δύο που γράφουν B. Θα μπορούσε η καταμέτρηση να δείξει AAABB, δηλαδή τα πρώτα τρία ψηφοδέλτια έδειξαν A και τα επόμενα δύο έδειξαν B. Ποια είναι η πιθανότητα να έχει συμβεί αυτό; Αφού έχουμε πέντε ψηφοδέλτια, μπορούμε να τα καταμετρήσουμε με 5! = 120 διαφορετικούς τρόπους. (Πέντε τρόπους για να διαλέξουμε πιο ψηφοδέλτιο θα μετρήσουμε πρώτο, τέσσερις τρόπους για να διαλέξουμε το δεύτερο κ.τ.λ.) Η καταμέτρηση AAABB εμφανίζεται με 3! \cdot 2! = 12 τρόπους. Άρα η ζητούμενη πιθανότητα είναι όντως 12/120 = 1/10. Ομοίως βρίσκουμε ότι κάθε μία από τις καταμετρήσεις AAABB, AABAB, ABAAB, AABBA, ABAAB, ABABA, ABBAA, BAAAB, BAABA, BABAA, BBAAA έχει πιθανότητα 1/10. Αλλά μόνο στις καταμετρήσεις AAABB και AABAB προηγείτο ο A. (Π.χ. στην καταμέτρηση BAAAB προηγείται αρχικά ο B, ενώ στην καταμέτρηση ABAAB αν και δεν προηγείται ποτέ ο B, έχουμε σε κάποια φάση ισοπαλία.) Άρα η πιθανότητα να προηγείται συνέχεια ο A είναι όντως 2/10=1/5.

Ας δώσουμε τώρα την πρώτη απόδειξη.

Απόδειξη 1: Μπορούμε να σκεφτούμε την όλη καταμέτρηση σαν μια ακολουθία σημείων (0,0),(1,y_1),(2,y_2),\ldots,(n,y_n) στο επίπεδο όπου το y_n δηλώνει με πόσους ψήφους διαφορά προηγείται ο A του B. Για παράδειγμα η καταμέτρηση AABAB αντιστοιχεί στην ακολουθία (0,0),(1,1),(2,2),(3,1),(4,2),(5,1) και στην ακόλουθη γραφική παράσταση, όπου συνδέσαμε τα γειτονικά σημεία μεταξύ τους με ευθείες γραμμές.

Ballot1

Κάθε καταμέτρηση αντιστοιχεί και σε μοναδικό γράφημα. Ας ονομάσουμε μια καταμέτρηση «καλή», αν κατά την διάρκεια της καταμέτρησης προηγείτο ο A, αλλιώς ας την ονομάσουμε «κακή». Αν κάποιος μας δείξει την γραφική παράσταση, μπορούμε να καταλάβουμε αν η καταμέτρηση είναι καλή η κακή; Βεβαίως. Η καταμέτρηση θα είναι καλή αν και μόνο αν η γραφική παράσταση είναι πάντα πάνω από τον άξονα των χ (και αγγίζει τον άξονα μόνο στο (0,0)). Ας κοιτάξουμε μια καταμέτρηση η οποία αρχίζει με ψήφο υπέρ του A. Αν η καταμέτρηση είναι κακή, τότε η γραφική παράσταση θα αγγίξει τουλάχιστον μία φορά (ίσως και περισσότερες) τον άξονα των χ. Έστω ότι η αυτό συμβαίνει για πρώτη φορά στην ψήφο k. Τότε κάνουμε την εξής μετατροπή στην γραφική παράσταση: Ανακλούμε το κομμάτι της γραφικής παράστασης από το 0 ως το k στον άξονά των χ. Για παράδειγμα:

Ballot2

Η κακή λοιπόν καταμέτρηση ABAAB αντιστοιχεί, μετά από την ανάκλαση, στην κακή καταμέτρηση BAAAB. Βλέπουμε ότι υπάρχει μια αντιστοίχιση μεταξύ των κακών καταμετρήσεων που ξεκινάνε με ψήφο υπέρ του A και των κακών καταμετρήσεων που ξεκινάνε με ψήφο υπέρ του B. Με άλλα λόγια, ο αριθμός των κακών καταμετρήσεων που ξεκινάνε με ψήφο υπέρ του A ισούται με τον αριθμό των κακών καταμετρήσεων που ξεκινάνε με ψήφο υπέρ του B. Εμείς θέλουμε να υπολογίσουμε τον αριθμό των καλών καταμετρήσεων. Έστω ότι ο συνολικός αριθμός των καταμετρήσεων ισούται με x. (Ισχύει ότι \displaystyle x = \frac{n!}{a!b!} αλλά δεν θα το χρησιμοποιήσουμε.) Εφ’ όσων ο A πήρε a ψήφους, ακριβώς ax/n καταμετρήσεις ξεκινούν με ψήφο υπέρ του A. (Οι υπόλοιπες bx/n ξεκινούν με ψήφο υπέρ του B.) Υπάρχουν όμως κάποιες καταμετρήσεις που ξεκινούν με ψήφο υπέρ του A αλλά είναι κακές. Πόσες; Ακριβώς όσες και οι κακές που ξεκινάνε με ψήφο υπέρ του B οι οποίες είναι bx/n. Άρα μένουν ακριβώς (a-b)x/n καλές καταμετρήσεις. Άρα η πιθανότητα η καταμέτρηση να είναι καλή είναι όντως \displaystyle  \frac{(a-b)}{n}. \square

Μπορεί να μακρυγόρησα κάπως στην πιο πάνω λύση (με την ελπίδα να την κάνω περισσότερο κατανοητή) αλλά η βασική ιδέα είναι μία: Η χρησιμοποίηση του ανακλαστικού κόλπου.

Ας δούμε τώρα και την δεύτερη απόδειξη.

Απόδειξη 2: Όπως και στην προηγούμενη απόδειξη, λέμε ότι μια καταμέτρηση είναι καλή αν προηγείται συνέχεια ο A. Η βασική παρατήρηση είναι ότι αν γράψουμε M(n,a) για τον αριθμό των καλών καταμετρήσεων, τότε ισχύει ότι

M(n+1,a+1) = M(n,a) + M(n,a+1).

Πράγματι, για κάθε καλή καταμέτρηση με n+1 ψηφοφόρους, και a+1 ψήφους για τον A, αν αγνοήσουμε την τελευταία ψήφο παίρνουμε μια καλή καταμέτρηση με n ψηφοφόρους και a ή a+1 ψήφους για τον A (ανάλογα με το αν η τελευταία ψήφος ήταν του A ή όχι). Επίσης σε αυτήν την αντιστοίχιση κάθε καλή καταμέτρηση με n ψηφοφόρους και a ψήφους για τον A εμφανίζεται ακριβώς μία φορά και το ίδιο ισχύει για κάθε καλή καταμέτρηση με n ψηφοφόρους και a+1 ψήφους για τον A.

Ισχυριζόμαστε τώρα ότι \displaystyle M(n,a) = \frac{(2a-n)(n-1)!}{a!(n-a)!}. Η απόδειξη του ισχυρισμού είναι με επαγωγή στο n και την αφήνουμε στον αναγνώστη.

Επειδή ο συνολικός αριθμός των καταμετρήσεων είναι \displaystyle \frac{n!}{a!(n-a)!}, η ζητούμενη πιθανότητα είναι όντως \displaystyle \left(\frac{(2a-n)(n-1)!}{a!(n-a)!}\right) / \left(\frac{n!}{a!(n-a)!}\right) = \frac{2a-n}{n} = \frac{a-b}{n}. \square

Advertisements

About Δημήτρης Χριστοφίδης

Course Leader in Mathematics at UCLan Cyprus.
This entry was posted in 05A15 - Exact enumeration problems, generating functions, 91B12 - Voting theory. Bookmark the permalink.

Σχολιάστε

Εισάγετε τα παρακάτω στοιχεία ή επιλέξτε ένα εικονίδιο για να συνδεθείτε:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s