"Υπάρχουν 10 είδη ανθρώπων. Αυτοί που καταλαβαίνουν το δυαδικό σύστημα, κι αυτοί που δεν το καταλαβαίνουν"
Prof. Mach Xor
Ο καθηγητής $Χ$ δοκιμάζει τις ικανότητες των μαθητών του, Βαγγέλη και Γιάννη. Βάζει στο τραπέζι μια συνηθισμένη σκακιέρα $(8 \times 8)$, και τους λέει: Ο Γιάννης θα πάει στο διπλανό δωμάτιο. Ο Βαγγέλης θα μείνει εδώ μαζί μου. Θα βάλω σε κάποια τετραγωνάκια (όσα και όποια θέλω) από ένα νταμάκι. Μετά θα επιλέξω ένα τετραγωνάκι (όποιο θέλω! Mε νταμάκι ή αδειανό) και θα το δείξω στον Βαγγέλη.
O Βαγγέλης θα αλλάξει την κατάσταση σε ένα και μόνο τετραγωνάκι , δηλαδή μπορεί να προσθέσει ένα νταμάκι σε κάποιο άδειο τετράγωνο, ή να αφαιρέσει ένα νταμάκι από κάποιο γεμάτο. Μετά ,θα έρθει στο δωμάτιο ο Γιάννης και πρέπει να βρει το τετράγωνο που επέλεξα! Έχετε το δικαίωμα να συναποφασίσετε μια στρατηγική, αλλά εννοείται πως μόλις αρχίσει το τεστ,καμία άλλη συνεννόηση μεταξύ σας δεν επιτρέπεται! Ο Βαγγέλης αφαιρεί ή προσθέτει ένα νταμάκι ,και ο Γιάννης έρχεται μέσα και πρέπει να βρει το τετράγωνο που διάλεξα. Αν τα καταφέρετε ,θα περάσετε το μάθημά μου με "Άριστα".
Τι λέτε; Υπάρχει τρόπος να τα καταφέρουν ο $Β$ και ο $Γ$ ,και να περάσουν με άριστα το μάθημα του $Χ$; ή μόνο "μάγοι" μπορούν να τα καταφέρουν;
Το δύσκολο αυτό πρόβλημα είναι πολύ ενδιαφέρον και έχει επεκτάσεις και εφαρμογές εξίσου ενδιαφέρουσες.
ΑπάντησηΔιαγραφήΌπως σε όλα τα θέματα που δεν μπορεί ίσως κάποιος να τα αντιμετωπίσει "ευθέως" ή που δεν είναι σαφές "ποια ακριβώς εργαλεία" απαιτούνται , βοηθάει ίσως μια προσπάθεια απλοποίησης ή "μετασχηματισμού" ...Το καλό διάβασμα της εκφώνησης, επίσης βοηθάει! :-)
Είμαι πολύ περίεργος να μάθω την απάντηση, αν υπάρχει βέβαια...
ΑπάντησηΔιαγραφήΛες να μην υπάρχει Φώτη; Eυτυχώς, έχω ακόμη σώας τας φρένας (νομιζω δηλαδή..) ώστε να βάζω θέματα που έχουν απάντηση.
ΔιαγραφήΚαι η περιέργεια ικανοποιείται για όποιον προσπαθήσει. Αρχή του χώρου. Όποιος περιμένει έτοιμη την απάντηση, μένει με την απορία. :-)
Αυτό το πρόβλημα δεν μπορώ να το λύσω, μου φαίνεται υπερβατικό. Οπότε περιμένω με ενδιαφέρον τη δημοσίευση της λύσης...
ΔιαγραφήΔιευκρινίζω πως υπάρχει τρόπος ΠΑΝΤΑ, με 1 κίνηση του Βαγγέλη (προσθήκη σε άδειο τετρ. ή αφαίρεση από γεμάτο) ο Γιάννης να βρίσκει το τετράγωνο του X.
ΑπάντησηΔιαγραφήΚαι αυτό ισχύει για οποιοδήποτε μέγεθος ή μορφή της σκακιέρας; Π.χ. αν είναι 6x6 ή 10x8, τότε το πρόβλημα έχει λύση;
ΑπάντησηΔιαγραφήΦώτη, αυτό πρέπει να διερευνηθεί...
ΑπάντησηΔιαγραφήΠάντως, για τα 64 τετραγωνάκια έχει.
Σε οποιαδήποτε διάταξη της σκακιέρας, καθένα από τα 64 τετράγωνα έχει μία από δύο δυνατότητες, γεμάτο (Γ) ή άδειο (Α) από νταμάκι. Ο καθηγητής παραδίδει στο Βαγγέλη μια συγκεκριμένη διάταξη και του ανακοινώνει ένα τετράγωνο, έστω το Τ.
ΑπάντησηΔιαγραφήΟ Βαγγέλης αντιστρέφει νοερά την κατάσταση του Τ (Α->Γ ή Γ->Α) και μετράει:
1. Πόσα τετράγωνα των στηλών 1,2,3 και 4 συνολικά είναι Γ. Αν ο αριθμός είναι ζυγός, θα αλλάξει (όχι ακόμα) τετράγωνο από τις στήλες 1 ή 2 ή 3 ή 4 και αν ο αριθμός είναι μονός, από τις στήλες 5 ή 6 ή 7 ή 8.
2. Πόσα τετράγωνα των στηλών 1,2,5 και 6 συνολικά είναι Γ. Αν ο αριθμός είναι ζυγός, θα αλλάξει (όχι ακόμα) τετράγωνο από τις στήλες 1 ή 2 ή 5 ή 6 και αν ο αριθμός είναι μονός, από τις στήλες 3 ή 4 ή 7 ή 8.
3. Πόσα τετράγωνα των στηλών 1,3,5 και 7 συνολικά είναι Γ. Αν ο αριθμός είναι ζυγός, θα αλλάξει (όχι ακόμα) τετράγωνο από τις στήλες 1 ή 3 ή 5 ή 7 και αν ο αριθμός είναι μονός, από τις στήλες 2 ή 4 ή 6 ή 8.
Έτσι, ο Βαγγέλης καταλήγει μονοσήμαντα στη στήλη, στην οποία θα αλλάξει τετράγωνο (όχι όμως πριν καταλήξει μονοσήμαντα και στη γραμμή).
Με την ίδια ακριβώς διαδικασία, δουλεύοντας όμως με γραμμές αντί για στήλες και πάντα αντιστρέφοντας νοερά την κατάσταση του Τ, ο Βαγγέλης καταλήγει μονοσήμαντα και στη γραμμή του τετραγώνου που θα αλλάξει. Αλλάζει τώρα (επί τέλους) την κατάσταση του τετραγώνου στο οποίο κατέληξε μονοσήμαντα.
Έρχεται τώρα ο Γιάννης και εφαρμόζει την ίδια διαδικασία των 3+3 βημάτων, όπως περιγράφεται παραπάνω για το Βαγγέλη, με μόνη τη διαφορά ότι ο Γιάννης δεν αντιστρέφει νοερά την κατάσταση κάποιου τετραγώνου και ότι σκοπός του είναι ο μονοσήμαντος εντοπισμός του τετραγώνου Τ. Με την ολοκλήρωση της διαδικασίας, νομίζω ότι τα έχει καταφέρει.
Τα μαθηματικά που κρύβονται πίσω από την πιο πάνω περιγραφή δεν είναι ιδιαιτέρως απλά: συμμετρίες, θεωρία συνόλων, λογικοί τελεστές, δυαδική ανάλυση κ.ά. Φαντάζομαι ότι ο αγαπητός Γιώργος ή και άλλοι φίλοι σχολιαστές, θα έχουν αρκετά να πουν για όλα αυτά, όπως πιθανόν και κάποιες παρατηρήσεις / βελτιώσεις για τη ίδια την (πολύ αδρή) παραπάνω περιγραφή.
Θα δώσω μερικές διευκρινίσεις, για να εξηγήσω πώς και γιατί λειτουργεί η στρατηγική που περιέγραψα στο προηγούμενο σχόλιό μου (έτσι βέβαια κερδίζουμε κάτι σε κατανόηση, αλλά χάνεται και αρκετή από τη μαγεία :-)).
ΑπάντησηΔιαγραφήTο πρόβλημα, αν το δούμε σε δυαδική βάση, έχει 6 διαστάσεις (2^6=64). Κάθε τετράγωνο ορίζεται από 6 συντεταγμένες 0 ή 1, εξ ου και τα 6 βήματα κάθε μαθητή με χρήση 0 ή 1 mod2 (ζυγά ή μονά) για να καταλήξει σε ένα μοναδικό τετράγωνο, αυτό που θα αλλάξει ο Βαγγέλης, το τετράγωνο Τ του καθηγητή ο Γιάννης.
Αν αναλύσει κανείς το πρόβλημα σε 2 διαστάσεις (σκακιέρα επίπεδη 2Χ2) ή σε 3 διαστάσεις (σκακιέρα -φανταστική- κυβική 2Χ2Χ2), καταλήγει σχετικά εύκολα στη στρατηγική σε 2 ή 3 βήματα αντιστοίχως.
Π.χ. σε σκακιέρα 2Χ2 αρκούν δύο ανεξάρτητες συντεταγμένες (0 ή 1) για να οριστεί ένα τετράγωνο. Ας πούμε ότι η κωδικοποίηση της διαδικασίας εντοπισμού τού Τ που συμφωνούν οι παίκτες να ακολουθήσει ο Γιάννης είναι η εξής:
Αν στην πρώτη στήλη ο αριθμός των τετραγώνων Γ είναι ζυγός (και τα δύο Γ ή κανένα Γ), τότε το Τ βρίσκεται στην πρώτη στήλη, ενώ αν είναι μονός (το ένα Γ και το άλλο Α) το Τ βρίσκεται στη δεύτερη στήλη.
Αν στην πρώτη γραμμή ο αριθμός των τετραγώνων Γ είναι ζυγός (και τα δύο Γ ή κανένα Γ), τότε το Τ βρίσκεται στην πρώτη γραμμή, ενώ αν είναι μονός (το ένα Γ και το άλλο Α) το Τ βρίσκεται στη δεύτερη γραμμή.
Ο Βαγγέλης τώρα, που παραλαμβάνει από τον καθηγητή μια συγκεκριμένη διάταξη και γνωρίζει τις συντεταγμένες του Τ, δεν έχει παρά να ελέγξει αν η διάταξη που παρέλαβε κωδικοποιεί σωστά τη θέση του Τ. Ελέγχει δηλαδή αν στην πρώτη στήλη
ο αριθμός των τετραγώνων Γ είναι ζυγός και αν το Τ βρίσκεται σε αυτή τη στήλη. Αν συμβαίνουν και τα δύο ή κανένα από τα δύο, τότε θα αφήσει την πρώτη στήλη απείραχτη και θα κάνει την κίνησή του στη δεύτερη στήλη. Αν συμβαίνει το ένα μόνο από τα δύο, τότε θα πρέπει να κάνει την κίνησή του στην πρώτη στήλη.
Με τον ίδιο ακριβώς τρόπο, αλλά ελέγχοντας την πρώτη γραμμή σε συνδυασμό με τη γραμμή του Τ, καταλήγει και στη γραμμή όπου θα κάνει την κίνησή του και έτσι καταλήγει στο τετράγωνο (γραμμή και στήλη), του οποίου θα αλλάξει την κατάσταση.
Τώρα πλέον ο Γιάννης έχει πλήρως κωδικοποιημένη, σύμφωνα με τη συμφωνημένη στρατηγική, την πληροφορία για τις ακριβείς συντεταγμένες του Τ και μπορεί να το εντοπίσει μονοσήμαντα.
Η ίδια στρατηγική μπορεί να λειτουργήσει και σε περισσότερες δυαδικές διαστάσεις, μόνο που εκεί αυξάνεται ανάλογα και ο αριθμός των απαιτούμενων συντεταγμένων που προσδιορίζουν τα τετράγωνα. Στη σκακιέρα των 8Χ8=64=2^6 τετραγώνων χρειαζόμαστε 6 δυαδικές συντεταγμένες, άρα 6 ανεξάρτητα βήματα για τον μονοσήμαντο καθορισμό ενός τετραγώνου.
Το λεπτό σημείο εδώ είναι το πώς θα μεταφράσουμε τις 6 αυτές ανεξάρτητες συντεταγμένες ενός δυαδικού χώρου 6 διαστάσεων στα σωστά 6 βήματα, πάνω στην κανονική σκακιέρα 8Χ8. Αυτό ακριβώς κάνει η διαδικασία των 3+3 βημάτων που ακολουθεί κάθε μαθητής.
Ευχαριστώ πολύ Θανάση(papadim) για τα ωραία σχόλια και τη λύση του θέματος! Eπίτρεψέ μου να κάνω μια ανάλυση:
ΑπάντησηΔιαγραφήΌπως ωραία αναλύεις στο δεύτερο σχόλιό σου , το πρόβλημα έχει λύση για κάθε σύνολο τετραγώνων που είναι δύναμη του $2$.
$2, 4, 8,...,64,...$ H "σκακιέρα" δεν έχει σημασία, αρκεί να αποδωθεί μονοσήμαντα κάποιος αύξων αριθμός στα τετράγωνα. O λόγος ,ουσιαστικά έχει αναφερθεί ήδη από σένα, και έχει να κάνει με την δυαδικότητα του θέματος.
Aλλά, επειδή είναι ένα απαιτητικό θέμα, ας πάρω τα πράγματα απ'την αρχή.
Διάβασα προσεκτικά τα σχόλια σου και αν έχω κατανοήσει καλά τη λύση σου (που νομίζω πως έχω) η πρότασή σου -που σίγουρα δουλεύει!- είναι ισοδύναμη με το εξής σκεπτικό στο δεκαδικό σύστημα:
Ο Β. αντιστοιχεί τους αριθμούς απο $0,1,..,63$ στα 64 τετράγωνα . Έστω $Χ$ το τετράγωνο που επιλέγει ο Χ.
Ο Β. προσθέτει τους αριθμούς των τετρ. που έχουν νταμάκι και αφαιρεί απ'αυτό το σύνολο το σύνολο των αριθμών που αντιστοιχούν σε άδεια τετράγωνα. Το αποτέλεσμα αυτής της αφαίρεσης είναι πάντα ένας άρτιος αριθμός (αρνητικός ή θετικός)
Αν ο αριθμός είναι αρνητικός , τού προσθέτουμε όσα πολλαπλάσια του $2n$ δηλαδή στην περίπτωσή μας του $128$ απαιτούνται ,ώστε να γίνει θετικός.
Κατόπιν διαιρούμε διά του $128$.
Το ήμιση(1/2) του υπολοίπου αυτής της διαίρεσης ,το αποκαλούμε έστω $y$ . Δηλαδή $y=(1/2)*υ$
Η αποστολή του Β. τώρα, είναι να αλλάξει έτσι ώστε ο νέος σχηματισμός να δίνει μια τιμή y =Χ.
Αν Χ>τρέχοντος y, τότε y(νεο)=y+64. Aφαιρώντας απ'αυτό το X, έχουμε το κελί στο οποίο ο Β .πρέπει να "αντιστρέψει" την τιμή.
Οπότε ,όταν ο Γ. κάνει ακριβώς τον ίδιο υπολογισμό, βρίσκει το y(νέο) που ταυτίζεται πλέον με το Χ.
Δεν ξέρω αν τα παραπάνω είναι πιο εποπτικά, αλλά ο θεωρητικός λόγος-εξήγηση , με βάση το δυαδικό σύστημα πλέον είναι ο εξής:
Στα logical gates (λογικές πύλες/τελεστές) υπάρχει το όρισμα
Χοr. (εξού και το hint της εκφώνησης με τον καθηγητή Mach Xor ..που σημαίνει σε κάποια ινδοευρωπαϊκή γλώσσα "Κάνε Xor!" :-) )
O τελεστής Xor ("exlusive or") ,που συμβολίζεται επίσης με $\oplus$
είναι ο τελεστής που δίνει μια τιμή "αληθές" σε μια διαδική περίπτωση, όταν δηλαδή μεταξύ δύο καταστάσεων ,αληθεύει είτε η μία, είτε η άλλη, όχι όμως και οι δύο.
Για παράδειγμα, η πρόταση "Το καλοκαίρι θα πάω ταξίδι είτε στην Ισπανία, είτε στη Γερμανία" αληθεύει αν πας ταξίδι σε κάποια απο τις δύο χώρες, αλλά είναι ψευδής αν δεν πάς σε καμία ή αν πας ΚΑΙ στις δύο.
Σε ένα δυαδικό string , σε κάποιον αριθμό δηλαδή binary το
$1Xor1=0$ και το $1xor0$=1 (1αληθές,0 ψευδές)
Δείτε και αυτά τα λινκ:
http://www.codeproject.com/Articles/544990/Understand-how-bitwise-operators-work-Csharp-and-V#exclusiveor
http://en.wikipedia.org/wiki/Exclusive_or
(συνεχίζεται...)
Έτσι ,αν:
ΑπάντησηΔιαγραφή$A xor B xor Γ xor...X= Y$ τότε ισχύει:
$A xor B xor Γ xor Y=X$.
Aυτό είναι ένα προφανές θεωρημα που προκύπτειν από τις εξορισμού ταυτότητες: $X xor X=0$ και $X xor 0=X$
Στο θέμα μας ,η εφαρμογή των παραπάνω, που δίνει και τον αλγόριθμο λύσης , μεταφράζεται ως εξής:
1. Aριθμούμε τα τετράγωνα 0-63 ,αντιστοιχίζοντάς τους στο καθένα έναν δυαδικό αριθμό από το $000000$ έως το $111111$
2. Mετά ο Β. γράφει όλα τα τετράγωνα που έχουν νταμάκι, το ένα κάτω από το άλλο. (o καθένας είναι ένας δυαδικός αριθμός με 6 ψηφία, π.χ 011101= to τετρ. 29)
3. Προσθέτει και τον δυαδικό αριθμό που αντιστοιχεί στο τετράγωνο X.
4. Τα Xor -ίζουμε όλα! (o τελεστής Xor είναι αντιμεταθετικός και επιμεριστικός. Xor τα 2 πρώτα, μετά το αποτέλεσμα με τον 3ο αριθμό, κ.λ.π.)
5.Ουσιαστικά, αυτό που κάνουμε είναι αυτό που έγραψα πιο πάνω: A xor B xor Γ...xor X. Θα πάρουμε έναν δυαδικό αριθμό έστω Y .
6. Αντιστρέφουμε τον Υ (δηλαδή αφαιρούμε νταμάκι αν ο Υ είναι με νταμάκι, ή προσθέτουμε νταμάκι αν ο Υ ήταν αδειος)
7. Τωρα έρχεται ο Γιάννης. Γραφει όλους τους αριθμούς με νταμάκι και τους κάνει Xor. Oυσιαστικά, αυτό που κάνει είναι να λύνει την:
A xor B xor Γ..xor Y. Oπότε αυτό που βρίσκει είναι το Χ. Το ζητούμενο τετράγωνο! Mαγεία!
Για να γίνει πλήρως κατανοητό, έχω προσθέσει ένα πρόχειρο σκίτσο στην ανάρτηση για την περιπτωση 4 τετραγώνων (2Χ2)
(συνεχίζεται...)
Στην πρώτη περίπτωση (αριστρό σχήμα) ο καθηγητής Χ ,έχει βάλει νατμάκια στα τετράγωνα 1 και 2, και έχει διαλέξει το τετράγωνο 3 (με Χ).
ΑπάντησηΔιαγραφήMετατρέπουμε τα Τετράγωνα στο δυαδικό:
0---> 000
1---> 001
2---> 010
3---> 011
Νταμάκι έχουν τα:
001
010
To 001 xor 010 είναι: 011 (θυμίζω πως 1xor 0 και 0 xor 1 =1 και 0 xor 0 ή 1 xor 1 δίνουν 0)
011 xor X δίνει:
011 xor
011
=000=τετράγωνο 0.
Αντιστρέφουμε το τετρ.0. Αφού είναι άδειο,του βάζουμε ένα νταμάκι.
Ερχεται ο Γιάννης λοιπόν και βλέπει νταμάκια στα τετραγωνα:
0,1, και 2.
Κάνει το xor των τριών τετραγώνων
000 xor
001 xor
010=
011 = τετράγωνο 3 = Χ Kαλό ε; :-)
Oποιος θέλει ,για εξάσκηση (ένα εξαιρετικό θέμα για να καταπλήξετε φίλους και γνωστούς!) ας κάνει το δεύτερο ταμπλό.
Ας δώσω κι ένα παράδειγμα εφαρμογής στη σκακιέρα της εκφώνησης.
ΑπάντησηΔιαγραφήΈστω πως ο $Χ$ βάζει νταμάκι στα τετραγωνα 63 και 29, αφήνει όλα τα υπόλοιπα κενά ,και διαλέγει το τετράγωνο Χ= 12
63 (σε βάση 2)=111111
29(2)= 011101
12 (2)= 001100
111111 xor 011101 =100010
100010 xor 001100=101110 = 46 (τετράγωνο 46)
Βάζουμε νταμάκι στο 46.
Έρχεται ο Τζώνυ μπη γκουντ και βλέπει
νταμάκια: 63, 29 και 46. Ήτοι:
111111
011101
101110
xoring..= 001100= 12 :-)
Πολύ καλό! Το πρόβλημα είναι ότι για να πραγματοποιηθεί χρειάζονται 3 και όχι 2 άτομα, εκ των οποίων τουλάχιστον οι δύο πρέπει να γνωρίζουν το δυαδικό σύστημα και τη συνάρτηση xor.
ΑπάντησηΔιαγραφήΌχι. Χρειάζεται ένας ανυποψίαστος "πελάτης" στο ρόλο του καθηγητή $Χ$ και ο οποίος θα μείνει άναυδος όταν θα του βρίσκει ο "Γιάννης" το τετράγωνο. :-)
ΔιαγραφήE, τι δυαδικό σύστημα; Kάντο σε 4 τετραγωνάκια (000, 001, 010, 011) To $Χor$ $1\oplus 1=0$ $0\oplus0=0 $ και $ 0\oplus1=1$ δεν είναι δα και τόσο πολύπλοκο.
Κανόνας: ίδιο ψηφίο πάνω-κάτω--->το Xor δινει $0$
διαφορετικό ψηφίο πάνω-κάτω---> το Xor δίνει $1$
Eναλλακτικά Φώτη, υπάρχει και η "δεκαδική" μέθοδος ,που περιγράφω στο σχόλιο 3.50, όπου δουλεύεις με δεκαδικούς αριθμούς και μεταφορές κρατουμένων στις προσθέσεις ,και υπόλοιπα, αλλά μάλλον είναι πιο πολύπλοκο από τη μετατροπή σε binary και μόνο άσσους και μηδενικά ,που Xor-ίζονται εύκολα.
ΔιαγραφήΚαι ο "Βαγγέλης" ποιος θα είναι;
ΔιαγραφήO Bενιζέλος.
ΔιαγραφήΤελικά δεν χρειάζεται να ξέρουν τα 2 από τα 3 άτομα που απαιτούνται για την πραγματοποίηση του κόλπου το δυαδικό σύστημα και τη συνάρτηση xor. Μόλις κατασκεύασα με τη βοήθεια προγράμματος σε γλώσσα Pascal μια 16x16 συμμετρική μήτρα ως προς τα στοιχεία της κύριας διαγωνίου, η οποία παρέχει για κάθε συνδυασμό τετραγώνων αριθμημένων από το 1 έως το 16, την τιμή της xor σε δεκαδική μορφή (πάλι από το 1 έως το 16). Θα δώσω το πινακάκι σε έναν συνεργό μου και θα έχω και εγώ ένα δικό μου. Το θύμα δεν θα καταλάβει τίποτα...
ΔιαγραφήΜε κάθε επιφύλαξη, κάτι σαν ερώτηση με άποψη!
ΑπάντησηΔιαγραφήΜε την ίδια αρίθμηση τετραγώνων 0-63
Αν ο $X$ βάλει νταμάκια στα τετράγωνα 12(2)=001100,
29(2)=011101 και 63(2)=111111,
και διαλέξει το τετράγωνο Χ=12 τότε φυσικά
1100 xor 11101 xor 111111 = 101110 =46 τετρ.
Και αφού στο 46 δεν υπάρχει νταμάκι τότε ο Βαγγέλης για να οδηγήσει τον Γιάννη στο 12 πρέπει και να προσθέσει νταμάκι στο 46 και να αφαιρέσει το νταμάκι τουαπό το 12 ώστε
11101 xor 10110 xor 111111 = 1100 (=12),
άρα δεν αρκεί σε κάθε περίπτωση το
“O Βαγγέλης θα αλλάξει την κατάσταση σε ένα και μόνο τετραγωνάκι” ?
Μου διαφεύγει κάτι?
Γεια σου Ευθύμιε!
ΔιαγραφήΠρόσεξε πώς στο αρχικό Xor-ισμα πρέπει να μπεί σαν τέταρτος άριθμος και το επιλεγμένο τετράγωνο $Χ$, στο παράδειγμά σου το $12$ δηλαδή πρέπει να μπει 2 φορές.
Οπότε το:
001100
011101
111111
001100
δίνουν μετά από Χor =100010 που είναι 34
Aντιστρέφουμε το 34, δηλαδή βάζουμε νταμάκι και ο Γ. βλέπει νταμάκια στα: 12,29,63,34
Aν κάνεις το Xor ,βγαίνει 12 (001100)
Γειά σου Γεώργιε!
ΑπάντησηΔιαγραφήΣωστά και ευχαριστώ και αν δεν απαντούσες τόσο γρήγορα θα απαντούσα μόνος μου στον εαυτό μου, το βρήκα μετέπειτα, δυστυχώς...
Υ.Γ Φυσικά και το ότι απάντησες τόσο γρήγορα με τιμάει!
ΔιαγραφήΚαταρχάς, πρωθύστερα, καταπληκτικό πρόβλημα και ασχολήθηκα πάρα πολύ με αυτό. Σκακιέρες 3*3, 4*4, 8*8 και με δυαδικό, τριαδικό,
ΑπάντησηΔιαγραφήτετραδικό και οκταδικό σύστημα και είχα λύση σε κάθε περίπτωση, πλην μιας, σπάνιας μεν αλλά υπαρκτής
Όταν το άθροισμα XOR δίνει τον άγνωστο Χ.
Χρησιμοποιώντας τους ίδιους αριθμούς, νταμάκια στα
τετράγωνα 12, 29, 34, 63 (αντιστοιχώ με το συγκεκριμένο)
οπότε Σxor=12.
Aδιέξοδο για μένα καθώς αρίθμησα τα τετράγωνα σαν 1 έως 64
και στο δυαδικό από 1 έως 1000000(64) και βλέπω ότι το
“μυστικό” είναι το μηδενικό τετράγωνο (1ο για μένα), έτσι
αν εκεί έχει νταμάκι το αφαιρούμε(-0) και αν δεν έχει
προσθέτουμε (+0) οπότε ούτε γάτα ούτε ζημιά!
Καταπληκτικό όπως και να έχει και ιδιαίτερα εξασκητικό
για μένα!
Αυτός δεν είναι ο λόγος που ξεκινάς την αρίθμηση από
το 0, ενώ από το 1-64 δεν έχουμε λύση στην περίπτωση
που Σxor=Χ ?
Και τελικά, είτε έχει νταμάκι το Χ είτε δεν έχει αν Σxor=Χ
“παίζουμε” με το 0 αναλόγως.?
Nαι, έτσι είναι Ευθύμη. Για 9 τετράγωνα όμως (3 Χ 3) δεν νομίζω πως υπάρχει λύση πάντα. To πλήθος πρέπει να είναι δύναμη του 2 (λόγω του ότι οι διαδικοί αριθμοί για να αντιστοιχίζονται μονοσήμαντα στην κατάσταση "νταμάκι-όχι νταμάκι" ή ας πουμε "κορώνα -γράμματα" σε μια παραλλαγή ταμπλώ γεμάτου νομίσματα είναι πάντα της μορφής:
Διαγραφήαν*2^ν +*α(ν-1)*2^(ν-1)+...+α2*2+α1*2^0)
Με {a1,a2,...,an} = {0,1) εννοούσα, φυσικά.
ΔιαγραφήΓιώργη ευχαριστώ και μπράβο σου για την εμπεριστατωμένη ανάλυση και λύση, με μια απλούστατη τελικά στην εκτέλεσή της στρατηγική των μαθητών! Αρκεί βέβαια να μη συμβεί αυτό που φοβάται ο Φώτης, να μην έχουν μάθει δηλαδή ακόμα τα παιδιά το 0 και το 1 :-)
ΑπάντησηΔιαγραφήΝα συμπληρώσω μόνο, αν επιτρέπεις, κάτι σχετικά με τον τελεστή xor, για όσους τυχόν δεν είναι εξοικειωμένοι με αυτόν. Ο συγκεκριμένος τελεστής λειτουργεί όπως ακριβώς και η άθροιση ανάμεσα στους όρους που συνδέει, με το αποτέλεσμα να εκφράζεται σε 0 ή 1 mod2. Π.χ 1+0=1, 0+1=1, 0+0=0, 1+1=0, 1+1+1=1, 1+0+1+0=0 κ.ο.κ. Με άλλα λόγια, δεν πρόκειται παρά για απλούστατη άθροιση δυαδικών αριθμών, χωρίς καν μεταφορά υπολοίπου.
Αυτό που λέω κ. papadim είναι ότι αν θέλω να κάνω το κόλπο αυτό στη μάνα μου η οποία είναι αδαής περί τα μαθηματικά, πρέπει να βρω και κάποιον που να γνωρίζει από δυαδικό σύστημα, τίποτα περισσότερο...
ΔιαγραφήΦώτη, αντιλαμβάνομαι τη δυσκολία που λες, γι αυτό άλλωστε στη δική μου πρόταση, στο αρχικό μου σχόλιο, δε χρησιμοποίησα καθόλου το δυαδικό σύστημα, παρά μόνο μετρήματα σε γραμμές και στήλες και μονά-ζυγά. Αυτά δε χρειάζονται παρά μόνο στοιχειώδεις γνώσεις αριθμητικής.
ΔιαγραφήΤώρα, αν δε σου άρεσε η λύση που έδωσα, και επειδή ο Βενιζέλος μάλλον δεν το κατέχει καθόλου το δυαδικό, ενώ ο Ριζόπουλος σού πέφτει ίσως λίγο μακριά, αν δεν έχεις κανέναν άλλο που να το ξέρει, όποτε με χρειαστείς είμαι στη διάθεσή σου! :-)
Λοιπόν, το βρήκα. Αφού απαιτούνται 3 άτομα, μπορούν να πραγματοποιήσουν το κόλπο 3 γνωστοί Σταύροι: Ο Σταύρος Τσώχος, ο Σταύρος Νταϊφάαααας, ο Σταύρος Ζακεστίδης!!!
ΔιαγραφήΝαι βέβαια Θανάση, έτσι είναι ,και παράλειψή μου όντως που δεν το ανέφερα ρητώς, αν και προκύπτει εμμέσως,και από το σύστημα "άρτιων-περιττών" στο αρχικό σου σχόλιο, και από την αναφορά-"μετάφραση" που έκανα στο δεκαδικό σύστημα (βάσει της δικής σου αρχικής μεθοδολογίας) που ουσιαστικά είναι η ίδια "πρόσθεση" αλλά πιο πολύπλοκη (μεθοδολογικά) λόγω μεταφορών υπολοίπων.
ΑπάντησηΔιαγραφήΕπίσης , αξιοσημείωτο εξ'αυτού που επισημαίνεις για τον τελεστή Xor είναι και πως περιττό πλήθως ίδιων ορισμάτων (π.χ άσσων ή μηδενικών) δίνουν "αληθές" δηλαδή 1 ,και άρτιο πλήθος---0.
Το $mod 2$ που επεσήμανε ο Θανάσης, δείχνει και γιατί η αλλαγή που γίνεται στο τετράγωνο Α(ποτέλεσμα της Xor) είναι ισοδύναμη είτε βάζουμε νταμάκι,είτε βγάζουμε, αφού στην binary αριθμητική το $+1$ είναι ισοδύναμο με το $-1$
ΑπάντησηΔιαγραφήΜια πρόσθετη γενικευση και συνάμα απόδειξη του γιατί υπάρχει λύση μόνο για $2^{ν}$ τετράγωνα είναι να δούμε το θέμα κάτω από το πρίσμα της Θεωρίας Γράφων.
ΑπάντησηΔιαγραφήΑν κατασκευάσουμε ένα γράφημα που να ανταποκρίνεται στο πρόβλημα , με τις κορυφές του γραφήματος να αντιστοιχούν στις θέσεις των νταμακίων , τι έχουμε;
Έχουμε τις κορυφές να είναι σε "ένα προς ένα" ανιστοίχιση με τα υποσύνολα του συνόλου των 64 στοιχείων.
Ας συνδέσουμε 2 κορυφές ,αν μπορούμε να μεταβούμε απο μια θέση σε μια άλλη ,αφαιρώντας ή προσθέτωντας ένα νταμάκι. Αυτό σημαίνει ,πως κορυφές συνδέονται εάν δύο αντοίστοιχα σύνολα διαφέρουν κατά ΑΚΡΙΒΩΣ ΕΝΑ στοιχείο.
Το προκύπτον γράφημα είναι κανονικό (regular) και κάθε κορυφή συνδέεται με ακριβώς 64 άλλες κορυφές. Αν αποδώσουμε σε κάθε τετραγωνάκι ένα διαφορετικό από 64 χρώματα, τι συμβαίνει; Ο Γιάννης μπορεί να βρει το τετραγωνάκι Χ ,απλώς κοιτάζοντας τη σκακιέρα. Αυτό σημαίνει πως πρέπει να υπάρχει μια ΜΟΝΟΣΗΜΑΝΤΗ αντιστοιχία (bijection) μεταξύ κορυφών του γράφου και τετραγώνων. Με άλλα λόγια μπορούμε να χρωματισουμε το γραφο με 64 χρώματα. Η ύπαρξη της στρατηγικής της λύσης σημαίνει δε πως ο χρωματισμός μπορεί να είναι τέτοιος ώστε κάθε κορυφή να συνδέεται με κορυφές ΟΛΩΝ (και των 64) των χρωμάτων. Πρέπει να έχουμε δηλαδή ένα γράφημα "μονοχρωματικό" και τα $K$ χρώματα να χρωματίζουν ολες τις κορυφές έτσι ώστε η καθεμιά να έχει ΑΚΡΙΒΩΣ ΕΝΑΝ γείτονα-κορυφή από ΚΑΘΕ χρώμα.
Λίγο θεωρητικά και αφηρημένα αυτά ίσως και γι'αυτό ας έρθουμε να δούμε και να κατανοήσουμε γιατί η στοιχειώδης περίπτωση $3$ τετραγώνων (και επαγωγικά κάθε συνόλου με $card διάφορο του $2^{ν}$ ) δεν ανταποκρίνεται στα παραπάνω.
Η "μονοδιάστατη" περίπτωση $1 Χ 2$ είναι τετριμμένη.
Ας πάρουμε λοιπόν τη σκακιέρα $1Χ3$ με $3$ τετραγωνάκια.
Υπάρχουν 2^3=8 διαφορετικές διατάξεις τετραγώνων.
Ας θεωρήσουμε την αρχική κατάσταση ,έστω "ΑΡΧΗ" και την τελική (βάσει της οποίας πρέπει να βρει το τετρ. ο Γιάννης) ,έστω "ΤΕΛΟΣ". Για κάθε σχηματισμό της "ΑΡΧΗΣ" φέρτε μια κοκκινη γραμμή σε κάποι0 στοιχείο του "ΤΕΛΟΣ" που θα αντιστοιχεί στην ενέργεια του Βαγγέλη ,αν ο καθ.Χ έχει διαλέξει ας πούμε το 1ο τετράγωνο από τα 3. Παρομοίως , ας φέρουμε πρασινες και μαύρες γραμμές που να δείχνουν τι ενέργεια κάνει ο Β (και δημιουργει έναν σχηματισμό στη στηλη "ΤΕΛΟΣ")για την επιλογή από τον Χ των τετραγλωνων 2 και 3 ,αντίστοιχα.
Όταν λοιπόν ολοκληρωθεί αυτό το γράφημα, τι έχουμε;
Έχουμε $24$ γραμμές("κατευθυντικές ακμές" με ορολογία γράφων) , $8$ από κάθε χρώμα.
Από καθέ διάταξη "ΑΡΧΗΣ" ξεκινούν μία κοκκινη,μία πράσιν και μία μαύρη γραμμή. Κάποιο ζεύγος "ΑΡΧΗ"-"ΤΕΛΟΣ" συνδέονται μόνον εάν διαφέρουν λόγω προσθήκς ή αφαίρεσης ΕΝΟΣ μόνο νταμακίου. Επεται λοιπόν πως και ακριβώς 3 γραμμές πρέπει να καταλήγουν σε κάθε διάταξη του "ΤΕΛΟΣ".
Ο Γιάννης βλέπει μόνον κάποια διάταξη "ΤΕΛΟΣ".
Το διάγραμμα δείχνει εάν έχει αρκετή πληροφορία για να αποδικωποιήσει την επιλογή του Χ. Προφανώς, αν όλες οι γραμμές που καταλήγουν σ'αυτό το "ΤΕΛΟΣ" έχουν το ίδιο χρώμα, τότε ξέρει την επιλογή του Χ και το πρόβλημα λύθηκε.
Σε διαφορετική περίπτωση, δεν μπορεί να είναι σίγουρος.
Αρα, η όποια στρατηγική,για να είναι επιτυχής πρέπει η ΚΑΘΕ "ΤΕΛΟΣ" κατάσταση να είναι "Μονοχρωματική". Αυτό όμως θα σήμαινε πως ο ολικός αριθμός από κόκκινες (ή πράσινες ή μαύρες) γραμμές είναι πολλαπλάσιο του $3$. Αυτό όμως έρχεται σε αντίθεση με αυτό που ήδη ξέρουμε πως ισχύει,δηλαδή πως υπάρχουν 8 γραμμές Χ 3 χρώματα=24 (όχι πολ/σιο του 3).Άρα άτοπο. Αρα, δεν μπορεί να υπάρξει για 3 τετράγωνα ,εγγυημένη στρατηγική.
Κάπως δύσκολο να περιγράφεις γραφήματα με λόγια, αλλά προσπάθησα. (έχω κι ένα άθλιο πληκτρολόγιο που με παιδεύει αφάνταστα ...συγγνώμη για τα ενδεχόμενα γραμματικά λάθη)
Ουφ... ξαναγράφω το κομμάτι που δεν εμφανίζεται σωστά και αφορά την απόδειξη αδυναμίας σίγουρης σταρτηγικής για 3 τετράγωνα. (1 Χ 3 σκακιέρα):
ΑπάντησηΔιαγραφή" Ας πάρουμε λοιπόν μια σκακιέρα με 3 τετραγωνάκια. Υπάρχουν 2^3 =8 διαφορετ. διατάξεις τετραγώνων.
Ας ονομάσουμε την αρχική κατάσταση "ΑΡΧΗ" και την τελική "ΤΕΛΟΣ"
Για κάθε σχηματισμό "ΑΡΧΗΣ" φέρνουμε μια κόκκινη γραμμή που συνδέει με την διάταξη στο "ΤΕΛΟΣ" που προκύπτει αν ο Χ έχει διαλέξει ας πούμε το 1ο τετράγωνο, Ομοίως και για την επιλογή του 2ου και 3ου τετραγώνου από τον Χ, χρησιμοποιούμε αντίστοιχα πράσινου και μαυρου χρώματος γραμμές.
Γραφημα κομπλέ. έχουμε 24 (3*8) γραμμές (ακμές)
Από καθε "ΑΡΧΗ" ξεκινουν 1 κοκκινη,1πρασινη και 1 μαύρη.
Ενα ζευγάρι "ΑΡΧΗ-ΤΕΛΟΣ" συνδέεονται μονον εάν διαφέρουν κατά 1 νταμάκι (που έχει προστεθεί ή αφαιρεθεί), άρα πρεέπι να καταλήγουν 3 ακμές και σε κάθε "ΤΕΛΟΣ"-διάταξη.
Όταν ο Γιάννης (που βλέπει μόνο "ΤΕΛΟΣ") θέλει να έχει πλήρη (δηλαδή μονοσήμαντη!) πληροφορία για να βρει την επιλογη του Χ, πρέπει να βλεπει γραμμές που να καταλήγουν και να είναι το ίδιο χρώμα. Τότε μπορεί να βρει το Χ προφανώς, αλλιώς δεν είναι σίγουρος. Αρα,για να είναι επιτυχημένη η στρατηγική πρέπει η κάθε διάταξη "ΤΕΛΟΥΣ" να είναι "Μονοχρωματική".
Αυτό σημαίνει πως ο ολικός αριθμός από κοκκινες (ή πράσινες ή μαυρες) γραμμές είναι πολλαπλάσιο του 3.Αυτό όμως έρχεται σε αντίθεση με αυτό που ήδη ξέρουμε πως ισχύει,δηλαδή πως υπάρχουν 8 γραμμές (όχι πολ/σιο του 3).Άρα άτοπο. Αρα, δεν μπορεί να υπάρξει για 3 τετράγωνα ,εγγυημένη στρατηγική.
ΥΓ. Το ""8 *3 =24 κ.λ.π στο προηγούμενο σχόλιο στο τέλος ,είναι προφανές λάθος-παραδρομή πληκτρολόγησης. Καληνύχτα! :-)
Πράγματι, Γιώργο,σε σκακιέρες 3χ1, 1χ3 ή 3χ3, 1χ9, 9χ1
ΑπάντησηΔιαγραφήκαι γενικά σε σκακιέρες 2^ν +1 δεν έχουμε πάντα λύση και
μάλιστα δεν έχουμε λύση μόνο σε μία περίπτωση αν ο καθ. Χ
επιλέξει το τελευταίο τετραγωνάκι και εκεί δεν υπάρχει νταμάκι.
Όλα τα υπόλοιπα τετράγωνα βρίσκονται αλλά και το τελευταίο,
αν υπάρχει νταμάκι σε αυτό βρίσκεται, νομίζω τουλάχιστον ότι
βρίσκονται.
Ας εξετάσουμε την σκακιέρα 3χ3
0000...0001...0010
0011...0100...0101
0110...0111...1000
Πέραν των γράφων που αναφέρεις διεξοδικά, αλλά δεν έχω ασχοληθεί καθόλου με αυτούς και δεν βρίσκω σχετική αρθρογραφία στο διαδίκτυο, στα Ελληνικά, υπάρχει και πρακτικός τρόπος προσέγγισης του θέματος.
Ο λόγος που δεν μπορεί να βρεθεί το τελευταίοτετράγωνο, αν το επιλέξει ο κ. Χ και δεν υπάρχει νταμάκι σαυτό είναι ότι το 1000 είναι ο μόνος τετραψήφιοςαριθμός και το Σ xor των υπολοίπων <<<1000 σε κάθε περίπτωση, άρα αδύνατο να βρεθεί.
Αν επιλεγεί από τον κ.Χ το τελευταίο και υπάρχει νταμάκι δεν έχουμε παρά να δώσουμε Σ xor =0 στα υπόλοιπα τετράγωνα με νταμάκι και άρα 0 xor 1000=1000.
Αν επιλεγεί οποιοδήποτε νταμάκι πλην του τελευταίου,
αδιαφορούμε για το τελευταίο και έχουμε στην ουσία σκακιέρα με 8 τετραγωνάκια, πχ 2χ4 (=2^3)
0000...0001
0010...0011
0100...0101
0110...0111...(1000)
Όμοια και για κάθε σκακιέρα 2^ν (+1) (17=16+1, 33=32+1, 65=64+1,...).
Πολύ ωραία διερεύνηση και ανάλυση,Ευθύμη!
ΑπάντησηΔιαγραφήΝα λοιπόν που διεύρυνες ωραία την οπτική του θέματος.
Είμαι λίγο πιεσμένος από χρόνο αυτή τη στιγμή για να το δω αναλυτικά, αλλά είχα από χθες την αίσθηση -και μού φαίνεται πως το σχόλιό σου την ενισχύει/επιβεβαιώνει- πως αν οι κανόνες του παιχνιδιού αλλάξουν ελαφρώς και μπορεί ο Β, να αφήσει ΑΠΑΡΑΛΛΑΧΤΗ την κατάσταση στη σκακιέρα (να μη βαλει-βγαλει νταμάκι,δηλαδή) υπάρχει μονοσήμαντη λύση και για $3$ τετράγωνα. Κοίτα το λίγο και σύ, αν δεν έχεις φυσικά τίποτε καλύτερο να κάνεις.
Αν εννοείς ο Β. να μπορεί να προσθέσει ή να αφαιρέσει νταμάκι ή να αφήσει απαράλλαχτη τη σκακιέρα, ναι υπάρχει μονοσήμαντη λύση και για 3 τετράγωνα.
ΑπάντησηΔιαγραφήΑυτή η τρίτη δυνατότητα άρει το αδιέξοδο που είχα, με την
αρίθμηση που έκανα 1, 2,.... αντί 0,1,.. θυμίζω ότι η λύση που είχα βρεί “κόλλησε” μόνο στην περίπτωση που
Σxor (τετραγώνων με νταμάκια)=Χ (επιλογή του κ. Χ)
και δεν είχε ο Β κίνηση αφού δεν υπήρχε 0 τετράγωνο.
Με την τρίτη δυνατότητα ο Β, σε αυτή την περίπτωση δεν κάνει τίποτα.
Συνολικά στην σκακιέρα 1(01).2(10).3(11) τετραγώνων διακρίνουμε τις περιπτώσεις:
Ο κ. Χ δεν βάζει κανένα νταμάκι και δείχνει σαν Χ, ένα από τα 3,
έστω το 2 προφανώς ο Β. βάζει νταμάκι στο 2, ο Γ. λέει το 2.
Ο κ. Χ τοποθετεί νταμάκι σε ένα τετράγωνο έστω το 1 και επιλέγει ένα άλλο ως Χ, έστω το 3, άρα 01 xor 11=10, o B τοποθετεί νταμάκι στο 2, 01xor 10=11
Ο κ. Χ τοποθετεί 2 νταμάκια και επιλέγει ως Χ ένα από τα δύο,
ο Β. αφαιρεί το άλλο.
Ο κ. Χ τοποθετεί 2 νταμάκια, έστω στα 1 και 2 τετράγωνα και επιλέγει ως Χ το 3, 01 xor 10=11, ο Β. τα αφήνει ως έχουν, ο Γ. δείχνει το 3.
Ο κ. Χ τοποθετεί νταμάκια και στα 3 τετράγωνα και επιλέγει, έστω το 2, 01 xor 10 xo r 11=0, o B. αφαιρεί το νταμάκι του 2,
01 xor 11=10 (2), o Γ. βρίσκει το 2.
Αν εννοείς μόνη δυνατότητα του β. να τα αφήσει απαράλλαχτα,
αλλά αποκλείω να εννοείς αυτό, γιατί είναι από “χέρι” αδιέξοδο.
Έχω την αίσθηση, θα έλεγα σχεδόν βεβαιότητα, ότι με τρεις
επιλογές για τον Β έχουμε μονοσήμαντη λύση και στην 3χ3
σκακιέρα, αφού τα 2 τελευταία τετράγωνα 8 και 9 στο δυαδικό
σύστημα είναι 1000 και 1001, και οι 2 τετραψήφιοι, αλλά πιθανόν και σε κάθε 2^ν +1 σκακιέρα.
Για σκακιέρα 1χ17, 16=10 000, 17=10 001
Για σκακιέρα 1χ33 ή 3χ11, 32=100 000, 33=100 001
Για σκακιέρα 1χ65 ή 5χ13, 64=1 000 000, 65=1 000 001
κ.ο.κ....
Υ.ΓΑν άργησα να απαντήσω, αυτό οφείλεται ότι το μεσημέρι
(4-6) ξεκουράζομαι ξαπλα ή ακόμα καλύτερα κοιμάμαι!
Και έπρεπε να το συντάξω κάπως αναλυτικά, για να είναι
κατανοητό προς κάθε κατεύθυνση ή αυτή ήταν η πρόθεση μου, άσχετα από το πόσο τα κατάφερα!
Tώρα που το professional addition-μου αποδείχτηκε ,για μια ακόμη φορά,φευ! μαγική εικόνα...επανέρχομαι στο εγγυημένα ευχάριστο parity addition (όπως επισήμανε ωραία ο Θανάσης ότι είναι το xoring) και στο θέμα τού ,αν υπάρχει λύση για $3$ τετράγωνα.
ΑπάντησηΔιαγραφήΠως με τον κανόνα της "υποχρεωτικά μίας" μεταβολής δεν υπάρχει λύση πάντα για $ν=3$ είναι σαφές. Το αποδείξαμε ,σαν θεώρημα "μη ύπαρξης" μοναδικής στρατηγικής με τους μονοχρωματικούς γράφους , και ο Ευθύμης έδειξε πολύ ωραία την ακριβή περίπτωση μη δυνατότητας μοναδικής μετάβασης με parity addition, που είναι ο $Χ$ στη σκακιέρα ${00, 01, 10}$ να βάλει ένα μόνο νταμάκι στο 2ο τετράγωνο (01) και να επιλέξει σαν Χ το τρίτο τετράγωνο (10). Τοτε ο Β δεν έχει τρόπο να μετατρέψει το 01 σε 10 με μία μόνο κίνηση. Αλλά αν είχαμε άλλο ένα τετραγωνο στη σκακιέρα (4 συνολικά) τότε βεβαίως θα μπορούσε να βάλει ένα νταμάκι σ'αυτό , το 11 δηλαδή ,και να το κάνει 10 ,οδηγώντας τον Γ. στη λύση. Kι αυτή η συλλογιστική δείχνει (για μια ακόμη φορά,εντάξει! :-) )γιατί η μέθοδος δουλεύει μόνο για δυνάμεις του 2. Μόνο τότε (όπως επισήμανε κι ο Ευθύμης αποπάνω) έχει ο Γ. την "πλήρη γκάμα" επιλογών δυιαδικών μετατροπών από κάθε διαδικό αριθμό σε κάθε άλλο.
Αν όμως , οι κανόνες επιτρέψουν ΚΑΙ να μην μεταβάλλει ο Β. το ταμπλώ, τότε υπάρχει τρόπος λύσης ΚΑΙ για $ν=3$ . Κατέληξα ,με trial and error , σε μια τέτοια διάταξη:
3 τετράγωνα σημαίνει $2^{3}=8$ binary strings. Π.χ το $010$ σημαίνει "ένα μόνο νταμάκι στο δεύτερο τετράγωνο".
Οι 8 δυνατότητες (0 έως 7), είναι:
000
001
010
011
100
101
110
111
Στο κάθε αριθμό πρέπει να αντιστοιχίσουμε ένα "χρώμα" δηλαδή τετράγωνο α,β,ή γ (έστω α=1ο,β=2ο,γ=3ο)
Χωρίς να έχω βρει κάποιον "συστηματικό" τρόπο ,με δοκιμές trial and error όπως προείπα , βρήκα την ακόλουθη διάταξη που δουλεύει σίγουρα:
000 α
001 β
010 γ
011 γ
100 γ
101 γ
110 β
111 α
Για παράδειγμα , ο Β. βλέπει τον συνδυσμό 001 και ο Χ διαλέγει το τετράγωνο γ. Προσθέτει ένα νταμάκι και φτιάχνει 011 που σημαίνει "γ". Βεβαίως αν έχει ας πούμε το 000 ή το 111 και ο Χ επιλέξει το α, πρέπει να αφήσει το ταμπλώ αμετάβλητο.
Όλοι οι συνδυασμοί του πιο πάνω ταμπλώ οδηγούν με 1μία -το πολύ!- κίνηση, σε λύση.
Το ζήτημα είναι αν αυτό γενικεύεται σε μεγαλύτερες διαστάσεις. Δεν βλέπω τον θεωρητικό λόγο να μην γίνεται, αλλά μην έχοντας καταλήξει σε γενική μεθοδολογία, επιφυλάσσομαι και περιμένω και απόψεις από τους εκλεκτούς σχολιαστές!
Πάντως, αν δουλεύει γενικά το πράμα ,νομίζω πως είναι μια ωραία ιδέα, και πιθανόν και πρωτότυπη. ;-)
A ωραία! Όπως καταλαβαίνεις ,γράφαμε σχεδόν ταυτόχρονα Ευθύμη!
ΑπάντησηΔιαγραφήΑυτό το σχόλιο αφαιρέθηκε από τον συντάκτη.
ΑπάντησηΔιαγραφήΓια τους φίλους που θα ήθελαν να ασχοληθούν παραπέρα, θα πρότεινα και την εξής παραλλαγή του αρχικού προβλήματος:
ΑπάντησηΔιαγραφήΑντί σκακιέρας 8Χ8 με νταμάκια ή όχι σε κάθε τετράγωνο, ο κ.καθηγητής έχει μια σκακιέρα 6Χ6 και σε όλα τα τετράγωνα έχει τοποθετήσει και από ένα κανονικό ζάρι με οποιαδήποτε πάνω όψη στο καθένα (36 τετράγωνα δηλαδή που στο καθένα υπάρχει και από ένας αριθμός, 1 έως 6, όχι αναγκαστικά ο ίδιος για κάθε τετράγωνο). Ο κ.καθηγητής δείχνει τη διάταξή του στο Βαγγέλη και του ανακοινώνει ένα συγκεκριμένο τετράγωνο. Ο Βαγγέλης πρέπει να μεταβάλει κατά +1 την όψη ενός και μόνο τετραγώνου της δικής του επιλογής (1->2, 2->3 κ.λπ.), εκτός κι αν το τετράγωνο που επιλέγει έχει 6, οπότε θα πρέπει να το φέρει να δείχνει 1. Τώρα ο Γιάννης, που καλείται μπροστά στη σκακιέρα, μετά την αλλαγή που έκανε ο Βαγγέλης, θα πρέπει να βρει ποιο ήταν το τετράγωνο που υπέδειξε ο κ.καθηγητής στο Βαγγέλη.
Θανάση, πολύ ωραία η εκδοχή που πρότεινες. Δίνω την προσέγγισή μου :
ΔιαγραφήΤο πρόβλημα είναι κι αυτό προφανώς πρόβλημα «απεικονίσεων-mappings» μόνο που εδώ δεν έχουμε
6-bitους διαδικούς αριθμούς,me bit: {0,1} όπως στο αρχικό πρόβλημα «διαστάσεων» 2^ν=2^6 ,αλλά προφανώς 2-μπιτους εξαδικούς, με bit:{0,1,2,3,4,5}. Oι αριθμοί των τετραγώνων της 6Χ6 σκακιέρας δηλαδή αντιστοιχούν σε κάποιον 6δικό αριθμό από το 00 έως το 55. (35 στο δεκαδικό) Για να μην μπλέκουμε με Χoring σε mod6, θα το αντιμετωπίσω εναλλακτικά (αλλά κατ ουσίαν το ίδιο είναι, βεβαια). Ένα παράδειγμα ίσον με δύο θεωρίες λένε ,οπότε δίνω παράδειγμα μονοδιάστατης ανάλυσης ,δηλαδή για σκακιέρα 1 Χ 6, ήτοι 6 ζάρια στη σειρά.
Έστω πως η σειρά είναι:
6 1 3 6 5 4
Από αριστερά προς δεξιά έστω πως αντιστοιχούν στους εξαδικούς αριθμούς τετραγώνων κατά σειρα:
00 01 02 03 04 05 , ήτοι έχουμε 6-->00 , 1-->01 , 3-->02 , 6-->03, 5-->04 , και 4-->05.
Έστω πως ο Χ επιλέγει το πέμπτο ζάρι ,αυτό που δείχνει 5, δηλαδή το τετράγωνο 04.
Μια απλή προσέγγιση είναι να προσομοιώσουμε σύμφωνα με την απεικόνιση πιομ πάνω , και τον αριθμό των ζαριών με τους συντελεστές ,δημιουργώντας έναν 6δικό αριθμό και να δούμε το mod 6 αυτού του αριθμού.
6*00 +1*01 + 3*02 +6*03 + 5*04 +4*05=6+1+6+18+20+20=71 = 5 mod 6
Aποστολή λοιπόν του Β. είναι να μετατρέψει το άθροισμα από 5 (mod 6) σε 4 (mod 6) ,οπότε φωτογραφίζει το τετράγωνο 4 για τον Γιάννη.
Πρέπει δηλαδή να προσθέσει άλλα 5 στο άθροισμα ,οπότε του χρειάζεται να μεταβάλλει τον συντελεστή «05» κατά 1 μονάδα ,και κάνει το 6ο ζάρι (το 4) 5. Οπότε ,το νέο άθροισμα είναι:
6*0 +1*1 +3*2+6*3+5*4 + 5*5=76= 4 mod 6 = τετράγωνο 04 . Voila! :-)
Aν γενικά, το mod 6 άθροισμα πρέπει να μείνει αμετάβλητο , γιατί ταυτίζεται με το τετράγωνο επιλογής του Χ, προφανώς αλλάζουμε το ζάρι «00».
Η αναλογία-μετάβαση στο διδιάστατο πρόβλημα της σκακιέρας
6 Χ 6 είναι προφανής. Απλώς θα δουλέψουμε το άθροισμα σε mod 36. Θα προκύψει ένας αριθμός από το {0, 1, 2,…,35} . Aν ας πούμε βρούμε το άθροισμα να είναι 30 mod 36 ,και ο Χ έχει επιλέξει το τετράγωνο 25(σε βάση 6) (το 17ο τετράγωνο απ’αρχής δηλαδή) για να βγάλουμε 25 mod 36 ,πρέπει να προσθέσουμε 41. (41μοδ36=5) θα πάμε στο τετράγωνο «41» (τεράγωνο 25ο στο δεκαδικό) που είναι ο πολλαπλασιαστής του 41 και θα αυξήσουμε το ζαρι κατά 1. (Η αλλάγη 6 σε 1 γενικά, προφανώς αυξάνει το mod 6 κατά 1, άρα Ο.Κ.)
Εγραψα κάπως βιαστικά, αλλά νομίζω πως όλα είναι Ο.Κ.
Θανάση, είσαι ευγενής και διακριτικός ώστε να δώσεις μόνο εύσημα στον "βιαστικό γιώργη":-) ,αλλά ας διορθώσω το αριθμητικό λάθος στο τέλος αποπάνω.
ΔιαγραφήΓια να γίνει τπ 30 mod 36 ---> 25 mod 36 πρέπει να προσθέσουμε 31 (κι όχι βέβαια 41).
30+31= 61 =25 mod 36. Άρα πάμε στον πολλαπλαστή του "31" και αυξάνουμε το ζάρι του κατά 1.
ΥΓ. Παρεμπιπτόντως , η εκδοχή σου το θέματος είναι πολύ καλή , ειδικά η "τάξης/διάστασης 1" βερσιόν με τα (mod 6) "μαθαίνεται" πανεύκολα, και μπορεί ασφαλώς να εντυπωσιάσει κόσμο και κοσμάκη! :-)
Γιώργο ευχαριστώ για το σχόλιό σου και την ωραία λύση!! Το βιαστικό σου, όπως το λες, γράψιμο είναι που τα λόγια σου τρέχουν να προλάβουν τη γρηγοράδα της σκέψης σου, αλλά είσαι πάντα to the point:-). Επίτρεψέ μου να δώσω με ελάχιστα λόγια την απλούστατη συνταγή της στρατηγικής (για όσους τυχόν θέλουν να παίξουν το κόλπο σε συγγενείς και φίλους):
ΑπάντησηΔιαγραφήΒαγγέλης
Αποδίδει σε κάθε τετράγωνο μια διεύθυνση γραμμής (0 έως 5) και μια διεύθυνση στήλης (0 έως 5).
Πολλαπλασιάζει τη διεύθυνση γραμμής κάθε τετραγώνου με τον αριθμό που δείχνει το αντίστοιχο ζάρι και αθροίζει τα 36 γινόμενα προσθέτοντας σε αυτά και τη διεύθυνση γραμμής του τετραγώνου που έδειξε ο καθηγητής, όλα mod6. Το αποτέλεσμα είναι η διεύθυνση γραμμής του τετραγώνου που θα αλλάξει.
Επαναλαμβάνει το ίδιο ακριβώς με τις διευθύνσεις στήλης των τετραγώνων και έτσι βρίσκει και τη διεύθυνση στήλης του τετραγώνου που θα αλλάξει.
Πάει στο τετράγωνο που τον οδηγούν τα προηγούμενα και το αλλάζει, κατά τα οριζόμενα.
Γιάννης
Στη διάταξη της σκακιέρας, όπως την άλλαξε ο Βαγγέλης, κάνει ό,τι ακριβώς έκανε ο Βαγγέλης, με μόνη τη διαφορά ότι στα 36 γινόμενα δεν προσθέτει τίποτε. Έτσι βρίσκει την πλήρη διεύθυνση του τετραγώνου του καθηγητή.