"Κάθε ζυγός αριθμός μεγαλύτερος του 2, μπορεί να εκφραστεί σαν άθροισμα 2 πρώτων. Έχω μια θαυμάσια απόδειξη γι'αυτό, αλλά δεν προλαβαίνω να τη γράψω γιατί έρχεται το τρένο."
Γκράφιτι σε σταθμό του μετρό στην Νέα Υόρκη
O μαθηματικός Σωκράτης αποφασίζει να αθλοθετήσει ένα βραβείο για τους 50 μαθητές του. Γράφει σε 50 κάρτες τους αριθμούς από το 1 έως το 50. Στους μαθητές αντιστοιχούν επίσης οι αριθμοί 1 ώς 50 (ας πούμε αλφαβητικά). Οι κάρτες τοποθετούνται ανάποδα και ανακατεμένες στην τύχη πάνω σ' ένα τραπέζι.
Κάθε μαθητής μπορεί να αναποδογυρίσει μέχρι 25 κάρτες. Αν βρει τον αριθμό του, κερδίζει! Το βραβείο όμως είναι πολύ σημαντικό και ο Σωκράτης αποφάσισε να το δώσει, μόνο αν το κερδίσουν όλοι. Αν αναποδογυρίσουν δηλαδή όλοι τον αριθμό τους. Μετά από κάθε προσπάθεια ,οι κάρτες ξαναγυρίζουν ανάποδα και ο κάθε μαθητής δεν βλέπει τι κάνει ο άλλος,ούτε επιτρέπεται ,μόλις ξεκινήσει το παιχνίδι, η επικοινωνία μεταξύ τους.
Κάθε μαθητής μπορεί να αναποδογυρίσει μέχρι 25 κάρτες. Αν βρει τον αριθμό του, κερδίζει! Το βραβείο όμως είναι πολύ σημαντικό και ο Σωκράτης αποφάσισε να το δώσει, μόνο αν το κερδίσουν όλοι. Αν αναποδογυρίσουν δηλαδή όλοι τον αριθμό τους. Μετά από κάθε προσπάθεια ,οι κάρτες ξαναγυρίζουν ανάποδα και ο κάθε μαθητής δεν βλέπει τι κάνει ο άλλος,ούτε επιτρέπεται ,μόλις ξεκινήσει το παιχνίδι, η επικοινωνία μεταξύ τους.
Υπάρχει κάποια στρατηγική που μπορούν να προαποφασίσουν οι μαθητές, ώστε να αυξήσουν σημαντικά τις πιθανότητες νίκης; (και να εντυπωσιάσουν και τον μαθηματικό τους!)
Μα τι μαθηματικός είναι ο Σωκράτης και τι αθλο-θέτηση είναι αυτή! Βραβείο "Μόνο αν το κερδίσουν όλοι" Αφού μόνο ο ένας έχει πιθανότητα 50% και φαινομενικά και "παγιδευτικά" όλοι μαζί, αφού οι κάρτες είναι με επανάθεση, (1/2)^50.
ΑπάντησηΔιαγραφήΈνα πιο ρεαλιστικό βραβείο...
Υ.Γ. Κε Ριζόπουλε, παράλειψη μου, ενδιαφέρον θέμα!
ΑπάντησηΔιαγραφή@ RIZOPOULOS GEORGIOS
ΑπάντησηΔιαγραφήΤο γνωρίζω το θέμα, το έλυσα παλιότερα σε άλλο μπλόγκ
με πολύ μικρότερους αριθμούς εκεί 4 και 2, αντί 50 και 25, αλλά το είχα γενικεύσει οπότε δεν έχει καμία διαφορά.
Γιαυτό και το σχόλιο μου για το..τσιγκούνικο βραβείο μόνο αν κερδίσουν όλοι.
Και βέβαια το θέμα είναι ενδιαφέρον αλλά για τους
άλλους, όσους δεν το γνωρίζουν!
@ Ε.Aλεξίου: Ωραία. Μπορεί και για σάς να γίνει ενδιαφέρον νομίζω, παρότι γνωρίζετε την ιδέα της στρατηγικής,αν θελήσετε να υπολογίσετε με ακρίβεια την πιθανότητα νίκης για τους 50. :-)
ΑπάντησηΔιαγραφή@ RIZOPOULOS GEORGIOS
ΑπάντησηΔιαγραφήΝα υπολογίσω κάτι πιο ακριβές από το 0,3167528?
ή έχω κάνει λάθος γενίκευση και να το ξαναδώ?
H ενδεδειγμένη στρατηγική είναι η εξής:
ΑπάντησηΔιαγραφήO ν-ιοστός μαθητής πρέπει να πάει στην ν-ιοστή κάρτα και να τη γυρίσει πρώτη. Αν η κάρτα γράφει τον αριθμό μ ,πάει στην μ-ιοστή κάρτα ,κλπ. μέχρις ώσπου βρει την κάρτα ν, ή εξαντλήσει τις 25 προσπάθειες ανεπιτυχώς.
Μ’αυτόν τον τρόπο ,οι αρχικά απειροελάχιστη πιθανότητα ομαδικής νίκης, αυξάνεται σημαντικά. Η εξήγηση βρίσκεται στο ότι οι αριθμοί δημιουργούν κύκλους (permutation circles) ,ή μ’άλλα λόγια οδηγούν από τον έναν στον άλλον μέσω πεπερασμένου και συγκεκριμένου αριθμού βημάτων, και έτσι ο κάθε μαθητής θα βρει τον αριθμό του με τον μέγιστο αριθμό αυτών των βημάτων (που αν είναι κάτω από 25, σημαίνει νίκη! )στην δυσμενέστερη περίπτωση/σενάριο.
Έτσι ,για να νικήσει ο καθένας από τους μαθητές, όλοι οι κύκλοι πρέπει να έχουν μήκος μικρότερο ή ίσο με 25. Έτσι, μιας και υπάρχουν 50! διαφορετικές πιθανές μεταθέσεις(permutations) για 50 κάρτες, και από αυτές υπάρχουν για κάθε «κακό» μήκος κύκλου ,έστω Κ, («κακό/μη ευνοϊκό» σημαίνει Κ>25) ,50!/Κ(i) ,προκύπτει ότι οι ευνοϊκές μεταθέσεις είναι οι ολικές (50!) μείον τις κακές, ή:
50! -(50!/26 +50!/27 +50!/28 +50!/29 +50!/30 +...+50!/50)
Και οι πιθανότητα (ευνοϊκά/ολικά):
(50! -(50!/26 +50!/27 +50!/28 +50!/29 +50!/30 +...+50!/50))/50!=
=981631146221515418647 / 3099044504245996706400 = 0,3167528…
Δηλαδή μια πιθανότητα λίγο πάνω από 30%. Καθόλου κακή!
ΥΓ. Να εποπτικοποιήσω λίγο την εξήγηση, με ένα σαφές παράδειγμα για 10 αριθμούς/κάρτες.
Ας υποθέσουμε ότι οι κάρτες είναι στην τυχαία σειρά:
10 , 2, 4 , 5, 7, 1, 9, 6, 3, 8
Σύμφωνα με τη «μέθοδο» ο 1ος μαθητής πάει στην 1ηκάρτα ,δηλαδή στο 10. Διαβάζει «10» οπότε πάει στην 10η κάρτα δηλ. το 8. Μετά στην 8η δηλ. το 6, μετά στην 6η ,δηλαδή το 1 (που είναι ο αριθμός του!) . Αν συνέχιζε ,θα πήγαινε στο 10 κλπ. Βλέπουμε δηλαδή ότι υφίσταται ο κύκλος : (10, 8, 6, 1, 10,)… και εφόσον αυτός ο κύκλος έχει μήκος=4 <5 , όλοι οι μαθητές με αύξοντα αριθμό: 10, 8, 6, 1 εγγυημένα θα βρουν την κάρτα τους με 4 ή λιγότερα βήματα, άρα θα κερδίσουν όλοι.
Αυτή η μέθοδος, εξ όσων γνωρίζω, βρίσκει σημαντική εφαρμογή σε υπολογιστικούς αλγόριθμους , μιας και είναι προφανώς μια «οικονομική» και έξυπνη μέθοδος, από πολλές πλευρές.