Τα Βάζα με το Γλυκό

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

"Έφτιαξα το γλυκό που σου αρέσει."

Και βλέπετε τέσσερα όμοια αδιαφανή βαζάκια. Πάτε να πάρετε τα βαζάκια και εισπράττετε μια ξυλιά στα χέρια.

"Δυο λεπτά!...", λέει η γιαγιά. "Θα πάρεις μόνο ένα από τα τέσσερα βαζάκια..."

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

Στο τέλος συμπληρώνει η γιαγιά:

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

 Έτσι λοιπόν, σε περιμένει η γιαγιά να επιλέξεις το βαζάκι...

Το ερώτημα είναι: Υπάρχει τρόπος (και ποιός) για να αυξηθούν οι πιθανότητες επιτυχίας ή πρόκειται για μια περίπτωση απλής τύχης για να βρεις το πιο γεμάτο βαζάκι; 

Βοήθεια: 

1.Υποθέστε ότι μπορείτε σαφώς να καταλάβετε τα περιεχόμενα (την ποσότητα) στο κάθε βαζάκι, απλά κοιτώντας τα.

2.Μην κολλήσετε στις περιγραφές και τη "σάλτσα" του προβλήματος.

3.Η λύση είναι κανονική, όχι καμιά εξυπνάδα του στυλ: "Δεν διαλέγω τίποτε  γιατί δεν μου αρέσουν τα γλυκά..." ή "Τα ζυγίζω", κλπ...(Κατ.33/Νο.39)
Πηγή: http://anekdota.duckdns.org/quiz/0197.html

Λύση

Λύση του Ε. Αλεξίου. Έστω 1,2,3,4 τα βάζα, 1μικρότερο του 2 μικρότερο του 3 μικρότερο του 4. Οι μεταθέσεις αυτών είναι: (1,2,3,4), (1,3,2,4), (1,2,4,3), (1,4,2,3), (1,3,4,2), (1,4,3,2), (3/6) (2,1,3,4) (2,1,4,3), (2,3,1,4), (2,3,4,1), (2,4,1,3), (2,4,3,1), (3/6) (3,1,2,4), (3,1,4,2), (3,2,1,4), (3,2,4,1), (3,4,1,2), (3,4,2,1), (6/6 (4,1,2,3), (4,1,3,2), (4,2,1,3), (4,2,3,1), (4,3,1,2), (4,3,2,1), (0/6) Παρατηρώ ότι αν ανοίγουμε βάζα μη επιλέγοντας το πρώτο μέχρι να βρούμε το πρώτο μεγαλύτερο από το προηγούμενο ή τα προηγούμενα, το οποίο και επιλέγουμε. Με αυτόν τον τρόπο πετυχαίνουμε το πιο γεμάτο βαζάκι σε 12 από τις 24 περιπτώσεις μεταθέσεων (1,2,4,3), (1,4,2,3), (1,4,3,2), (2,1,4,3), (2,4,1,3), (2,4,3,1) (3,1,2,4), (3,1,4,2), (3,2,1,4), (3,2,4,1), (3,4,1,2), (3,4,2,1) Η πιθανότητα έτσι να βρούμε το μεγαλύτερο είναι 50%. (αντί του 25% στην τύχη) Ενδιαφέρον παρουσιάζει η γενίκευση του θέματος σε "n" βάζα ή οτιδήποτε "n". Διόρθωση: Στο (1,2,4,3) δεν πετυχαίνουμε το μεγαλύτερο άρα 11/24 η πιθανότητα. Επειδή επιμένετε ότι ποσοστό που έβγαλα είναι πολύ υψηλό, σημαίνει ότι κάπου έχετε δει λύση με λιγότερο ευνοϊκό αποτέλεσμα, πιθανόν όπως η παρακάτω(πιθανόν με άλλο τρόπο, (συνδυασμών) υπολογισμένο): Μετά από 2 ανοίγματα χωρίς επιλογή διαλέγουμε το επόμενο μεγαλύτερο και από τα 2 πρώτα, δηλαδή αν το 3ο που θα ανοίξουμε είναι μεγαλύτερο από τα δύο πρώτα το διαλέγουμε, αν όχι πάμε για το 4ο. (1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3), (1,4,3,2), (3/6) (2,1,3,4) (2,1,4,3), (2,3,1,4), (2,3,4,1), (2,4,1,3), (2,4,3,1), (3/6) (3,1,2,4), (3,1,4,2), (3,2,1,4), (3,2,4,1), (3,4,1,2), (3,4,2,1), (4/6 (4,1,2,3), (4,1,3,2), (4,2,1,3), (4,2,3,1), (4,3,1,2), (4,3,2,1), (0/6) Ευνοϊκές περιπτώσεις (1,2,4,3), (1,3,2,4), (1,3,4,2), (2,1,4,3), (2,3,1,4), (2,3,4,1), (3,1,2,4), (3,1,4,2), (3,2,1,4), (3,2,4,1), συνολικά 10 στις 24 Πιθανότης: 10/24=41.666.... Με 5 βάζα έχω βγάλει Π=49/120=40.8333...% και όπως υποψιάζομαι όσο θα ανεβάζουμε τον αριθμό των βάζων η πιθανότητα ελάχιστα θα μικραίνει και πιθανόν να υπάρχει και όριο που να μην πέφτει παρακάτω, αλλά αυτό θέλει πολύ ανώτερα μαθηματικά που εγώ δεν κατέχω ως γνωστόν. Γράφει ο Γιώργος Ριζόπουλος, που προτείνει ως βέλτιστη στρατηγική την στρατηγική «Άσε 2 βαζάκια να περάσουν, και διάλεξε το αμέσως επόμενο που είναι καλύτερο από τα 2 πρώτα!» Πράγματι είναι καλή στρατηγική αλλά όχι η βέλτιστη. Αλλά ας δούμε αν την εφάρμοσε σωστά: «Nικητήριες» περιπτώσεις είναι έτσι οι: [2341],2314, 2413, 3214, 4312,4213” ωραία ως εδώ και συμφωνώ. Γράφει παρακάτω “ΚΑΙ οι 3241 (το 4 το απορρίπτουμε ,αφού είναι χειρότερο από τα 3 και 2), [2341]. Τέλεια το 2341 επαναλαμβάνεται 2 φορές. Άρα 7 οι «νικητήριες» περιπτώσεις, άρα Π= 7/24 κατά τον Γιώργο. Συμφωνείτε ότι η διπλομέτρηση είναι μέρος της ορθής και “πολύ ωραίας ανάλυσης”? Τέλεια!... Και σε αυτό. Ας δούμε όμως αν διέφυγε κάποια μετάθεση πέραν των αναφερομένων επτά (7) Νικητήρια μετάθεση 1η(8η) που διέφυγε 4231. Αφού έχουμε δεί το 2 στα δύο πρώτα βάζα σαφώς δεν επιλέγουμε και το τρίτο βαζάκι αφού 3<2 1="" 2134="" 2431.="" 2="" 3412.="" 3="" 4="">2 και φυσικά χάνουμε Όμως στο 3214, απορρίπτουμε δεύτερο και τρίτο βαζάκι (2 μικρότερο του 3, 1 μικρότερο του 3) και πάμε για το τέταρτο και κερδίζουμε. Διαβάστε όμως καλά αυτό που προτείνω και σημειωτέον η δική μου κατάταξη ως παραδοχή είναι 4 μεγαλύτερο του 3 μεγαλύτερο του 2 μεγαλύτερο του 1 για να βοηθάει συνειρμικά καθώς για τους αριθμούς ισχύει 4 μεγαλύτερο του 3 μεγαλύτερο του 2 μεγαλύτερο του 1 και να μου πείτε μια μετάταξη από τις 11 που βγαίνουν με την δική μου στρατηγική, 1423, 1432, 2143, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421 είναι λάθος, δεν είναι νικητήρια! ΟΙ ΑΡΙΘΜΟΙ ΜΙΛΑΝΕ ΜΟΝΟΙ ΤΟΥΣ ή ΜΗΠΩΣ ΟΧΙ? “Αφήνουμε το πρώτο βαζάκι και επιλέγουμε το μεγαλύτερο από το 1ο” Θεωρώ 4 μεγαλύτερο του 3 μεγαλύτερο του 2 μεγαλύτερο του 1 χάριν ευκολίας. Το ίδιο προκύπτει και αν θεωρήσουμε 1 μεγαλύτερο του 2 μεγαλύτερο του 3 μεγαλύτερο του 4 με άλλες μεταθέσεις εννοείται, φαντάζομαι να είναι κατανοητό. Αν όχι ευχαρίστως να το κάνω και με 1 μεγαλύτερο του 2 μεγαλύτερο του 3 μεγαλύτερο του 4 1423 ΝΑΙ, μάς πέφτει το 4 άμεσα, ΚΕΡΔΙΖΟΥΜΕ 1432 ΝΑΙ, μάς πέφτει το 4 άμεσα, ΚΕΡΔΙΖΟΥΜΕ 2143 ΝΑΙ, 1 μικρότερο του 2, πάμε παρακάτω 4, ΚΕΡΔΙΖΟΥΜΕ 2413 ΝΑΙ, μάς πέφτει το 4 άμεσα, ΚΕΡΔΙΖΟΥΜΕ 2431 ΝΑΙ, μάς πέφτει το 4 άμεσα, ΚΕΡΔΙΖΟΥΜΕ 3124 ΝΑΙ, 1,2 μικρότερο του 3, πάμε παρακάτω μας πέφτει το 4, ΚΕΡΔΙΖΟΥΜΕ 3142 ΝΑΙ, 1 μικρότερο του 3, πάμε παρακάτω μας πέφτει το 4, ΚΕΡΔΙΖΟΥΜΕ 3214 ΝΑΙ, 2,1 μικρότερο του 3, πάμε παρακάτω μας πέφτει το 4, ΚΕΡΔΙΖΟΥΜΕ 3241 ΝΑΙ, 2 μικρότερο του 3, πάμε παρακάτω μας πέφτει το 4, ΚΕΡΔΙΖΟΥΜΕ 3412 ΝΑΙ, μάς πέφτει το 4 άμεσα, ΚΕΡΔΙΖΟΥΜΕ 3421 ΝΑΙ, μάς πέφτει το 4 άμεσα, ΚΕΡΔΙΖΟΥΜΕ (με το αφήνουμε το πρώτο κερδίζουμε και στις 6 μεταθέσεις με 1ο βαζάκι το 3, μεγάλο πλεονέκτημα! Μετράω και ξανά μετράω και βγάζω 11>10 ευνοϊκές περιπτώσεις ΘΡΙΑΜΒΟΣ! ΜΕΓΙΣΤΟΠΟΙΗΣΗ ΠΙΘΑΝΟΤΗΤΑΣ 11/24 μεγαλύτερο του 10/24 Μου διαφεύγει κάτι που δεν το βλέπω? Συνοψίζοντας και γενικεύοντας το πολύ ενδιαφέρον αυτό θέμα για n αντικείμενα (στην περίπτωση μας n=4). To πρώτο και βασικό θέμα είναι η εύρεση του αριθμού, έστω m που αφήνουμε αρχικά (στην περίπτωση μας m=1 ή m=2, διΐστανται μέχρι στιγμής οι απόψεις). Ο τύπος που δίνει την βέλτιστη επιλογή του m είναι m=n*(1/e) Ο τύπος που δίνει την βέλτιστη πιθανότητα P(m) είναι: P(m)= (m/n)Σ(1/i), ι=m,(m+1),..,(n-1) → P(m)= (m/n)[1/m +1/(m+1) +1(m+2)+...+1/(n-1)] Για n=3 και m=1 (τρία βαζάκια και αφήνουμε το ένα το πρώτο) μας δίνει: P(1)=(1/3)*(1/1 +1/2)=1/2 όπως ακριβώς βγαίνει και με τις μεταθέσεις. Για n=4, m=2 (βέλτιστη λύση κατά Γ. Ριζόπουλο) μάς δίνει: P(2)=(2/4)*(1/2+1/3)=10/24, όπως ακριβώς τα υπολογίσαμε με τις μεταθέσεις Για n=4, m=1 (βέλτιστη λύση κατά Ε. Αλεξίου) μάς δίνει: P(2)=(1/4)*(1/1+1/2+1/3)=11/24, όπως ακριβώς υποστηρίζω με απόλυτη βεβαιότητα από την αρχή. Τα συμπεράσματα κ. Κάρλο για την βέλτιστη λύση, δικά σας. Για n=5, βέλτιστο m=2, όπως ακριβώς έχω ήδη γράψει P(2)=(2/5)*(1/2+1/3+1/4)=52/120 =0.4333..., είχα βρει 49/120, πράγματι μετά από έλεγχο των 120 μεταθέσεων που έχω κάνει στο χαρτί βρήκα και τις υπόλοιπες τρεις που μου διέφυγαν. Για n πολύ μεγάλο, ας πούμε n=100.000 (για να μπορεί η Βολφραμάλφα -Wolfram Alpha - να κάνει τις πράξεις) κατάλληλο m=100.000/e =36.787,944117, επιλέγουμε προφανώς m=36.788 (μερικές φορές χρειάζεται έλεγχο όταν ας πούμε βγει m=agc..k,515, ποιος από τους 2 πλησιέστερους ακέραιους είναι ο καταλληλότερος) και έχουμε: P(36788)=(36788/100000)*(1/36788+1/36789+...+1/99999)= 0.36788*1.00000707238937839529...= 0.3678826... μεγαλύτερο του 1/e=0.36787944... Απίστευτο και όμως αληθινό, από 100.000 με αυτή την στρατηγική πετυχαίνουμε το καλύτερο με πιθανότητα 36,79% Αλλά και όπως έχω διαβάσει στο παρελθόν, (τα μαθηματικά πέραν των γυμνασιακών χρόνων δεν με ενδιέφεραν αλλά οι γρίφοι, σπαζοκεφαλιές και τέτοιου είδους προβλήματα, ήταν ένα από τα αγαπημένα μου χόμπυ μέχρι τα 33 μου, ε μετά οικογένεια, η καριέρα που ήταν στο φούλ και η ενασχόληση μου έντονα με την πολιτική, δεν μου άφηναν χρόνο ούτε για ένα 6ωρο ύπνου) οσοδήποτε μεγάλο και να είναι το n, n να τείνει στο άπειρο με το κατάλληλο m=n/e , η πιθανότητα ποτέ δεν θα γίνει μικρότερη του 1/e=0.367879... Απίστευτο, σχεδόν σχιζοφρενικό.. Γράφω εδώ καθώς το “Τα βάζα με το Γλυκό”, όχι μην φοβάσθε ότι θα συνεχίσω την αντιπαράθεση μαζί σας, αν και δεν αποφασίσατε ακόμη πια είναι η βέλτιστη λύση, γιατί εκει φρακάρισε από σχόλια και θα χαθεί. Το βιβλίο που διάβασα (πρίν ενάμισυ-δύο χρόνια, μαλιστα είναι το από τα πρώτα αυτης της κατηγορίας μετα από δεκαετίες το βρήκα στην βιβλιοθήκη μου), για το πρόβλημα της βέλτιστης επιλογής του καλύτερου μεταξύ 4,..,10,..., n επιλογών είναι: ΤΑ ΜΑΘΗΜΑΤΙΚΑ ΤΟΥ ΟΖ του KLIFFORD A. PICKOVER Πρόβλημα 70: Η ΕΠΙΛΟΓΗ, σελίδα 194 Η απάντηση στις σελίδες 397, 398, 399 όπου αναπτύσσει το θέμα αρκετά διεξοδικά και κυρίως κατανοητά. Το βιβλίο αυτό σας το συνιστώ ανεπιφύλακτα, αν δε το έχετε διαβάσει, μιας και ασχολείσθε και μάλιστα σαν θεματοθέτης το τελευταίο διάστημα, με αρκετά δύσκολα θέματα και πολύ καλά κάνετε, στο παρελθόν εξάλλου σας είχα ζητήσει κατ' επανάληψη να ανεβάσετε τον πήχυ δυσκολίας των θεμάτων. Λύση του Γ. Ριζόπουλου. Το πρόβλημα δεν είναι «θεωρητικό» ή «στο περίπου» ,αλλά πολύ ακριβές και συγκεκριμένο ποσοτικά. Καταρχάς , το «μικρό βαζάκι» είναι κάπως προβληματικό στην εκφώνηση, γιατί το νόημα είναι να μην ξέρουμε εκ των προτέρων, δηλαδή τη στιγμή που το βλέπουμε, το βέλτιστο. Γι’αυτό και λέγεται «πρόβλημα της γραμματέως» η «της ταιριαστής νύφης». Η σειρά κατάταξης είναι ξεκάθαρη μόνο στο τέλος. Ένα μικρό βαζάκι γεμάτο είναι το βέλτιστο, οπότε πιο σωστά θα έπρεπε να είναι ένα πολύ μεγάλο βάζο (που δεν μπορεί να είναι τελείως γεμάτο ποτέ) . Ας πούμε πως έχουμε να δούμε 3 υποψήφιες νύφες (ή υποψήφια βαζάκια με γλυκό). Δεν ξέρουμε με ποια σειρά θα τις/τα δούμε. Η σειρά με την οποία εμφανίζονται μπροστά μας μπορεί να είναι τυχαία, δηλαδή οποιαδήποτε από τις μεταθέσεις ισοπίθανα. Ν! για Ν αντικείμενα. Όταν απορρίψουμε μια νύφη/γραμματέα/βαζάκι φεύγουν και δεν γυρίζουν πίσω. Τώρα είναι πλήρως ορισμένο το πρόβλημα. Για 3 βαζάκια ,υπάρχουν 3!=6 πιθανοί συνδυασμοί/σειρές εμφάνισης. (123), (132), (213), (231), (312), (321) Έστω 1>2>3 με την έννοια δηλαδή πως το 1 είναι το τελικά καλύτερο βαζάκι ,2 το αμέσως πιο κάτω και 3 το χειρότερο. Είναι προφανές πως αν επιλέξουμε στην τύχη ένα οποιοδήποτε βάζο που βλέπουμε, η πιθανότητα να διαλέξουμε το 1 είναι 0,33% (1 στις 3). Η ίδια πιθανότητα υπάρχει αν ακολουθήσουμε ας πούμε τον κανόνα «Διάλεξε το πρώτο βαζάκι!» Ο κανόνας θα δούλευε αν ήμασταν σε μια από τις 2 πρώτες μεταθέσεις (123 , 132) και όχι στις υπόλοιπες. 2/6 =1/3. Αν βάζαμε τον κανόνα «Διάλεξε το δεύτερο βαζάκι» (ή το τρίτο) ,θα συνέβαινε ακριβώς το ίδιο. Οι «καλές» μεταθέσεις είναι ανά περίπτωση 2 από τις 6 συνολικά, άρα η p(επιτυχίας)=0,33. Το πρόβλημα λοιπόν που αντιμετωπίζουμε είναι η απάντηση στην ερώτηση: “Υπάρχει τρόπος να αυξήσουμε αυτή την πιθανότητα;» Ας βάλουμε στον εαυτό μας έναν άλλο κανόνα: “Άσε το πρώτο βαζάκι να περάσει και διάλεξε το αμέσως επόμενο, που είναι καλύτερο(πιο γεμάτο) από το πρώτο!» Για να δούμε τι γίνεται τώρα. Στις πρώτες δύο μεταθέσεις (123, 132) δεν δουλεύει (χάνουμε το 1) αλλά δουλεύει στις περιπτώσεις 213, 231, και 312. Σε τρεις δηλαδή περιπτώσεις ,ενώ το αρχικό τυχαίο δούλευε μόνο σε 2. Αμέσως βελτιώσαμε λοιπόν την πιθανότητα από 33% σε 50% . ΑΥΤΟ είναι το κόλπο! Ε, στην περίπτωσή μας με τα 4 βαζάκια, οι δυνατές μεταθέσεις (με το συμβολισμό πάντα: 1 το καλύτερο, 2 το δεύτερο καλύτερο κ.λ.π.) είναι 4!=24, οι εξής: 1234 2134 3124 4123 1243 2143 3142 4132 1324 2341 3214 4213 1342 2314 3241 4231 1432 2413 3412 4312 1423 2431 3421 4321 Ποιος κανόνας θα αυξήσει το στάνταρ ¼ (25%) ; Με απλή εξέταση των περιπτώσεων είναι φανερό πως ο κανόνας πρέπει να είναι: “Άσε 2 βαζάκια να περάσουν, και διάλεξε το αμέσως επόμενο που είναι καλύτερο από τα 2 πρώτα!» “Nικητήριες» περιπτώσεις είναι έτσι οι: 2341,2314, 2413, 3214, 4312,4213 (αυτές που είναι έτσι κι αλλιώς «στάνταρ» με τυχαία επιλογή: 6 στις 24) ΚΑΙ οι 3241 (το 4 το απορρίπτουμε ,αφού είναι χειρότερο από τα 3 και 2) ,2341 . Σύνολο: 8/24 = 33%. Σημαντική αύξηση πιθανοτήτων επιτυχίας. Απλό, «μαγικό» και πολύ συγκεκριμένο αριθμητικά. Η γενική περίπτωση για ν υποψήφια βαζάκια έχει την γενική απάντηση που έγραψα στο πρώτο σχόλιο, και η απόδειξη της βελτιστοποίησης είναι κάπως τεχνική. Ίσως γράψω κάποια στιγμή στο «eisatopon.» Eνδιαφέρον θέμα Κάρλο εφαρμοσμένης Συνδυαστικής, με εφαρμογές σε αρκετούς τομείς. (decision theory, game theory, optimal algorithms, κ.α) Άφησα απέξω από τις "νικητήριες" 2 ευνοϊκές περιπτώσεις. Aς ξαναμετρήσω αναλυτικά: (Σύμβαση: 1 το καλύτερο,κλπ.) 1234 2134 3124 4123 1243 2143 3142 4132 1324 2341 3214 4213 1342 2314 3241 4231 1432 2413 3412 4312 1423 2431 3421 4321 Η 1η στήλη έχει πρώτο το 1 πάει όλη στράφι. 2η στήλη: (2341 NAI), (2314 NAI), (2413 NAI), (2431 NAI) 3η στήλη: (3214 NAI), (3241 NAI), (3412 NAI), (3421 OXI) 4η στήλη: (4213 NAI), (4231 NAI), (4312 NAI), (4321 OXI) ΣΥΝΟΛΟ ΝΑΙ: 4+3+3=10. Σύνολο λοιπόν: 10/24= ≈ 41,7%.