Το πρόβλημα των στιγματισμένων μοναχών
Στο σημερινό άρθο θα ασχοληθούμε με ένα από τα πιο γνωστά προβλήματα λογικής το λεγόμενο "πρόβλημα των στιγματισμένων μοναχών". Πρόκειται για ένα ενδιαφέρον πρόβλημα λογικής το οποίο λύνεται με μαθηματική επαγωγή. Το άρθρο δεν απαιτεί προχωρημένες γνώσεις μαθηματικών, απαιτεί όμως σύνθετη μαθηματική σκέψη. Μπορεί επομένως να διαβαστεί από μαθητές Λυκείου και φοιτητές ΑΕΙ, ΤΕΙ, ΕΑΠ.
Συνήθως το πρόβλημα διατυπώνεται ως εξής:
Σε ένα μοναστήρι υπάρχουν 100 μοναχοί που έχουν πάρει όρκο σιωπής. Κάποια μέρα εκδηλώνεται μια ασθένεια στο μοναστήρι, της οποίας το μοναδικό σύμπτωμα είναι ότι εμφανίζεται ένα μπλε στίγμα στο μέτωπο του ασθενούς. Στο μοναστήρι δεν υπάρχουν καθρέφτες και γνωρίζουμε ότι απαγορεύεται οποιαδήποτε μορφή επικοινωνίας μεταξύ των μοναχών. Επιπλέον, είναι γνωστό ότι όλοι οι μοναχοί γνωρίζουν άριστα τους κανόνες της λογικής και γνωρίζουν ότι όλοι οι άλλοι μοναχοί είναι άριστοι χρήστες των κανόνων της λογικής. Κάθε μέρα το μεσημέρι, οι μοναχοί συγκεντρώνονται για το γεύμα, όπου ο ηγούμενος τους ανακοινώνει αν υπάρχουν ασθενείς ανάμεσά τους. Επίσης, τους ανακοινώνει ότι θα πρέπει οι ασθενείς να αποχωρήσουν από το μοναστήρι το βράδυ (όταν καταλάβουν ότι ασθενούν) και να πάνε στην κοντινότερη πόλη για θεραπεία. Διευκρινίζουμε ότι ο ηγούμενος δεν ανακοινώνει τον αριθμό των ασθενών, αναφέρει απλώς ότι υπάρχουν ασθενείς και δεν δίνει καμμιά άλλη πληροφορία για το πόσοι ή ποιοι είναι οι ασθενείς. Επίσης, διευκρινίζουμε ότι η ασθένεια δεν είναι μεταδοτική, ότι ο ηγούμενος δεν έχει την ασθένεια, ότι λέει πάντα την αλήθεια και ότι οι μοναχοί γνωρίζουν ότι ο ηγούμενος λέει πάντα την αλήθεια.
Αν αρρώστησαν 10 μοναχοί, μετά από πόσες μέρες θα φύγουν από το μοναστήρι οι ασθενείς και πώς θα καταλάβουν ότι ασθένησαν;
Το ενδιαφέρον αυτό πρόβλημα λύνεται εύκολα αν εφαρμόσουμε τη μέθοδο της μαθηματικής επαγωγής. Ας δούμε τις πρώτες δύο απλές περιπτώσεις:
Ας υποθέσουμε ότι υπάρχει μόνο ένας ασθενής ο μοναχός Α. Τότε, όταν ο ηγούμενος ανακοινώσει ότι στο μοναστήρι υπάρχουν ασθενείς, ο Α θα κοιτάξει τα μέτωπα των υπόλοιπων μοναχών και θα δει ότι δεν υπάρχει μοναχός με μπλε στίγμα. Θα καταλάβει επομένως ότι αυτός είναι ο ασθενής και θα αναχωρήσει το βράδυ της πρώτης ημέρας.
Ας υποθέσουμε ότι υπάρχουν δύο ασθενείς, ο μοναχός Α και ο μοναχός Β. Όταν ο ηγούμενος ανακοινώσει ότι υπάρχουν ασθενείς στο μοναστήρι, ο Α θα κοιτάξει τα μέτωπα των υπολοίπων και θα δει ότι στίγμα έχει μόνο ο Β. Θα σκεφτεί λοιπόν ως εξής: «Αν εγώ δεν είμαι άρρωστος, τότε ο Β θα αποχωρήσει το βράδυ» (όπως δείξαμε στο πρώτο βήμα της επαγωγής). Ομοίως σκέφτεται και ο Β και έτσι το βράδυ δεν αποχωρεί κανένας. Την δεύτερη μέρα το μεσημέρι, ο ηγούμενος ανακοινώνει και πάλι ότι υπάρχουν ασθενείς. Τότε ο Α καταλαβαίνει ότι αφού ο Β έμεινε στο μοναστήρι, θα πρέπει να είδε κάποιον ακόμη μοναχό με το στίγμα. Αφού βλέπει ότι όλοι οι άλλοι μοναχοί είναι καθαροί, συμπεραίνει ότι ο δεύτερος άρρωστος είναι ο ίδιος. Έτσι αποφασίζει να αποχωρήσει το βράδυ. Όμοια σκέφτεται και ο Β. Επομένως και οι δύο μοναχοί θα αποχωρήσουν το βράδυ της δεύτερης μέρας.
Η διαδικασία συνεχίζεται με τον ίδιο τρόπο και για τους υπόλοιπους ασθενείς. Δηλαδή, αν υποθέσουμε ότι υπάρχουν Ν άρρωστοι μοναχοί τότε θα φύγουν όλοι μαζί το βράδυ της Ν-οστής μέρας (για κάθε τυχαίο φυσικό αριθμό Ν). Για να ολοκληρώσουμε την απόδειξη του παραπάνω ισχυρισμού, αρκεί να εφαρμόσουμε μεθοδικά την επαγωγική διαδικασία:
Είδαμε ότι για Ν=1 και Ν=2 ο ισχυρισμός ισχύει.
Ας υποθέσουμε ότι για Ν=Κ ισχύει ο ισχυρισμός. Δηλαδή, ότι αν υπάρχουν Κ ασθενείς τότε θα φύγουν όλοι μαζί το βράδυ της Κ-οστής μέρας.
Θα αποδείξουμε τότε ότι ο ισχυρισμός αληθεύει και για Κ+1 ασθενείς. Πράγματι, αν υποθέσουμε ότι υπάρχουν Κ+1 ασθενείς, τότε ο καθένας από αυτούς βλέπει Κ μοναχούς με στίγματα. Επομένως, κάθε ένας από τους Κ+1 ασθενείς θα συμπεράνει ότι αν αυτός δεν έχει στίγμα, οι Κ στιγματισμένοι μοναχοί θα φύγουν όλοι μαζί το βράδυ της Κ-οστής μέρας (προηγούμενη υπόθεση). Επομένως, αν δει την Κ+1 μέρα ότι οι μοναχοί δεν έφυγαν, θα καταλάβει ότι υπάρχουν περισσότεροι από Κ στιγματισμένοι μοναχοί. Και αφού αυτός παρατηρεί ακριβώς Κ μοναχούς με στίγματα, θα συμπεράνει ότι και ο ίδιος έχει στίγμα, επομένως θα φύγει το βράδυ της μέρας Κ+1. Όμοια θα πράξουν και οι υπόλοιποι Κ μοναχοί. Δηλαδή και οι Κ+1 στιγματισμένοι μοναχοί θα φύγουν το βράδυ της μέρας Κ+1.
Στο συγκεκριμένο πρόβλημα που δώσαμε, είναι πλέον προφανές ότι και οι 10 μοναχοί θα φύγουν από το μοναστήρι στο τέλος της 10ης μέρας.
Αξίζει να αναφέρουμε ότι εκτός από την διατύπωση με τους μοναχούς που έχουν ασθενήσει, το πρόβλημα αυτό δίνεται και με άλλες παραλλαγές. Μια άλλη γνωστή παραλλαγή είναι και αυτή με τους κατοίκους ενός απομονωμένου νησιού που είναι χωρισμένοι σε δύο ομάδες ανάλογα με το χρώμα των ματιών τους. Υπάρχουν οι κάτοικοι με καστανά μάτια και οι κάτοικοι με γαλανά μάτια. Στο νησί δεν επιτρέπεται καμμιά επικοινωνία (όπως και στο μοναστήρι), ενώ κάθε μεσημέρι, ο πρόεδρος του νησιού αναφέρει ότι όλοι οι κάτοικοι με γαλανά μάτια πρέπει να φύγουν από το νησί...
