Friday 2 February 2018

Δυαδική τράπουλα

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

Ακολουθώντας την επόμενη διαδικασία, ο σκοπός μας είναι να «κλείσουμε» όλα τα φύλλα. Επιλέγουμε ένα οποιοδήποτε ανοιχτό φύλλο και το αναποδογυρίζουμε (το κάνουμε δηλαδή κλειστό). Είμαστε όμως υποχρεωμένοι να κάνουμε το ίδιο και στο αμέσως επόμενο προς τα δεξιά φύλλο. Αν δηλαδή είναι ανοιχτό τότε γίνεται κλειστό και αντιστρόφως. Συνεχίζουμε την παραπάνω διαδικασία όσες φορές χρειαστεί και κάθε φορά έχουμε την ελευθερία να επιλέξουμε οποιοδήποτε ανοιχτό φύλλο θέλουμε. 

Για παράδειγμα έστω ότι κάποια στιγμή, σε ένα τμήμα της τράπουλας εμφανίζεται η παρακάτω εικόνα.


Εικόνα 1.

Επιλέγουμε στην τύχη το 3 Μπαστούνι, το αναποδογυρίζουμε και το ίδιο κάνουμε με το διπλανό του κλειστό φύλλο, το οποίο ανοίγει και είναι το 6 Καρό (βλ. Εικόνα 2). 


Εικόνα 2.

Συνεχίζοντας, επιλέγουμε ξανά στην τύχη το 9 Καρό και κάνουμε ότι και προηγουμένως σε αυτό και στο αμέσως διπλανό του από τα δεξιά φύλλο (βλ. Εικόνα 3).


Εικόνα 3.

Το ερώτημα είναι αν είναι βέβαιο ότι σε πεπερασμένου πλήθους βήματα εφαρμογής του παραπάνω αλγορίθμου η διαδικασία θα ολοκληρωθεί με όλα τα φύλλα κλειστά (βλ. Εικόνα 4), ανεξάρτητα από την επιλογή φύλλου σε κάθε βήμα. 


Εικόνα 4.

Λύση: Ο γρίφος αυτός εμφανίζεται στην ταινία \( x + y \) [1], όπου παρουσιάζεται μια εξαιρετικά κομψή και απλή λύση η οποία επιστρατεύει το δυαδικό σύστημα αρίθμησης και έχει ως εξής: Αν αντιστοιχίσουμε καθένα από τα κλειστά φύλλα στο \( 0 \) και καθένα από τα ανοιχτά στο \( 1 \), τότε η ακολουθία των φύλλων που είναι αραδιασμένα μπροστά μας αντιστοιχεί σε ένα δυαδικό αριθμό του οποίου τα ψηφία παράγονται από τα φύλλα από τα αριστερά προς τα δεξιά. Για παράδειγμα, στην ακολουθία της Εικόνας 1 αντιστοιχεί ο δυαδικός αριθμός \( 01101010 \). Όταν επιλέγουμε ένα ανοικτό φύλλο είναι σαν να επιλέγουμε ένα \( 1 \) και να το μετατρέπουμε σε \( 0 \). Ταυτόχρονα όμως αλλάζουμε και το ψηφίο που βρίσκεται αμέσως δεξιά. Αν είναι \( 0 \), το μετατρέπουμε σε \( 1 \) και αντιστρόφως. Έτσι, στην νέα ακολουθία (βλ. Εικόνα 2) αντιστοιχεί ο δυαδικός αριθμός \( 01100110 \). Παρατηρούμε ότι ανεξάρτητα από το τι είναι το δεξί ψηφίο, ο νέος δυαδικός αριθμός που παράγεται σε κάθε βήμα (ζεύγος ενεργειών), είναι μικρότερος του προηγούμενου (π.χ., \( 01100110 < 01101010 \)) καθώς το αριστερό φύλλο, το οποίο πάντα μικραίνει, αντιστοιχεί σε ψηφίο μεγαλύτερης αξίας. Έτσι, συνεχίζοντας την παραπάνω διαδικασία κατασκευάζουμε ουσιαστικά μια φθίνουσα ακολουθία θετικών ακεραίων δυαδικών αριθμών η οποία αναγκαστικά καταλήγει στο \( 0 \), που αντιστοιχεί σε όλα τα φύλλα κλειστά. Η απάντηση λοιπόν στο αρχικό ερώτημα, αν η διαδικασία είναι τερματιζόμενη σε πεπερασμένου πλήθους βήματα είναι καταφατική.

[1] https://en.wikipedia.org/wiki/X%2BY

1 comment:

  1. Η μαγεία του δυαδικού συστήματος! (άτιμα χέρια)

    ReplyDelete