:: Nikos Tsirakis :: the weblog ::

homework #2

Έχουμε 100 φυλακισμένους σε ένα κελί. Υπάρχει μόνο ένας τρόπος να γλυτώσουν τη θανατική ποινή. Αυτός είναι το αν καταφέρουν και βρουν μια φόρμουλα για το παρακάτω πρόβλημα.
Γίνεται κάθε φορά μια τυχαία επιλογή ενός ατόμου, από τα 100, το οποίο το βάζουν σε ένα δωμάτιο σκοτεινό και το οποίο έχει μόνο μια λάμπα με ένα διακόπτη. Κάθε φορά δηλαδή ένα άτομο πηγαίνει στο δωμάτιο και το μόνο που μπορεί να κάνει είναι να αλλάξει την κατάσταση του διακόπτη ή να τον αφήσει όπως είναι. Το θέμα μας είναι πως μπορεί τελικά κάποιος (και πότε) από αυτούς τους 100 να καταλάβει πως όλοι τους έχουν περάσει από το δωμάτιο έστω μια φορά. Μόνο έτσι θα σωθούν, διαφορετικά η θανατική ποινή είναι σίγουρη και άμεση. Εννοείτε πως από τη στιγμή που ξεκινάει όλη η διαδικασία δεν ξανασυναντιούνται και η μόνη φορά που μπορούν να συνεννοηθούν κάτι είναι στην αρχή. Οπότε έχουν μόνο έναν διακόπτη και το μυαλό τους να χρησιμοποιήσουν. Τέλος ο διακόπτης αρχικά δεν ξέρουμε σε τι κατάσταση είναι δηλαδή αν η λάμπα είναι ανοιχτή ή κλειστή.
Το ίδιο πρόβλημα μπορεί να τεθεί με Ν άτομα αντί 100 και επίσης με 2 διακόπτες αντί του ενός. Βέβαια ανάλογα την παραλλαγή αλλάζει και ο αλγόριθμος.
Περιμένω πιθανές λύσεις. Είμαι σχεδόν σίγουρος πως το βρήκα. Σίγουρα αν ξέρουμε την αρχική κατάσταση του διακόπτη είναι σχετικά πιο απλό αλλά είναι γενικά πολύ ενδιαφέρον πρόβλημα.