Newsgroup: it.hobby.enigmi
Titolo: Matrici luminose

A proposito delle matrici luminose, mi scrive Sergio Reggi in leggera 
difficolta' di computer. Gli faccio volentieri da ponte, testualmente:
"
...
Riguardo alle matrici luminose, ho seguito la discussione su mailgate e 
volevo porre questo quesito (non so se Dario Uri ne sia a conoscenza).
Premesso che si prendono in considerazione matrici quadrate e con le 
celle da un solo colore (acceso o spento), possiamo dire che una 
qualsiasi soluzione è determinata da quali pulsanti premere sulla prima 
riga (il resto viene da se; immagino che sia anche intuitivo). Si può 
impostare un sistema di equazioni (Dario Uri ne parlò su MC), la cui 
soluzione determina quante caselle della prima riga dipendano dalle 
restanti. Ad esempio: la matrice 5x5, ha due caselle libere e le tre 
restanti che dipendono da tre equazioni sulle prime due. In altre parole, 
posso fare quello che voglio con le prime due caselle, applicare le 
soluzioni per le altre tre caselle, e completare la matrice. Senza 
considerare soluzioni simmetriche, speculari ecc. possiamo dire che il 
numero di soluzioni per una determinata matrice di ordine n è 2^(numero 
di caselle libere risultanti dal sistema).
Impostai all'epoca un programmino (che nemmeno ritrovo!!!) che dato in 
input l'ordine della matrice, determinava le caselle libere e quelle con 
equazioni. La cosa sorprendente è che solo la matrice 4x4 ha tutte le 
caselle libere; in altre parole posso premere i pulsanti della prima riga 
a mio piacimento, tanto una soluzione per accenderla tutta esiste sempre!!
La mia congettura è: non esiste nessuna matrice quadrata superiore alla 
4x4 con tutte le variabili libere.
Ciao
Sergio
P.S.: scusa il mio silenzio, sono stato in viaggio di nozze."
Congratulation!
Ciao a tutti  :o)
Livio
-- 
Posted from 
mta09-acc.tin.it
 [212.216.176.40] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 4x4 con tutte le variabili libere.
nel sito che ho già segnalato,
http://www.psc.edu/~burkardt/puzzles/lights_out_solution.html
c'è una tabella con i gradi di libertà degli interruttori, e sembra
confermare la congettura:
Dimension of the null space for an N by N grid.
N   Dimension
1   0
2   0
3   0
4   4
5   2
6   0
7   0
8   0
9   8
10  0
11  6
12  0
13  0
14  4
15  0
16  8
17  2
18  0
19 16
20  0
21  0
per un pelo il caso n=9 non smentisce la congettura: si possono scegliere 8
interruttori a caso!
In pratica si tratta di calcolare il rango (numero di righe linearmente
indipendanti) della matrice di influenza degli interruttori (ovvero della
matrice di ordine n^2 in cui l'elemento (i,j) vale 1 se l'interruttore i
pilota la lampadina j). Nel caso 5X5 vale 23, l'ho provato a mano (o
quasi...), quindi 2 gradi di libertà. Penso che i calcoli necessari a
determinare il rango siano complicatelli al crescere di n.
Ciao, Silv:o)

 

Dovresti vedere il caso n=492 (o giu di lì): ci sono solo 8 equazioni.
Io sono arrivato fino a n=500, ma non ho trovato altri casi simili a n=4.
Nel programma che non ritrovo (acc!! malediz!!) procedevo nel seguente modo:
partivo dalla prima riga con le equazioni pari alle incognite; ad es. per n=5:
x1   x2   x3   x4   x5
procedo con la costruzione delle equazioni sulle caselle restanti, come segue:
(seconda riga calcolata utilizzando la prima riga)
x1+x2+1   x1+x2+x3+1   x2+x3+x4+1   x3+x4+x5+1   x4+x5+1
(terza riga calcolata utilizzando la prima e la seconda)
x1+x3+1   x4   x1+x5   x3+x5+1
(quarta riga calcolata utilizzando la seconda e la terza)
x2+x3+x4+1   x1+x2+x4+x5+1   x1+x3+x5   x1+x2+x4+x5+1   x2+x3+x5+1
in pratica, ogni equazione che si va a costruire, determina lo stato di acceso
della casella della riga precedente. Ad esempio, la prima equazione della
quarta riga è determinata da
(x1+x3+1) + (x1+x2+1) + (x4) + 1   (x1 si elide perchè è doppio)
e pone nello stato di acceso  la prima casella della terza riga. Infatti:
(x1+x2+1) + (x1+x3+1) + (x4) + (x2+x3+x4+1) = 1 (sempre in modulo 2)
Questo programma l'ho sviluppato indipendentemente, ma credo che Dario Uri
utilizzava un metodo analogo.
Dario ci sei? Cosa ne dici?
Sergio
-- 
Posted from 
www.tercas.it
 [195.103.179.162] 


 Dario ci sei? Cosa ne dici?
Ciao Sergio,
Si' ci sono.
E' stato utilizzato un metodo simile al tuo, per la soluzione della 
variante piu' complessa  Pile di Pedine. Il metodo e' stato messo a punto 
da Dani Ferrari. Visto che la cosa desta un certo interesse, vedo di 
appoggiare i vari articoli in un sito accessibile, per chi avra' voglia di 
approfindire. Appena pronto do' notizia.
Grazie :) ciao dario