Τα εργασία παζλ τον περασμένο μήνα ήταν να σώσει ένα Star Trek επιφανειακό κόμμα των οκτώ με επικεφαλής τον Εταιρεία Υπεύθυνη Επικοινωνίας Υπολοχαγός Ουχούρα (παίζει ο αείμνηστος Nichelle Nichols). Το πλήρωμα φυλακίζεται από μια εξωγήινη φυλή, τους Κατενάτι, σε έναν πλανήτη του Νεφέλωμα κολιέ. Για να ξεφύγουν, πρέπει να μεγιστοποιήσουν την πιθανότητα να εκτελέσουν μια εργασία που στην αρχή φαίνεται να προσφέρει μόνο μια θλιβερή πιθανότητα επιτυχίας.
Το πλήρωμα των οκτώ ατόμων ενημερώνεται για το έργο ενώ κρατείται προσωρινά σε μια κοινή αίθουσα όπου είναι ελεύθεροι να επικοινωνούν και να σχεδιάζουν στρατηγική. Σε λίγες ώρες, θα οδηγηθούν, ένας κάθε φορά, σε ένα δωμάτιο που ονομάζεται θάλαμος ρουλέτας. Αυτό το δωμάτιο έχει οκτώ κουμπιά τοποθετημένα στη σειρά, καθένα από τα οποία είναι προγραμματισμένο να ανταποκρίνεται σε διαφορετικό μέλος του πληρώματος. Για να παραπλανηθεί το πλήρωμα, κάθε κουμπί επισημαίνεται τυχαία με το όνομα άλλου μέλους του πληρώματος. Κάθε μέλος του πληρώματος επιτρέπεται να πατήσει έως και τέσσερα από τα κουμπιά, με οποιαδήποτε σειρά. Κάθε φορά που πατούν ένα κουμπί, θα δουν σε ποιον ανήκει πραγματικά το κουμπί. Μέσα στις τέσσερις προσπάθειές τους, πρέπει να βρουν το κουμπί που τους έχει ανατεθεί. Για να απελευθερωθεί το πλήρωμα, πρέπει όλοι να επιτύχουν σε αυτό το έργο. Εάν έστω και ένα από αυτά αποτύχει, όλα θα εκτελεστούν. Αφού ένα μέλος του πληρώματος ολοκληρώσει την προσπάθειά του, πρέπει να απομονωθεί χωρίς τρόπο να διαβιβάσει πληροφορίες σε κανέναν από τους συντρόφους του πληρώματος.
Οι πιθανότητες επιτυχίας φαίνονται ελάχιστες. Εάν τα μέλη του πληρώματος επιλέξουν κουμπιά τυχαία, το καθένα θα έχει 1 στις 2 πιθανότητες να βρει το κουμπί του. Η πιθανότητα να πετύχουν και οι οκτώ είναι μόλις 1 στις 256, ή περίπου 0.4%.
Αλλά δεν χρειάζεται να πατούν κουμπιά τυχαία. Ένας τρόπος για να αυξήσετε την πιθανότητα επιτυχίας θα μπορούσε να είναι να εξομαλύνετε όλα τα πατήματα των κουμπιών με κάποιο τρόπο. Αυτό μας φέρνει στην πρώτη μας ερώτηση παζλ.
Παζλ 1
Κατά πόσο μπορεί να βελτιωθεί η πιθανότητα επιβίωσης του πληρώματος, εάν βεβαιωθεί ότι κάθε κουμπί πατιέται εξίσου συχνά (αντί να πατάει οποιαδήποτε τέσσερα κουμπιά τυχαία);
Ρομπ Κόρλετ και JPayette απάντησε καλά, όπως έκαναν και όλες οι άλλες ερωτήσεις. Όσο για την άπιαστη κεντρική ιδέα πίσω από τα παζλ αυτής της στήλης, οι Rob Corlett, JPayette και Jouni Seppänen το περιέγραψε όμορφα, ενώ Sacha Bugnon συνέβαλε μια λύση υπολογιστή.
Εδώ είναι η απάντηση του Rob Corlett:
Ένας τρόπος για να διασφαλίσετε ότι κάθε κουμπί πατιέται ίσες φορές είναι να χωρίσετε τους κρατούμενους σε δύο ίσου μεγέθους ομάδες των 4.
Κάθε ομάδα πατάει μόνο τα κουμπιά που αντιστοιχούν στα μέλη της ομάδας της. Έτσι, εάν τα A, B, C και D είναι όλα στην ίδια υποομάδα, πατούν μόνο τα κουμπιά για A, B, C και D.
Αυτό αλλάζει το πρόβλημα και ζητά την πιθανότητα ότι κάθε κρατούμενος κατανέμεται στη σωστή ομάδα, καθώς τότε είναι εγγυημένο ότι θα πατήσει το κουμπί του με τέσσερα ή λιγότερα πατήματα.
Ο αριθμός των τρόπων συμπλήρωσης της πρώτης ομάδας (και επομένως και της δεύτερης ομάδας) με τέσσερα άτομα είναι ο αριθμός των τρόπων επιλογής 4 από 8 που είναι C(8, 4) = 70. Επομένως, ο συνολικός αριθμός τρόπων Η κατανομή όλων στις δύο ομάδες είναι 70.
Υπάρχει μόνο μία κατανομή που κατανέμει σωστά κάθε κρατούμενο στη σωστή ομάδα και έτσι η πιθανότητα να είναι όλοι στη σωστή ομάδα και όλοι οι κρατούμενοι να επιβιώσουν είναι 1/70, που είναι 3.66 φορές καλύτερη από το 1/256 της προηγούμενης στρατηγικής. [Αλλά είναι ακόμα πολύ μικρό: μόλις 1.4% πιθανότητα.]
Παζλ 2
Υπάρχει τρόπος να βελτιωθούν οι αρχικές θλιβερές πιθανότητες πάνω από 90 φορές, σε περίπου 36.5%, που φαίνεται θαυματουργό! Αυτή η στρατηγική περιλαμβάνει τη χρήση βρόχων ή αλυσίδων εικασιών — εξ ου και οι αναφορές στο Νεφέλωμα του Κολιέ και στο Κατενάτι (αλυσίδα είναι λατινικά για την αλυσίδα). Στη βασική μορφή της στρατηγικής, κάθε μέλος του πληρώματος ξεκινά πατώντας το κουμπί που φέρει το όνομά του, μετά πηγαίνει στο κουμπί που φέρει το όνομα του μέλους του πληρώματος στο οποίο ανήκε στην πραγματικότητα το πρώτο κουμπί και ούτω καθεξής, δημιουργώντας μια αλυσίδα ονομάτων.
Ας δούμε πώς λειτουργεί αυτό στην πράξη. Στο διάγραμμα, τα κουμπιά εμφανίζονται με τις ετικέτες τους σε λευκό χρώμα. Τα μπλε γράμματα παρακάτω δείχνουν τους πραγματικούς ιδιοκτήτες των κουμπιών. Όταν το πρώτο μέλος του πληρώματος, η Α, μπαίνει στον θάλαμο της ρουλέτας, πατάει πρώτα το κουμπί Α. Αυτό είναι το κουμπί της C, οπότε πατάει το κουμπί C στη συνέχεια, μετά το κουμπί E και τέλος το κουμπί F, που είναι στην πραγματικότητα το κουμπί του ίδιου του A, οπότε το βρήκε με επιτυχία σε τέσσερις προσπάθειες. Σημειώστε ότι τα κουμπιά ACEF σχηματίζουν έναν κλειστό βρόχο τεσσάρων κουμπιών. Όταν τα μέλη του πληρώματος C, E και F παίρνουν τη σειρά τους, θα περάσουν επίσης στον ίδιο κλειστό βρόχο, ξεκινώντας από τις αντίστοιχες θέσεις τους, και επίσης θα βρουν τα δικά τους κουμπιά σε τέσσερις προσπάθειες.
Αυτή η διάταξη έχει επίσης δύο μικρότερους βρόχους από δύο κουμπιά ο καθένας: BD και GH. Αυτά τα τέσσερα μέλη του πληρώματος θα βρουν τα δικά τους κουμπιά μέσα σε δύο προσπάθειες. Έτσι, με αυτή τη ρύθμιση, όλα τα μέλη του πληρώματος θα έχουν επιτυχία και θα έχουν κερδίσει την ελευθερία τους. Είναι σαφές ότι εάν η διάταξη περιέχει μόνο βρόχους μήκους 4 ή λιγότερο, όλα τα μέλη του πληρώματος θα έχουν επιτυχία και θα απελευθερωθούν. Εάν, από την άλλη πλευρά, υπάρχει ένας μόνο βρόχος 5 ή περισσότερων, τότε όλα τα μέλη του πληρώματος σε αυτόν τον βρόχο θα αποτύχουν να βρουν το κουμπί τους σε τέσσερις προσπάθειες και το πλήρωμα θα εκτελεστεί. Για να βρούμε την πιθανότητα επιτυχίας, μπορούμε να βρούμε την πιθανότητα να έχουμε έναν βρόχο 5, 6, 7 ή 8, να τα αθροίσουμε και να αφαιρέσουμε αυτό το άθροισμα από το 1. Αυτό είναι πιο εύκολο να υπολογιστεί από τον άλλο τρόπο, γιατί για οκτώ κουμπιά, μπορεί να υπάρχει μόνο ένας βρόχος με 5, 6, 7 ή 8 μέλη.
Υπάρχουν 8! διαφορετικούς τρόπους για να τακτοποιήσετε οκτώ κουμπιά. Αλλά όταν κάνουμε βρόχους, ο ίδιος βρόχος αντιπροσωπεύει οκτώ από αυτές τις ρυθμίσεις (το ABCDEFGH σχηματίζει τον ίδιο βρόχο με το BCDEFGHA, το οποίο είναι το ίδιο με το CDEFGHAB, κ.λπ.). Άρα η πιθανότητα να έχουμε βρόχο μεγέθους 8 είναι (8!/8)/8!, που είναι απλά 1/8. Ομοίως, η πιθανότητα να έχουμε βρόχο μεγέθους 7 είναι 1/7, μεγέθους 6 είναι 1/6 και μεγέθους 5 είναι 1/5. Επομένως, η πιθανότητα επιτυχίας για το ατρόμητο πλήρωμά μας είναι 1 − (1/5 + 1/6 + 1/7 + 1/8), ή 36.5%, όπως αναφέρθηκε προηγουμένως.
Η παραπάνω στρατηγική λειτουργεί για οποιονδήποτε αριθμό κρατουμένων και η βελτίωση των πιθανοτήτων έναντι της τυχαίας προσέγγισης αυξάνεται γρήγορα όσο αυξάνεται αυτός ο αριθμός. Είναι περίπου επταπλάσιο για τέσσερις κρατούμενους, 24 φορές για έξι, 93 φορές για οκτώ και εκπληκτικό (3.8 × 1029)-πάσο για 100 κρατούμενους. Το κλειδί για την κατανόηση αυτής της τεράστιας αύξησης είναι ότι η μέθοδος συνδέει την επιτυχία ή την αποτυχία κάθε μέλους της ομάδας με αυτή των άλλων. Σε πολύ μεγάλο βαθμό, όλοι μαζί πετυχαίνουν ή αποτυγχάνουν. Η πιθανότητα επιτυχίας της ομάδας δεν μειώνεται πολύ από αυτή ενός μεμονωμένου ατόμου, πέφτοντας μόνο από το 50% για έναν μόνο κρατούμενο σε 30.69% καθώς ο αριθμός των κρατουμένων αυξάνεται απεριόριστα. Από την άλλη πλευρά, η πιθανότητα επιτυχίας μιας τυχαίας προσέγγισης ή ακόμα και μιας προσέγγισης «ζυγών κουμπιών» μειώνεται γρήγορα σε πολύ κοντά στο μηδέν ακόμη και για έναν μικρό αριθμό κρατουμένων.
Εάν η λογική πίσω από αυτή τη στρατηγική εξακολουθεί να φαίνεται ασαφής, εδώ είναι μια ανάλυση του προβλήματος των 100 κρατουμένων σε αυτό εξαιρετικό βίντεο από το Veritasium.
Παζλ 3
Αυτό το παζλ αφορούσε τον υπολοχαγό Ουχούρα που θυμόταν ένα παιδικό παιχνίδι, το οποίο ήταν ουσιαστικά το ίδιο παζλ, αλλά για έξι άτομα. Ως υπόδειξη, πρότεινα την επίλυση του προβλήματος για τέσσερα άτομα. Τώρα που έχουμε τον τύπο, μπορούμε εύκολα να υπολογίσουμε τις πιθανότητες.
Για τέσσερα άτομα, η πιθανότητα ο μεγαλύτερος βρόχος να είναι μόλις 2 ή 1 είναι: 1 − (1/3 + 1/4) ή 41.7% με επταπλάσιο κέρδος έναντι της τυχαίας επιλογής.
Για έξι άτομα, η πιθανότητα ο μεγαλύτερος βρόχος να είναι 3, 2 ή 1 είναι: 1 − (1/4 + 1/5 + 1/6) ή 38.3% με περισσότερο από 24πλάσιο κέρδος σε σχέση με την τυχαία επιλογή.
Παζλ 4
Καθώς η ιστορία μας συνεχίζεται, αποδεικνύεται ότι ένας από τους Κατενάτι έχει αντιπαθήσει ιδιαίτερα το Εταιρεία πλήρωμα και τους παρακολουθεί εξ αποστάσεως. Υποψιάζεται ότι έχουν καταλήξει σε κάποια αποτελεσματική στρατηγική που βασίζεται στο διάγραμμα του Ουχούρα. Είναι αποφασισμένος να ματαιώσει το σχέδιό τους γλιστρώντας στην αίθουσα και αλλάζοντας σκόπιμα τη σειρά των ετικετών των κουμπιών πριν ξεκινήσει η ρουλέτα. Μπορεί να ματαιώσει με επιτυχία το σχέδιο; Τι πρέπει να είναι ιδιαίτερα προσεκτικό για να κρύψει η προσγείωση;
Πολύ νωρίς στη συζήτηση στρατηγικής του πληρώματος, τα μάτια του Ουχούρα στένεψαν ξαφνικά. Έδωσε ένα σήμα στο πλήρωμά της και άλλαξε να μιλήσει στα Nicholese, ανακοινώνοντας: «Όλη η περαιτέρω συζήτηση στο Nicholese, παρακαλώ». Η Nicholese ήταν μια νέα γλώσσα που η Ουχούρα είχε εφεύρει νωρίς στην καριέρα της ακριβώς για τέτοιου είδους καταστάσεις, για να παρακάμψει τη χρήση των καθολικών μεταφραστών. «Πρέπει να προσέξατε αυτόν τον ύποπτο Κατενάτι», συνέχισε. «Θα μπορούσε να προσπαθήσει να μας σαμποτάρει, οπότε πρέπει να τροποποιήσουμε το σχέδιό μας. Να τι πρέπει να κάνουμε…»
Η Ουχούρα περιέγραψε το νέο σχέδιο μέχρι να βεβαιωθεί ότι κάθε μέλος του πληρώματος της το γνώριζε πολύ καλά. Στη συνέχεια, σκέφτηκε, με ένα μακρινό βλέμμα στα μάτια της: «Ονόμασα τη Nicholese από μια εμβληματική ηθοποιό του 20ου αιώνα. Χαίρομαι που επέμενα στο Starfleet να το κάνει στάνταρ σε όλα μας τα πλοία.»
Γύρισε πίσω στο πλήρωμα. «Αυτό είναι όλο, αξιωματικοί. Ξέρετε τι πρέπει να κάνετε!"
Δεν ξέρουμε τι ακριβώς είπε η Ουχούρα στην ομάδα της. Αλλά η JPayette και ο Rob Corlett είχαν μια πολύ καλή ιδέα. Εδώ είναι πάλι ο Rob Corlett:
Εάν ο κακός Catenati ακούσει ότι χρησιμοποιούν αυτή τη στρατηγική, τότε μπορεί να αλλάξει τα ονόματα που εμφανίζονται στην οθόνη για να διασφαλίσει ότι υπάρχει ένας κύκλος μεγαλύτερος από 4.
Για να διακοπεί αυτό, οι κρατούμενοι πρέπει να συμφωνήσουν σε μια μυστική παραγγελία που τυχαιοποιεί την ακολουθία. Το κάνουν λέγοντας κάτι σαν «αν δείτε το όνομα του Ουχούρα, τότε πηγαίνετε στο κουμπί με την ένδειξη Τσέκοφ. Αν δείτε το όνομα του Τσέκοφ να εμφανίζεται, μεταβείτε στο κουμπί με την ένδειξη Smith, κ.λπ.».
Με αυτόν τον τρόπο, η αναδιάταξη από το Catenati δεν έχει σημασία, καθώς λειτουργεί μόνο εάν γνωρίζετε τον τρόπο με τον οποίο το πλήρωμα θα απαντήσει στα ονόματα στις οθόνες. Ωστόσο, πρέπει να κρατήσουν μυστική οποιαδήποτε αναδιάταξη, διαφορετικά μπορεί να σπάσει ξανά.
Όπως είδαμε, ο Ουχούρα εξασφάλισε ότι το μυστικό θα διατηρηθεί ασφαλές. Κάθε μέλος του πληρώματος έπρεπε απλώς να χρησιμοποιήσει την ίδια μυστική παραγγελία και να διασφαλίσει ότι ο κακός Κατενάτι δεν ήξερε τι ήταν. Στην πραγματικότητα, η αλλαγή της σειράς από τον κακό Κατενάτι αύξησε στην πραγματικότητα την πιθανότητα του πληρώματος να τα καταφέρει!
Αυτό έγινε. Ο Ουχούρα ήταν ο πρώτος που οδηγήθηκε στην αίθουσα της ρουλέτας. Πάτησε τρία κουμπιά. Καμία δεν ήταν δική της. Πρέπει να είναι λυπημένη ή χαρούμενη; Κράτησε την ανάσα της και πάτησε την τέταρτη. Είχε βρει το αληθινό της κουμπί!
Ήξερε ότι όλοι επρόκειτο να σωθούν.
Παζλ 5
Ποιο είναι το όριο που πλησιάζει το μέγιστο ποσοστό επιτυχίας καθώς το μέγεθος του προσγειωμένου μέρους αυξάνεται επ' αόριστον; Μπορείτε να εξηγήσετε γιατί αυτή η μέθοδος είναι πολύ πιο αποτελεσματική από το τυχαίο πάτημα κουμπιών;
Η JPayette έγραψε:
Όλα τα παραπάνω γενικεύονται ευθέως σε ένα πλήρωμα 2 ατόμωνn κάθε μέλος επιτρέπεται να πιέζει το πολύ n κουμπιά. Από το Puzzle 2, συμπεραίνουμε ότι οι πιθανότητες επιτυχίας τους είναι
1 − (άθροισμα πάνω k μεταξύ n + 1 και 2n 1 /k).
Το άθροισμα μπορεί να συγκριθεί με το ολοκλήρωμα του 1/x στο διάστημα [n, 2n], που μας επιτρέπει να αποδείξουμε ότι ως n αυξάνεται στο άπειρο, η παραπάνω πιθανότητα μειώνεται για να συγκλίνει σε ένα εκπληκτικό 1 − ln(2) ≈ 30.6%. [Στην πραγματικότητα 30.69% με δύο δεκαδικά ψηφία.]
Ο Rob Corlett πρόσθεσε:
Εάν δεν γνωρίζετε την ενσωμάτωση, μπορείτε να φτάσετε γρήγορα σε μια κατά προσέγγιση απάντηση με υπολογισμό χρησιμοποιώντας ένα υπολογιστικό φύλλο. Έφτασα στο 0.307 μια φορά n έφτασε περίπου το 750 που είναι ακριβές με 3 δεκαδικά ψηφία.
Έχουμε ήδη εξηγήσει παραπάνω γιατί λειτουργεί αυτή η μέθοδος. Όλοι οι βρόχοι μεγαλύτεροι από 1 μοιράζονται πολλά μέλη του πληρώματος. Έτσι, οι επιτυχίες και οι αποτυχίες τους συσχετίζονται σε μεγάλο βαθμό. Είναι μια απεικόνιση της αρχής «Όλοι για έναν και ένας για όλους». Κατευθείαν από το εγχειρίδιο Starfleet!
Ευχαριστούμε όλους τους συντελεστές μας. Η JPayette και ο Rob Corlett υπέβαλαν αμφότεροι αξιόλογες απαντήσεις που έκαναν αυτή τη στήλη λύσης να φαίνεται σχεδόν περιττή. Δυστυχώς, πρέπει να επιμείνω στον κανόνα μας να επιλέγω έναν νικητή ανά στήλη παζλ. Το βραβείο Insights πηγαίνει στο JPayette ως αναγνώριση των συνεισφορών εδώ και στο προηγούμενο παζλ. Συγχαρητήρια! Rob Corlett, οι συνεισφορές σας δεν θα ξεχαστούν.
Ραντεβού τον επόμενο μήνα για νέα Insights!
