Αποφυλάκιση κρατουμένων

[Λάμπρος Κατσάπας]

Έχουμε κρατούμενους σε μία φυλακή. Οι δεσμοφύλακες τους έχουν προμηθεύσει με ένα αμερόληπτο

κέρμα και μία μηχανή που παράγει τυχαίους αριθμούς στο . Κάθε κρατούμενος βρίσκεται σε διαφορετικό

κελί και οι κρατούμενοι δεν μπορούν να επικοινωνήσουν μεταξύ τους. Οι δεσμοφύλακες αποφασίζουν να παίξουν το

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

Αν όλοι οι κρατούμενοι που θα στρίψουν το νόμισμα φέρουν κορώνα τότε και οι κρατούμενοι θα ελευθερωθούν.

Αν τουλάχιστον ένας κρατούμενος φέρει γράμματα ή κανένας κρατούμενος δεν στρίψει το νόμισμά του τότε όλοι θα

απομείνουν στη φυλακή μέχρι το τέλος της ζωής τους. Οι κρατούμενοι είναι ενημερωμένοι για τον τρόπο διεξαγωγής του

παιχνιδιού. Πως θα πρέπει να παίξουν το παιχνίδι οι κρατούμενοι και ποια θα είναι πιθανότητα να αποφυλακιστούν;

[kkala]

Κατά μια απλοϊκή σκέψη, οι κρατούμενοι πρέπει να αρνηθούν να στρίψουν το κέρμα, όλοι εκτός από τον τελευταίο. Έτσι θα έχουν 50% πιθανότητα να αποφυλακισθούν. Αν στρίψουν το κέρμα π.χ. δύο κρατούμενοι (ή n) η πιθανότητα να ελευθερωθούν είναι 1/4 (ή ).
Τούτο προϋποθέτει ότι οι κατούμενοι γνωρίζουν τη σειρά με την οποία θα στρίψουν το κέρμα, δηλαδή ποιός θα το στρίψει τελευταίος. Αυτή η παραδοχή καλόν είναι να διευκρινισθεί στην άσκηση, καθώς και ο ρόλος της μηχανής που παράγει τυχαίους αριθμούς στο (0,1). Πιθανόν μετά από αυτά η άσκηση να γίνει πιό περίπλοκη, με διαφορετικο αποτέλεσμα. Μπορεί και τώρα κάτι να μην είναι κατανοητό σε μένα.
Πάντως το " Αν.. κανένας κρατούμενος δεν στρίψει το νόμισμά του τότε όλοι θα απομείνουν στη φυλακή" σημαίνει ότι τουλάχιστον ένας κρατούμενος πρέπει να στρίψει το νόμισμά του. Αλλοιώς όλοι θα μείνουν στη φυλακή.

[Λάμπρος Κατσάπας]

Κατά μια απλοϊκή σκέψη, οι κρατούμενοι πρέπει να αρνηθούν να στρίψουν το κέρμα, όλοι εκτός από τον τελευταίο. Έτσι θα έχουν 50% πιθανότητα να αποφυλακισθούν. Αν στρίψουν το κέρμα π.χ. δύο κρατούμενοι (ή n) η πιθανότητα να ελευθερωθούν είναι 1/4 (ή ).
Τούτο προϋποθέτει ότι οι κατούμενοι γνωρίζουν τη σειρά με την οποία θα στρίψουν το κέρμα, δηλαδή ποιός θα το στρίψει τελευταίος. Αυτή η παραδοχή καλόν είναι να διευκρινισθεί στην άσκηση, καθώς και ο ρόλος της μηχανής που παράγει τυχαίους αριθμούς στο (0,1). Πιθανόν μετά από αυτά η άσκηση να γίνει πιό περίπλοκη, με διαφορετικο αποτέλεσμα. Μπορεί και τώρα κάτι να μην είναι κατανοητό σε μένα.
Πάντως το " Αν.. κανένας κρατούμενος δεν στρίψει το νόμισμά του τότε όλοι θα απομείνουν στη φυλακή" σημαίνει ότι τουλάχιστον ένας κρατούμενος πρέπει να στρίψει το νόμισμά του. Αλλοιώς όλοι θα μείνουν στη φυλακή.

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

[kkala]

Έκανα την (απλοϊκή) υπόθεση στο #2 ότι δεσμοφύλακες προχωρούν στα κελλιά των κρατουμένων από την αρχή στο τέλος, ώστε το τελευταίο κελί να αντιστοιχεί στο τελευταίο ζητούμενο στρίψιμο. Διευκρινίστηκε όμως στο #3 ότι αυτό δεν ισχύει, ο κάθε δεσμοφύλακας (μπορούμε να πούμε ότι) μπαίνει τυχαία στο κελί ενός κρατούμενου (ανεξαρτήτως σειρας) και του ζητά να στρίψει το κέρμα.

[Λάμπρος Κατσάπας]

Επαναφορά.