Κομψό θέμα

[billy_scabilly]

Τρεις παίκτες βρίσκονται έξω από ένα δωμάτιο μέσα στον οποίο υπάρχει ένας 8x8 πίνακας με 0 και 1(την κατάσταση των οποίων κανείς δεν ξέρει αρχικά αφού είναι απέξω). Ο Α και ο Γ είναι φίλοι και έχουν συννενοηθεί εκ των προτέρων, ενώ ο Β είναι εχθρός τους. Μπαίνουν στο δωμάτιο ο Α και ο Β,ενώ ο Γ μένει απέξω. Ο Β αλλάζει κάνει flip ένα bit του πίνακα(ο Α βλέπει τι κάνει) και μετά πρέπει να αλλάξει και o A ακριβώς ένα bit από τον πίνακα. Βγαίνουν από το δωμάτιο και μπαίνει ο Γ μετά. Υπάρχει στρατηγική που μπορούν να συννενοηθούν ο Α και ο Γ ώστε ο Γ μόλις μπει στο δωμάτιο να μπορέσει να βρει ποιο κουτάκι άλλαξε ο Β?

[ealexiou]

Οι και συνεννοήθηκαν εκ των προτέρων να κάνουν χρήση της ιδιότητας της πράξης :

Αν τότε ισχύει:

Αριθμούν τα τετράγωνα του πίνακα και μετατρέπουν την αρίθμηση στο δυαδικό σύστημα ήτοι:

Έστω ότι το υπάρχει στις θέσεις στο δυαδικό και και στις άλλες θέσεις (χάριν ευκολίας των πράξεων και χωρίς βλάβη της γενικότητας) και έστω ότι ο αλλάζει το τετράγωνο , από σε

Ο υπολογίζει το συνολικό xor των τετραγώνων που έχουν το .

Στο που βρήκε ξαναπροσθέτει το , , τετράγωνο 62) και αντικαθιστά το 0 με 1 στο τετράγωνο

Στον πίνακα τώρα υπάρχει το 1 στα τετράγωνα ..

Κάνοντας την πράξη μας δίνει το που αντιστοιχεί στο τετράγωνο και έτσι ο εύκολα βρίσκει ποιο τετράγωνο του πίνακα άλλαξε ο .