Tο παιχνίδι του Googol,η επιλογή της βέλτιστης γραμματέως και τα βάσανα μιας πριγκίπισσας

P.Halmos

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

                                            P.Halmos,The college mathematics Journal,Vol 35,No1,2004                                                                                          

  Απο κουβέντα πιάστηκα ως συνήθως, σε κάποιο τμήμα  για το παιχνίδι του googol και επειδή δεν μπορώ να τα πω στο μάθημα,το γράφω.      

    "Στην μακρινή χώρα της Λοξολάνδης η πριγκίπισσα Χόνη πρόκειται να παντρευτεί και πρέπει να επιλέξει έναν πρίγκιπα ανάμεσα στους 20 που της προτείνει ο πατέρας της, βασιλιάς Βασίλης.Δεν γνωρίζει τίποτα για τον καθένα τους,ο πατέρας της θυμίζει ότι το βασιλικό πρωτόκολλο έχει τους εξής κανόνες: έχει την δυνατότητα να βγαίνει ραντεβού με έναν υποψήφιο κάθε μέρα και πρέπει στο τέλος του ραντεβού να ανακοινώσει στον πάτερα της αν ο ημερήσιος υποψήφιος είναι ο ιδανικότερος,οπότε σταματά τα επόμενα ραντεβού και τελείται ο γάμος.Με την επιλογή της, να προχωρήσει στο ραντεβού της επόμενης μέρας είναι υποχρεωμένη να απορρίψει όλους τους προηγούμενους υποψηφίους .Υπάρχει βέλτιστη στρατηγική για την πριγκίπισσα Χόνη;"
 

    Μοιάζει με φάρσα αλλά είναι ένα πολύ γνωστό πρόβλημα που αναφέρει ο Μάρτιν Γκάρντνερ ως παιχνίδι του Googol  ή πρόβλημα  του γάμου ή σε μια πιο σύγχρονη εκδοχή πρόβλημα της γραμματέως. 

Μάρτιν Γκάρντνερ

    Το πρόβλημα έχει πολλαπλές αναφορές,αλλά προτιμώ αυτή του P.Halmos στο βιβλίο του Problems for mathematicians young and old (Μια άψογη  μετάφραση του βιβλίου στα ελληνικά ).

Ο Halmos αναδιατυπώνει λοιπόν το αρχικό πρόβλημα ως εξής:

   Υπάρχουν 100  χαρτάκια,σε ένα καπέλο,που καθένα έχει έναν αριθμό.Οι αριθμοί δεν χρειάζεται να είναι οι 100 πρώτοι  θετικοί ακέραιοι,ούτε καν ακέραιοι ή θετικοί.Είναι άγνωστοι πραγματικοί αριθμοί,όπως 4, 2e, 1/3,….Η μόνη υπόθεση είναι ότι οι εκατό αριθμοί είναι όλοι διαφορετικοί.Παίζουμε τώρα το εξής παιχνίδι.Τραβάει ο παίκτης ένα χαρτάκι στην τύχη  από το καπέλο,κοιτάει τον αριθμό του και το πετάει για πάντα πριν τραβήξει κάποιο επόμενο.Μπορείς να σταματήσει ανά πάσα στιγμή,μετά την πρώτη επιλογή ή οποιαδήποτε άλλη.Αν δεν έχει σταματήσει  μετά από 99  επιλογές,σταματάει αναγκαστικά στην εκατοστή.Ο παίκτης κερδίζει,αν ο αριθμός στον οποίο σταμάτησε  είναι ο μεγαλύτερος στο καπέλο – μεγαλύτερος ενδεχομένως από όσους απέρριψε  ή από όσους παραμένουν.Υπάρχει βέλτιστη στρατηγική που πρέπει να ακολουθήσει ο παίκτης,ποια είναι αυτή;

    Αν ο παίκτης υιοθετήσει τον εξής τρόπο δράσης.Τραβάει ένα αριθμό, έναν δεύτερο έναν τρίτο κ.λ.π  μέχρι τον πεντηκοστό. Κοιτάει τους αριθμούς αλλά,όποιοι και είναι δεν σταματάει.Όταν τραβήξει τον πεντηκοστό αριθμό συγκρίνει το αποτέλεσμα με τους πρώτους 50.Αν ο αριθμός είναι μεγαλύτερος από όλους τους προηγούμενους σταματάει, ειδάλλως είναι υποχρεωμένος να συνεχίσει. Αφού έτσι και αλλιώς είναι χαμένος (ένας από τους προηγούμενους είναι μεγαλύτερος). Αν ο πεντηκοστός δεύτερος  υπερβαίνει τους πρώτους 50 σταματάει,ειδάλλως συνεχίζει.Με άλλα λόγια, τραβάει έως ότου ξεπεράσει τους πρώτους 50.Αυτό φυσικά,μπορεί να μην συμβεί ποτέ, ο μεγαλύτερος αριθμός μπορεί  να είναι ένας από τους πρώτους 50 .Ακόμη  και αν αυτό  δεν αληθεύει,δεν είναι καθόλου βέβαιο  ότι η στρατηγική θα οδηγήσει σε νίκη : μπορεί ο πεντηκοστός πρώτος να ξεπεράσει  τους προηγούμενους άλλα  να μην είναι ο μεγαλύτερος (ο οποίος π.χ μπορεί να είναι ο ενενηκοστός  δεύτερος ).Σε κάθε περίπτωση, όμως, πρόκειται για συγκεκριμένη στρατηγική.Ποια είναι η πιθανότητα νίκης υιοθετώντας την;

   Ο ακριβής υπολογισμός είναι οδυνηρός,άλλα, ευτυχώς,δεν είναι απαραίτητος ( οι μισοί από σας  θα σταματούσαν το διάβασμα της ανάρτησης εδώ ) Αυτό που είναι προφανές  είναι ότι αν  ο δεύτερος  πιο μεγάλος αριθμός ανήκει  στους πρώτους 50  και αν ο  μεγαλύτερος αριθμός ανήκει τους τελευταίους πενήντα,τότε η στρατηγική οδηγεί σε βέβαιη νίκη.Υπάρχουν άλλες δυνατότητες  νίκης,άλλα η προηγούμενη είναι ξεκάθαρη.Ποια,λοιπόν είναι η πιθανότητα ο δεύτερος αριθμός να είναι στους πρώτους πενήντα και ο μεγαλύτερος στους τελευταίους πενήντα;

Προφανώς η πιθανότητα κάθε γεγονότος χωριστά είναι (1/2)(50/100)  και θα μπορούσε κάποιος να ισχυριστεί ότι η πιθανότητα να συμβούν και τα δυο είναι 1/4=(1/2)(1/2) Λανθασμένα.Η απάντηση είναι μια καλή προσέγγιση, άλλα δεν είναι η σωστή.Το πρόβλημα  είναι ότι τα δυο γεγονότα (δεύτερος στους πρώτους πενήντα, πρώτος στους τελευταίους πενήντα) δεν είναι ανεξάρτητα,ώστε να μπορούμε να πολλαπλασιάσουμε τις αντίστοιχες πιθανότητες.Η σωστή απάντηση όμως είναι εύκολη: αρκεί να υπολογίσουμε  την εξαρτώμενη πιθανότητα  για τον πρώτο αριθμό να ανήκει στους πενήντα τελευταίους, δεδομένου ότι ο δεύτερος ανήκει στους πενήντα πρώτους.Αν είναι γνωστό ότι ο δεύτερος πιο μεγάλος ανήκει  στους πενήντα πρώτους,τότε απομένουν 99 δυνατές θέσεις για τον μεγαλύτερο.Αφού οι τελευταίες είναι πενήντα,η τιμή της ζητούμενης δεσμευμένης πιθανότητας είναι 50/99 .Η πιθανότητα εγγυημένης νίκης είναι λοιπόν (1/2)(50/99)=0.2525, προφανώς μεγαλύτερη από  (1/2)(50/100)

Επομένως,με μια καλή στρατηγική,η πιθανότητα νίκης είναι  τουλάχιστον ¼.

    Η παραπάνω στρατηγική είναι στον σωστό δρόμο άλλα όχι η βέλτιστη. Η καλύτερη στρατηγική  είναι να τραβάς αριθμούς με τον τρόπο που υποδείχτηκε  άλλα όχι 100/2 φορές ,αποδεικνύεται ότι ο σωστός αριθμός είναι 100/e φορές (Η αναλυτική απόδειξη στο τέλος της ανάρτησης).Αν δηλαδή,το καπέλο δεν περιέχει  εκατό άλλα n αριθμούς,τραβήξετε n/e από αυτούς(τον πλησιέστερο ακέραιο) και μετά εξακολουθήστε να τραβάτε έως ότου υπερβείτε  τους προηγούμενους.Όσο το n μεγαλώνει,η στρατηγική βελτιώνεται  και η πιθανότητα νίκης πλησιάζει την μέγιστη δηλαδή 1/e περίπου 0.37.
                                        
                                    

Άρα επανερχόμαστε στο αρχικό ερώτημα. Η πριγκίπισσα Χονη θα πρέπει να πραγματοποιήσει το 37% των ραντεβού,ο πλησιέστερος ακέραιος είναι το 7,και να επιλέξει τον πρώτο υποψήφιο που θα θεωρήσει ότι είναι καλύτερος από όσους έχει δει μέχρι εκείνη την στιγμή.

 Bonus στην ανάρτησή μια τρίλεπτη συνέντευξη από το P.Halmos,που απηχεί τις απόψεις του για το πως γράφουμε,διδάσκουμε και εν γένει ασχολούμαστε με τα μαθηματικά.

                  

Σχετικοί σύνδεσμοι

http://www.math.uah.edu/stat/urn/Secretary.html

http://www.math.upenn.edu/~ted/210F10/References/Secretary.pdf

http://theory.stanford.edu/~sergei/slides/hiring-dagstuhl.pdf

http://rs.io/2014/03/03/the-secretary-problem.html

Σχετικά βιβλία 

-Problems for mathematicians young and old, P.Halmos 
-My Best Mathematical and Logic Puzzles , Martin Gardner
-The Mathematics of Oz: Mental Gymnastics from Beyond the Edge,Clifford A.Pickover

Η απόδειξη από τον Γκάρντνερ