Newsgroup: it.hobby.enigmi
Titolo: Pile di pedine

Alcuni anni fa (molti) ideai un giochetto, che poi si e' sviluppato
in molte varianti. Ancor oggi in rete si trovano programmi-puzzles che 
si basano su questo principio. Fu pubblicato dal nostro Giovanni Ravesi, 
su Contromossa, dicembre 1984 col nome di Matrici Luminose. Immaginiamo 
di avere una scacchierina 5x5 dove in realta' ogni casella e' un 
pulsante illuminabile. Ogni volta che premo un pulsante, cambiano di 
stato accese/spente, oltre la casella toccata, anche le caselle 
adiacenti a questa. Iniziando con la scacchiera spenta e' possibile 
accendere tutte le luci? Non e' difficile trovare la soluzione, o ideare 
varianti e generalizzazioni.
Abbandonando il modulo 2, ora vi propongo un problema molto piu' difficile.
Ho una quantita' illimitata di pedine, ed una generica scacchiera NxN. 
Una mossa consite nel porre una pedina nella casella scelta ed una sulle 
caselle adiacenti. E' chiaro che se la casella e' lontana dal bordo si 
collocheranno 5 pedine a croce, se la casella e' sul bordo le pedine 
messe saranno 4, e per le caselle d'angolo saranno 3. Le pedine vengono 
via via accatastate le une sopra le altre.
Lo scopo e' quello di ottenere lo stesso numero di pedine per tutte le 
caselle, cioe'le pedine accumulate devono raggiungere la stessa altezza.
Il problema e' piu' complesso del precedente, in quanto, non lavorando 
piu' mod2, non sappiamo quale sia l'altezza che restituisca una 
possibile soluzione. Per fugare ogni dubbio riporto qui sotto la 
soluzione per una scacchiera 5x5.
Questo e' il numero di mosse da effettuare su ogni casella.
1 5 4 2 7
5 1 0 1 5
4 0 5 3 1
2 1 3 1 2
4 5 1 2 7
Il numero di pedine impilate su ogni casella e' ovviamente dato dalla 
somma delle mosse effettuate su tale casella e sulle caselle adiacenti.
E' facile vedere che tale numero e' sempre 11.
Il problema che vi propongo ora e' quello di trovare una soluzione per 
una scacchiera 9x9  (vi avverto pero' che c'e' da lavorare!!)

 una scacchiera 9x9  (vi avverto pero' che c'e' da lavorare!!)
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
:-)))
ciao
paolo

 E' facile vedere che tale numero e' sempre 11.
In alto a destra c'e' qualcosa che non va. 7+2+5=14.
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 In alto a destra c'e' qualcosa che non va. 7+2+5=14.
Ci va messo un 4, si noti la struttura simmetrica rispetto alla diagonale 
principale
Ciao,
GaS 


Si', scusate. Mi e' scivolato il dito un po' verso l'alto... sul 
tastierino :)

 in molte varianti. Ancor oggi in rete si trovano programmi-puzzles che
[snip
E' possibile farsi aiutare dall'algebra lineare elementare.
Chiamiamo ogni casella della scacchiera allo stesso modo di un elemento di
una matrice e cioè
a11 per l'elemento in alto a sinistra,a12 per quello immediatamente a destra
e così via,
a21 per il primo elemento della seconda riga e così via fino a a55 per
l'ultimo in basso a destra.
Scriviamo 25 equazioni in 25 incognite dove riportiamo per ogni casella
la condizione che ne permette un cambiamento di stato.
a11 sarà 1 cioè acceso quando premiamo su a11 oppure su a12 oppure su a21
quindi scriviamo
a11+a12+a21=1
ovvero
1*a11+1*a12+1*a21+0*a13+0*a14+...+0*a55=1
 Lo stesso facciamo per la seconda casella mantenendo l'ordine degli
elementi
a(nm).
 Al termine possiamo ottenere un matricione A 25x25, di zeri e uno che
moltiplica la colonna delle incognite a11,a12,a21,... e che uguaglia il
vettore colonna di tutti 1.
 Se invertiamo A abbiamo  [axy]=[[A^-1]]*[1...1]
cioè la soluzione cercata,se è di 0 e 1
Analogamente procediamo sostituendo al termine noto [1...1] un vettore di
numeri tutti uguali come si vuole nel secondo e terzo quesito.
Il problema è che questa procedura non è elegante e impone l'uso di grosse
potenze di calcolo per determinare l'inversa di una matrice così grande ma
sparsa.
Con alcuni accorgimenti e tecniche si possono però affrontare facilmente
problemi del genere.

Qualcuno (Carlo mi sembra) mi ha inviato una e-mail per avere alcune 
delucidazioni riguardo le matrici luminose, purtroppo inavvertitamente 
ho cancellato il mgs.
<Ti invito a ricontattarmi>
Scusate tutti dell'OT, ma ho dovuto per educazione.

 accendere tutte le luci? Non e' difficile trovare la soluzione...
[cut
11000
11011
00111
01110
01101


Hai detto che c'era da lavorare, mica che c'era da impazzire!!
Dopo tanto lavoro forza bruta (fatto manualmente) ho deciso un paio di cose:
- come nel tuo esempio anche in questo caso mettiamo una simmetria rispetto 
alla diagonale principale.
-ci sono sicuramente degli 0 nelle seguenti posizioni:
x x x x x x 0 x x
x x x x x x x x x
x x x x x x x x 0
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
0 x x x x x x x x
x x x x x x x x x
x x 0 x x x x x x
non è molto ma gia qualcosa :o)
Mettendo poi 6 incognite a, b,c, d, e, f come segue:
a b x x x x 0 x x
b c x x x x x x x
x x d x x x x x 0
x x x e x x x x x
x x x x f x x x x
x x x x x x x x x
0 x x x x x x x x
x x x x x x x x x
x x 0 x x x x x x
si ricavano, ricorsivamente, i valori delle altre caselle (45 in 
totale!!!!)in funzione delle 6 incognite. Dopo aver fatto il lavoraccio mi 
sono accorto che probabilmente era meglio mettere le incognite in posizioni 
differenti ma ormai il lavoro è fatto e non ricomicio di certo....
Arrivati a questo punto si ricavano 5 brutte equazioni che devono essere 
soddisfatte, purtroppo dopo un po' mi si incrociavano gli occhi e non sono 
sicuro al 100% della loro esattezza.
Comunque eccole qua per gli uomini di buona volntà:
-7a+28b+32c+10e-50d-7f=0
29a+104b+154c+238d+76e-13f=0
101a+130b+432c-468d+134e-57f=0
a+19b+36c+54d-5f-39e=0
39a+125b+145c+142d+39e-12f=0
Notiamo intanto che non ce ne aspettavamo 6 (nonostante le 6 incognite) 
perchè se una soluzione esiste allora ne esistono infinite moltiplicando 
ogni valore per una qualche costante k.
Le soluzioni devono essere inoltre tali che b>=c, a>=c, d>=c, 2b>=d-c e 
forse qualche altra condizione che mi sono perso per strada.
Sinceramente non riesco più a ragionare dopo più di un'ora passata a 
ricavarmi le equazioni di cui sopra, magari qualcuno prova a trovarne una 
soluzione per arrivare alla soluzione del problema originale. Ripeto però 
che non sono sicuro al 100% delle stesse, in caso non prendetevela con me 
:o)
Io butto il sasso......
Ciao,
Gabriele 

 Io butto il sasso......
Ho usato Mathematica per fare i calcolacci e me la sono cavata con poco,
perņ vista l'ora tarda non garantisco al 100%. Comunque ecco il mio
risultato (che non č simmetrico):
18, 35, 57, 27, 38, 15, 29, 63, 30
69, 12,  3,  0, 42, 40, 15,  0, 29
23,  3, 50, 50,  2, 10, 38, 15, 63
27, 34, 16, 20, 18, 32, 44,  6, 15
38, 42,  2, 18, 50, 18,  2, 42, 38
15,  6, 44, 32, 18, 20, 16, 34, 27
63, 15, 38, 10,  2, 50, 50,  3, 23
29,  0, 15, 40, 42,  0,  3, 12, 69
30, 63, 29, 15, 38, 27, 57, 35, 18
Le pedine sono sempre 122. Sarą il minimo?
Maurizio

 Le pedine sono sempre 122. Sarà il minimo?
Tanto è sempre così, si prende un problema in cui nessuno ha postato la 
soluzione per vari giorni, si scrivono 2 cavolate (non appositamente ma poi 
si sono rivelate tali) e qualcuno ti tira fuori la soluzione esatta in meno 
di un'ora.... :o)
Succede sempre, bisognerebbe approfondire il fenomeno  :o)
A parte gli scherzi: complimenti.
Ma come l'hai tirata fuori? penso che estrarre sol. random sia veramente 
troppo oneroso, a meno che non esistano veramente tantissime sol. diverse, 
ma non penso che, in ogni caso, ce l'avresti fatta in così poco tempo. 
Quindi?
Forse hai fissato N caselle in cui variavi i valori ciclicamente e, da 
queste, si ricavavano i valori delle restanti caselle in maniera ricorsiva? 
Se si, quali caselle di partenza hai scelto?
Insomma, non è tanto il risultato ma come ci si arriva.....
Facci sapere,
ciao
Gabriele 

Maurizio Frigeni wrote:

Bravi, bravissimi. A suo tempo lavorarono sul problema Dani Ferrari e 
l'analista tedesco Dieter Gebhardt.
Hanno trovato che 122 e' il minimo, e ci sono 135 soluzioni base 
(escludendo R&R). In tutte per la colonna e la riga centrali restano 
invariati i numeri 38,42,.....42,38.
Chiamando i primi due elementi in alto a sx = A e B:
A puo' variare da 18 a 24 con B=(53-A)....69
A puo' variare da 25 a 30 con B=29....(93-A)
Le relazioni degli altri valori, per i primi due quadranti, sono:
A	B	92-B	45-A
122-A-B	30-A	A-15	A+B-53
A+B-30	A-15	68-A	103-a-b
45-A	69-B	B-19	A+2	
A-3	B-6	98-B	48-A
93-A-B	33-A	A-18	A+B-24
A+B-43	A+20	33-A	116-A-B
50-A	79-B	B-29	A-3
I quadranti opposti sono speculari ai primi due.

 Ma come l'hai tirata fuori?
Risolvendo il sistema di 80 equazioni... che per il computer è uno
scherzo. Nel dettaglio, ho chiamato x[i,j] il numero di mosse effettuate
sulla casella di coordinate (i,j) e ho creato (con Mathematica) una
lista che contiene le somme delle cinque caselle vicine:
somme = Flatten[
   Table[x[i, j] + x[i-1, j] + x[i+1, j] + x[i, j-1] + x[i, j+1], 
          {i, 1, 9}, {j, 1, 9}]];
dalla quale però devo togliere le caselle che sono "fuori dal bordo":
somme = somme /. 
         {x[0, _] -> 0, x[_, 0] -> 0, x[10, _] -> 0, x[_, 10] -> 0};
Ad esempio, il primo elemento di questa lista è 
x[1, 1] + x[1, 2] + x[2, 1], e così via. Adesso basta trovare i valori
di x[i,j] che fanno diventare uguali tutte queste somme, cosa che
Mathematica fa in un amen:
sol = Solve[Equal @@ somme]
Devo dire che mi spunta un messaggio di avvertimento che dice che
potrebbero mancare delle soluzioni, ma questo è normale trattandosi di
un sistema sottodeterminato; mi fido del fatto che in genere viene data
la soluzione più generale, ma qui ovviamente volendo bisognerebbe fare
qualche ragionamento per averne la certezza. Vado avanti fiducioso e
vedo che la soluzione trovata (che non riporto per esteso) mi presenta
tutte le incognite in funzione di altre tre: x[9,3], x[9,4] e x[9,5].
Posso inoltre vedere il valore comune della somma:
(somme/.sol)[[1,1]]
(61/19) x[9,5]
che dipende quindi solo da x[9,5]. Comincia ad essere chiaro che x[9,5]
deve essere un multiplo di 19, ma ispezionando la soluzione si vede che
contiene termini del tipo:
x[9,1] = -x[9,4] + (45/38) x[9,5]
quindi x[9,5] deve essere almeno 38 affinché tutte le soluzioni siano
intere. Un'occhiata approfondita a tutti i termini rivela che in effetti
38 funziona; una volta posto x[9,5]=38 non rimane che scegliere x[9,3] e
x[9,4] in modo che tutte le soluzioni siano interi non negativi. Ho
fatto un po' di prove e ho visto che 
x[9,4] = 15 e x[9,3] = 29   
andava bene (probabilmente si possono scegliere altre combinazioni), il
che mi dà la soluzione che ho postato. That's all!
BTW: la cosa si può ripetere senza grandi sforzi anche per scacchiere
più grandi; l'unica cosa delicata è la scelta finale affinché tutte le
incognite siano interi non negativi, ma con un po' di buona volontà si
potrebbe automatizzare pure quello, presumo. Inoltre esistono anche
soluzioni simmetriche come quella che cercavi tu: questa è solo la prima
che ho trovato, tutto lì.
Maurizio