Πρόβλημα σχετικά με τους κρατουμένους και τα καπέλα, το χρώμα των οποίων πρέπει να καθοριστεί

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

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

Ας δούμε το παράδειγμα από την παραπάνω εικόνα. Ο ψηλότερος κρατούμενος # 1 βλέπει τρία μαύρα καπάκια μπροστά. Μιλάει «μαύρα» δυνατά. Αυτό δίνει σε όλους τους άλλους πληροφορίες ότι υπάρχει ένας περίεργος αριθμός μαύρων κεφαλαίων μπροστά. Ο πρώτος κρατούμενος έκανε ένα λάθος με το χρώμα του καπακιού του, αλλά αυτό είναι εντάξει: όταν του επιτρέπεται να απαντήσει λανθασμένα.

Ο φυλακισμένος # 2 βλέπει έναν περίεργο αριθμό μαύρων καπακιών μπροστά της. Συνειδητοποιεί ότι είναι λευκή και απαντά σωστά. Ο φυλακισμένος # 3 βλέπει έναν ομοιόμορφο αριθμό μαύρων καπακιών και μαντεύει ότι φοράει ένα μαύρο καπάκι που είδαν οι δύο πρώτοι αιχμάλωτοι.

Η αιχμάλωτη αρ. 4 ακούει την απάντηση και συνειδητοποιεί ότι θα έπρεπε να ψάξει για έναν ομοιόμορφο αριθμό μαύρων καπακιών, επειδή υπήρχε ένα μαύρο πίσω από την πλάτη της, αλλά βλέπει μόνο ένα μπροστά και καταλήγει στο συμπέρασμα ότι το καπάκι της είναι μαύρο. Οι φυλακισμένοι Νο. 5-9 αναζητούν έναν περίεργο αριθμό μαύρων καλυμμάτων, τα οποία μόλις βλέπουν, συνειδητοποιώντας ότι φορούν λευκά καπάκια. Η σειρά έρχεται στον δέκατο φυλακισμένο. Εάν ο φυλακισμένος # 9 είδε έναν περίεργο αριθμό μαύρων καπακιών, αυτό σημαίνει μόνο ένα πράγμα - ο φυλακισμένος # 10 έχει μαύρο καπάκι.

Έτσι λειτουργεί αυτός ο αλγόριθμος για οποιοδήποτε σύνολο hubcaps. Για τον πρώτο συμμετέχοντα, η πιθανότητα λανθασμένης απάντησης είναι 50%, αλλά οι πληροφορίες σχετικά με την ομοιόμορφη ισοτιμία, τις οποίες θα δώσει, θα επιτρέψουν στους υπόλοιπους αιχμάλωτους να μαντέψουν το χρώμα του καπακιού τους.

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

Αυτό το παζλ είναι μετάφραση ενός βίντεο TED-Ed.