Modulo 3
Il quesito di quest'anno riguarda la variante modulo 3 del ben piu' noto LIGHTS OUT:
|
Prima di dare la soluzione facciamo alcune considerazioni di carattere generale.
E' interessante osservare che NON e' importante l'ordine in cui vengono eseguiti i click. Inoltre e' sufficiente
cliccare ciascuna casella al massimo due volte (cliccarla tre volte equivale a non cliccare affatto). |
Ogni invariante si calcola facendo la somma dei numeri delle caselle con il segno "+"
meno la somma dei numeri delle caselle con il segno "-" e riducendo il risultato modulo 3. |
Come si vede, in ogni caso i numeri dei "+" meno i numeri dei "-" delle caselle interessate dall'operazione (quelle verdi) danno sempre 0 modulo 3
e quindi non incrementano ne' diminuiscono il valore iniziale dell'invariante (qualunque esso sia!). |
Se l'ultima riga e'... | ...allora clicca nella prima riga queste caselle e poi riduci |
00000 | 00000 |
01010 | 22000 |
02020 | 11000 |
10201 | 02000 |
11211 | 21000 |
12221 | 00200 |
20102 | 01000 |
21112 | 20000 |
22122 | 12000 |
Veniamo quindi alla soluzione dei problemi proposti. |
I problemi proposti sono una variante modulo 3 del gioco LIGHTS OUT dove invece i numeri nelle caselle vengono invece ridotti modulo 2. La annullabilita' di una tabella binaria (LIGHTS OUT significa appunto "spegnere tutte le luci") si puo' interpretare come la risoluzione di un sistema lineare di ben 25 equazioni (le 25 caselle) in 25 incognite (le combinazioni di click) modulo 2. Nel caso modulo 3 il metodo si adatta facilmente sostituendo il campo algebrico Z_2 con Z_3. Tale metodo e' diverso dalla spiegazione che ho dato sopra che e' piu' elementare anche se meno generale. Infatti, per esempio, con l'algebra lineare si puo' spiegare perche' nel nostro caso le soluzioni, se ci sono, sono 27. La ragione e' che la matrice del sistema ha rango 22 (rispetto a Z_3) mentre lo spazio delle variabili ha dimensione 25 quindi rimangono 3 parametri liberi ciascuno da scegliere in Z_3 che ha 3 elementi quindi 3^3=27 soluzioni. Una descrizione di questo approccio con l'algebra lineare si puo' trovare su Jaap's Puzzle Page (precisamente qui). Per i piu' curiosi consiglio di provare a dare un'occhiata ai seguenti articoli: The Solving of Lights Out e Lights Out!: A Survey of Parity Domination in Grid Graphs. Ulteriori referenze si possono trovare sul sito MathWorld della Wolfram. |