Ο Αναστάσης έχει 128 πανομοιότυπα νομίσματα, εκ των οποίων μόνο ένα είναι φτιαγμένο από αληθινό χρυσό — τα υπόλοιπα είναι πλαστά. Καλεί την Αλίκη στο γραφείο του και την τοποθετεί μπροστά σε δύο πίνακες 8×8, με ένα νόμισμα σε κάθε τετράγωνο.
Ο ίδιος γνωρίζει ποιο είναι το αυθεντικό νόμισμα και μπορεί να επιλέξει πώς θα τοποθετήσει καθένα από τα νομίσματα — με την κορώνα ή με την ουρά προς τα πάνω.
Ενημερώνει την Αλίκη ποιο είναι το χρυσό νόμισμα. Η Αλίκη έχει στη διάθεσή της ένα και μοναδικό εργαλείο: μπορεί να αναποδογυρίσει έως και 4 νομίσματα, αλλά μόνο στην πρώτη σειρά του αριστερού πίνακα. Στη συνέχεια φεύγει από το δωμάτιο.
Μπαίνει ο Μιχαήλ, χωρίς καμία γνώση για τη θέση του χρυσού νομίσματος. Το μόνο που βλέπει είναι η τελική διάταξη των 128 νομισμάτων. Παρ' όλα αυτά, χάρη σε μια ιδιοφυή προσυνεννοημένη στρατηγική, μπορεί πάντα —χωρίς λάθος— να επιλέξει το αυθεντικό νόμισμα.
Πώς γίνεται αυτό;
Το μυστικό κρύβεται στην έντεχνη χρήση της δυαδικής κωδικοποίησης και της πράξης XOR. Η Αλίκη και ο Μιχαήλ έχουν συμφωνήσει πώς να αριθμούν τις 128 θέσεις (π.χ. από 0 έως 127) και να υπολογίζουν το XOR των θέσεων όπου τα νομίσματα δείχνουν κορώνα. Με βάση αυτό το XOR, και με έξυπνες αναστροφές σε συγκεκριμένες θέσεις της πρώτης σειράς, η Αλίκη μπορεί να «κωδικοποιήσει» τη θέση του χρυσού νομίσματος. Ο Μιχαήλ, μετρώντας ξανά το XOR, αποκρυπτογραφεί το σήμα και εντοπίζει με ακρίβεια τη σωστή θέση.
Μια απλή πράξη με τεράστια ισχύ: έως και 128 πληροφορίες μεταδίδονται με μόλις 4 κινήσεις!
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου