Το τριώροφο χωνάκι και το κόλπο του Von Neumann

17.07.2017
Το τριώροφο χωνάκι και το κόλπο του Von Neumann

Τα παγωτατζίδικα της εταιρείας Baskin-Robbins διαφημίζουν τριάντα ένα διαφορετικά είδη παγωτού. Ο αριθμός των διατάξεων που μπορούν να γίνουν χωρίς επανάληψη κάποιου είδους σ’ ένα χωνάκι με τρεις μπάλες είναι επομένως 31 X 30 X 29 = 26.970· οποιοδήποτε από τα τριάντα ένα είδη μπορεί να μπει από πάνω, οποιοδήποτε από τα υπόλοιπα τριάντα στη μέση και οποιοδήποτε από τα υπόλοιπα είκοσι εννέα από κάτω.

Αν δεν μας ενδιαφέρει με ποια σειρά μπαίνουν οι μπάλες στο χωνάκι αλλά μόνο πόσα τριώροφα χωνάκια υπάρχουν, διαιρούμε το 26.970 με το 6 και έχουμε 4.495 χωνάκια. Ο λόγος που διαιρούμε με το 6 είναι ότι υπάρχουν 6 = 3 x 2 x 1 διαφορετικοί τρόποι να βάλουμε τις τρεις μπάλες, π.χ. σ’ ένα χωνάκι με παγωτό φράουλα, κρέμα και σοκολάτα: ΦΚΣ, ΦΣΚ, ΚΦΣ, ΚΣΦ, ΣΚΦ και ΣΦΚ. Αφού μπορούμε να πούμε το ίδιο για οποιοδήποτε τριπλό χωνάκι, ο συνολικός αριθμός τους είναι (31 x 30 x 29)/(3 x 2 x 1) = 4.495.

Ένα λιγότερο παχυντικό παράδειγμα δίνουν πολλές δημόσιες λοταρίες που απαιτούν από το νικητή να διαλέξει έξι από 40 πιθανούς αριθμούς. Αν μας ενδιαφέρει η σειρά με την οποία επιλέγονται αυτοί οι έξι αριθμοί, τότε υπάρχουν (40 X 39 X 38 X 37 X 36 X 35) = 2.763.633.600 τρόποι επιλογής. Αν όμως μας ενδιαφέρουν μόνο οι έξι αριθμοί ως σύνολο (όπως συμβαίνει στην περίπτωση της λοταρίας) και όχι η σειρά με την οποία επιλέγονται, τότε διαιρούμε το 2.763.633.600 με το 720 για να καθορίσουμε τον αριθμό τέτοιων συνόλων, που είναι: 3.838.380. Η διαίρεση είναι απαραίτητη αφού υπάρχουν 720 = 6 x 5 x 4 x 3 x 2xl τρόποι να βάλουμε τους έξι αριθμούς σε οποιοδήποτε σύνολο.

Ένα άλλο παράδειγμα, αρκετά σημαντικό για τους χαρτοπαίχτες, είναι ο αριθμός των συνδυασμών από πέντε φύλλα που μπορεί να πάρει στο χέρι ένας παίκτης σε μια μοιρασιά πόκερ. Υπάρχουν 52 x 51 x 50 x 49 x 48 δυνατοί τρόποι να πάρει κανείς πέντε φύλλα αν η σειρά των φύλλων που μοιράζονται έχει σημασία. Αφού όμως δεν έχει, διαιρούμε το γινόμενο με το (5 x 4 x 3 x 2 x 1) και βρίσκουμε ότι υπάρχουν 2.598.960 δυνατές μοιρασιές. Όταν γνωρίζει κανείς αυτό τον αριθμό, μπορεί να υπολογίσει διάφορες χρήσιμες πιθανότητες. Οι πιθανότητες να του έρθουν τέσσερις άσσοι, για παράδειγμα, είναι 48/2.598.960 ( = περίπου 1 στις 50.000), αφού υπάρχουν σαράντα οχτώ δυνατοί τρόποι να γίνει μια μοιρασιά με τέσσερις άσσους, που αντιστοιχούν στα σαράντα οχτώ χαρτιά που θα μπορούσαν να είναι το πέμπτο φύλλο σε μια τέτοια μοιρασιά.

Σημειώστε ότι η μορφή του αριθμού που βγαίνει είναι ίδια και στα τρία παραδείγματα: (31 x 30 x 29)/(3 x 2 x 1) διαφορετικά τριπλά χωνάκια· (40 x 39 x 38 x 37 x 36 x 35)/(6 x5x4x3x2x 1) διαφορετικοί τρόποι επιλογής έξι αριθμών από σαράντα- και (52 x 51 x 50 x 49 x 48) /(5 x 4 x 3 x 2 x 1) διαφορετικές μοιρασιές στο πόκερ. Οι αριθμοί που βρίσκονται με αυτό τον τρόπο ονομάζονται συνδυασμικοί συντελεστές. Αυτοί προκύπτουν όταν μας ενδιαφέρει ο αριθμός των τρόπων επιλογής Ρ στοιχείων από Ν στοιχεία και δεν μας ενδιαφέρει η σειρά των επιλεγμένων Ρ στοιχείων.

Κάτι ανάλογο με την αρχή του πολλαπλασιασμού μπορεί να χρησιμοποιηθεί για τον υπολογισμό πιθανοτήτων. Αν δύο συμβάντα είναι ανεξάρτητα, με την έννοια ότι η έκβαση του ενός δεν έχει καμία επίδραση στην έκβαση του άλλου, τότε η πιθανότητα να συμβούν και τα δύο, υπολογίζεται πολλαπλασιάζοντας τις πιθανότητες των ξεχωριστών συμβάντων.

Για παράδειγμα, η πιθανότητα να πετύχει κανείς δύο φορές κορώνα στρίβοντας δύο φορές ένα νόμισμα είναι 1/2 X 1/2 = 1/4, αφού από τις τέσσερις ίσες πιθανότητες -γράμματα-γράμματα, γράμματα-κορώνα, κορώνα-γράμματα, κορώνα-κορώνα- η μία είναι να πετύχει ένα ζευγάρι κορώνες. Για τον ίδιο λόγο, η πιθανότητα να πετύχει κανείς κορώνα πέντε φορές στη σειρά είναι (1/2)5 = 1/32, αφού μία από τις τριάντα δύο ίσες πιθανότητες είναι να έρθουν πέντε διαδοχικές κορώνες.

Αφού η πιθανότητα να σταματήσει μια ρουλέτα στο κόκκινο είναι 18/38 και αφού οι περιστροφές μιας ρουλέτας είναι ανεξάρτητες μεταξύ τους, η πιθανότητα να σταματήσει στο κόκκινο σε πέντε διαδοχικές περιστροφές είναι (18/38)5 (ή 0,024-2,4%). Με τον ίδιο τρόπο, δεδομένου ότι η πιθανότητα ένα τυχαία επιλεγμένο άτομο να μην έχει γεννηθεί τον Ιούλιο είναι 11/12 και δεδομένου ότι τα γενέθλια των ανθρώπων είναι ανεξάρτητα μεταξύ τους, η πιθανότητα μεταξύ δώδεκα τυχαία επιλεγμένων ατόμων κανένα να μην έχει γεννηθεί τον Ιούλιο είναι (11/12)'2 (ή 0,352-35,2%). Η ανεξαρτησία των συμβάντων είναι μια πολύ σημαντική έννοια στις πιθανότητες, και όταν ισχύει, η αρχή του πολλαπλασιασμού απλουστεύει σημαντικά τους υπολογισμούς μας.

Ένα από τα πιο παλιά προβλήματα των πιθανοτήτων είχε υποδειχθεί στο Γάλλο μαθηματικό και φιλόσοφο Pascal από τον παίκτη Antoine Gombaud, Σεβαλιέ ντε Μερέ. O de Mere ήθελε να μάθει τι ήταν πιθανότερο: να φέρει τουλάχιστον μια φορά έξι ρίχνοντας τέσσερις φορές ένα μοναδικό ζάρι ή να φέρει τουλάχιστον μια φορά εξάρες ρίχνοντας είκοσι τέσσερις φορές δύο ζάρια. Η αρχή του πολλαπλασιασμού εφαρμοσμένη στις πιθανότητες είναι αρκετή για να προσδιορίσουμε την απάντηση αν θυμηθούμε ότι η πιθανότητα να μη συμβεί κάτι είναι ίση με 1 μείον την πιθανότητα να συμβεί (20% πιθανότητα βροχής σημαίνει 80% πιθανότητα να μη βρέξει).

Αφού 5/6 είναι η πιθανότητα να μη φέρει κανείς έξι ρίχνοντας ένα ζάρι μία φορά, (5/6)4 είναι η πιθανότητα να μη φέρει έξι ρίχνοντας το ζάρι τέσσερις φορές. Επομένως, αν αφαιρέσουμε αυτό τον αριθμό από το 1, βρίσκουμε τι πιθανότητα υπάρχει να μην προκύφει αυτή η τελευταία περίπτωση (κανένα έξι)· μ’ άλλα λόγια, η πιθανότητα να έρθει τουλάχιστον μία φορά έξι στις τέσσερις προσπάθειες είναι 1—(5/6)4 = 0,52. Με τον ίδιο τρόπο, η πιθανότητα να φέρει κανείς τουλάχιστον μία φορά εξάρες ρίχνοντας είκοσι τέσσερις φορές δύο ζάρια υπολογίζεται ότι είναι 1-(35/36)24 = 0,49.

Ένα πιο σύγχρονο παράδειγμα αυτού του είδους υπολογισμών αφορά την πιθανότητα να προσβληθεί κανείς από AIDS έχοντας ετεροφυλόφιλες σεξουαλικές σχέσεις. Εκτιμάται ότι η πιθανότητα προσβολής από AIDS, σε μία μοναδική ετεροφυλόφιλη σεξουαλική επαφή χωρίς προφυλακτικά μέτρα, από ένα σύντροφο που είναι γνωστό ότι έχει την ασθένεια, είναι περίπου μία στις πεντακόσιες (μέσος όρος των αριθμών από μια σειρά ερευνών). Επομένως η πιθανότητα να μην προσβληθεί κανένας από μια τέτοια μοναδική επαφή είναι 499/500. Αν ο κίνδυνος προσβολής είναι κάθε φορά ανεξάρτητος, όπως πολλοί υποθέτουν, τότε οι πιθανότητες να μην πέσει κανένας θύμα μετά από δύο τέτοιες επαφές είναι (499/500)2, και μετά από Ν τέτοιες επαφές (499/500)Ν. Αφού (499/500)346 είναι 1/2, έχει κανείς περίπου 50% πιθανότητα να μην προσβληθεί από AIDS έχοντας ετεροφυλόφιλη σεξουαλική επαφή χωρίς προφυλάξεις κάθε μέρα επί ένα χρόνο με κάποιον που έχει την ασθένεια (κι επομένως την ίδια 50% να προσβληθεί).

Με ένα προφυλακτικό, η πιθανότητα να κολλήσει κανείς από μία μόνο ετεροφυλόφιλη επαφή με κάποιον που είναι γνωστό ότι έχει την ασθένεια πέφτει σε μία στις πέντε χιλιάδες, ενώ καθημερινό σεξ με προφυλάξεις επί δέκα χρόνια μ’ έναν τέτοιο σύντροφο (υποθέτοντας ότι το θύμα θα επιβιώσει) θα οδηγούσε σε 50% πιθανότητα να κολλήσετε ο ίδιος την ασθένεια. Αν η κατάσταση του συντρόφου σας σχετικά με την ασθένεια δεν είναι γνωστή, αλλά αυτός ή αυτή δεν ανήκει σε καμιά γνωστή ομάδα υψηλού κινδύνου, η πιθανότητα να κολλήσετε την ασθένεια είναι μία στα πέντε εκατομμύρια σε κάθε επαφή χωρίς προφυλάξεις και μία στα πενήντα εκατομμύρια σε κάθε επαφή με προφυλαχτικό. Είναι πιθανότερο να πεθάνετε σε αυτο-κινητικό δυστύχημα γυρίζοντας σπίτι σας μετά από μια τέτοια συνάντηση.

Δυο αντιτιθέμενες πλευρές συχνά εναποθέτουν την απόφαση για κάποιο ζήτημα στο στρίψιμο ενός νομίσματος. Η μία ή και οι δύο πλευρές μπορεί να υποψιάζονται ότι το νόμισμα είναι «φτιαγμένο». Ένα χαριτωμένο κολπάκι βασισμένο στην αρχή του πολλαπλασιασμού επινοήθηκε από τον μαθηματικό John von Neumann, για να επιτρέψει στους αντιπάλους, ενώ χρησιμοποιούν το φτιαγμένο νόμισμα, να βγάλουν δίκαια αποτελέσματα.

Το νόμισμα στρίβεται δυο φορές. Αν έρθει κορώνα και τις δύο φορές ή γράμματα και τις δύο φορές, ξαναστρίβεται άλλες δυο φορές. Αν έρθει κορώνα-γράμματα, αυτό θα κρίνει το αποτέλεσμα υπέρ της πρώτης πλευράς, και αν έρθει γράμματα-κορώνα, αυτό θα κρίνει το αποτέλεσμα υπέρ της δεύτερης πλευράς. Οι πιθανότητες των δύο αυτών αποτελεσμάτων είναι ίσες, ακόμη κι αν το νόμισμα είναι φτιαγμένο. Για παράδειγμα, αν ένα νόμισμα έρχεται κορώνα κατά 60% και γράμματα κατά 40%, μία ακολουθία κορώνα-γράμματα έχει πιθανότητα 0,6 x 0,4 = 0,24 και μία ακολουθία γράμματα-κορώνα έχει πιθανότητα 0,4 X 0,6 = 0,24. Έτσι, και οι δύο πλευρές μπορεί να είναι σίγουρες για το δίκαιο του αποτελέσματος, παρά το ενδεχόμενο να είναι το νόμισμα φτιαγμένο (εκτός αν είναι στημένο με κάποιον άλλο τρόπο).

Ένα βασικό δεδομένο που συνδέεται στενά με την αρχή του πολλαπλασιασμού και τους συνδυασμικούς συντελεστές είναι η διωνυμική κατανομή πιθανοτήτων. Αυτή προκύπτει όταν μια διαδικασία ή μια δοκιμή μπορεί να καταλήξει σε «επιτυχία» ή «αποτυχία» και κάποιος ενδιαφέρεται για την πιθανότητα να έχει Ρ επιτυχίες σε Ν δοκιμές. Αν 20% των αναψυκτικών που δίνει ένα αυτόματο μηχάνημα ξεχειλίζουν από τα κύπελλά τους, τι πιθανότητα υπάρχει να ξεχειλίσουν ακριβώς τρία από τα επόμενα δέκα; ή το πολύ τρία; Αν μια οικογένεια έχει πέντε παιδιά, τι πιθανότητα υπάρχει να έχει ακριβώς τρία κορίτσια; ή τουλάχιστον τρία; Αν το ένα δέκατο όλων των ανθρώπων έχουν μια ορισμένη ομάδα αίματος, τι πιθανότητα υπάρχει, από τους επόμενους εκατό ανθρώπους που θα επιλέγουμε τυχαία, ακριβώς οκτώ να έχουν αυτή την ομάδα αίματος; ή το πολύ οκτώ;

Ας βρούμε την απάντηση στις ερωτήσεις σχετικά με το αυτόματο μηχάνημα, του οποίου 20% των αναψυκτικών ξεχειλίζουν από τα κύπελλά τους. Η πιθανότητα τα πρώτα τρία αναψυκτικά να ξεχειλίζουν και τα επόμενα εφτά να μην ξεχειλίζουν είναι, σύμφωνα με την αρχή του πολλαπλασιασμού στις πιθανότητες, (0,2)3 x (0,8)7. Αλλά υπάρχουν πολλοί διαφορετικοί τρόποι να ξεχειλίσουν ακριβώς τρία από τα δέκα κύπελλα και καθένας έχει πιθανότητα (0,2)3 X (0,8)7. Μπορεί να ξεχειλίσουν μόνο τα τρία τελευταία κύπελλα, ή μόνο το τέταρτο, το πέμπτο και το ένατο κύπελλο και ούτω καθεξής. Έτσι, αφού υπάρχουν συνολικά (10 X 9 X 8)/(3 X 2 X 1) = 120 τρόποι με τους οποίους μπορούμε να επιλέξουμε τρία από τα δέκα κύπελλα (συνδυασμικός συντελεστής), η πιθανότητα να ξεχειλίσει κάποιο σύνολο ακριβώς τριών κυπέλλων, είναι 120 x (0,2)3 X (0,8)7.

Η πιθανότητα να ξεχειλίσουν το πολύ τρία κύπελλα προσδιορίζεται βρίσκοντας την πιθανότητα να ξεχειλίσουν ακριβώς τρία κύπελλα, πράγμα που έχουμε ήδη κάνει, και προσθέτοντας σ’ αυτήν τις πιθανότητες να ξεχειλίσουν ακριβώς δύο, ένα και μηδέν κύπελλα, οι οποίες μπορούν να προσδιοριστούν με παρόμοιο τρόπο. Ευτυχώς, υπάρχουν πίνακες και καλές προσεγγίσεις που μπορούν να χρησιμοποιηθούν για τη συντόμευση αυτών των υπολογισμών. 

***

Από το βιβλίο "ΑΡΙΘΜΟΦΟΒΙΑ" του John Allen Paulos