Newsgroup: it.hobby.enigmi
Titolo: domino&quadrati

Ricordate le pedine del domino ?
Allora vorrei sapere se esiste una formula per calcolare
tutte le possibili disposizioni di k pedine (2x1 caselle)
in quadrati di lato n (ovviamente con n pari).
Io non ho trovato di meglio che scrivere un piccolo
algoritmo di ricerca esaustiva. Qualcuno sa dirmi come
procedere nel migliore dei modi ?
Numerando le pedine del domino in modo da averle tutte
con numeri simmetrici (ad esempio dato il quadrato da 4x4
numerare le 8 pedine come segue : 1-16 2-15 ....7-10 8-9)
si possono ottenere quadrati magici ?
Massimo

 in quadrati di lato n (ovviamente con n pari).
Ho fatto piccoli progressi ed ho trovato che :
1) I quadrati devono essere di lato pari
2) Il numero di pedine e' : k = lato*lato/2
3) Il numero di mosse possibili e' : m = 2*lato*(lato-1)
Quindi adesso per calcolare le possibili disposizioni uso la seguente :
m! / ((m-k)!*k!)     ovvero tutte le possibili mosse prese solo k volte,
avendo cura di scartare le combinazioni che danno una sovrapposizione
di pedine !
Per il quadrato di lato 2 e' banale, per il quadrato di lato 4 ho
trovato
36 disposizioni considerando anche quelle simmetriche.
Ancora non ho provato con il quadrato da 6, per il quale avremo :
60 mosse possibili
18 pedine
 9,250295657411e+14 disposizioni possibili !!!
Possibile che non si possa fare meglio ?!?!
Qualcuno ha avuto una *brillante* idea ?!?
Massimo

 Massimo
Ciao Massimo,
se non ricordo male, la formula per un rettangolo m * n e'
prod(prod((cos(i * Pi / m) * cos(j * Pi / n))^(1/4)) * 2 ^(m * n/2)
dove i due prodotti coprono tutte le combinazioni i = 0 .. n - 1 e j = 0
.. m - 1.
Cosa c'entrano i coseni? Non chiedermelo!
se il rettangolo e' 2 x m,  saltano fuori i numeri di Fibonacci.
Guarda anche
http://www.astro.virginia.edu/~eww6n/math/math.html
alla voce Domino,
Ciao
Mauro Fiorentini

 Mauro Fiorentini
Cacchio !!!
Io non solo ti chiedo cosa c'entrano i coseni ma ti chiedo di piu' !!
Il sito lo vado a guardare subito ma intanto :
"Come vien fuori 'sta formula o meglio formulone ?
E poi come si potrebbe passare all'analisi dei quadrati ?"
In attesa, saluti
Massimo

 E poi come si potrebbe passare all'analisi dei quadrati ?"
sostituisci m = n e ti ritrovi:
prod(prod((cos(i * Pi / (n+1))^2 + cos(j * Pi / (n+1))^2)^(1/4)) * 2 ^(n^2/2)
Ecco i primi valori:
2    2
4    36
6    6728
8    12988816
10    258584046700
asintoticamente tende a K^(2*n^2), dove K = exp(2*G/Pi) ~=1.791622812
e G e' la costante di Catalan (cosa c'entra? E lo chiedi a me?)
Se conti anche le coperture msite di domini e caselle singoli, K ~= 3.7644356,
ma non se ne conosce il valore esatto.
Cerca anche sull'Enc. delle sequenze di interi.
Versione in linea a:
http://www.research.att.com/~njas/sequences/eisonline.html
Sequenza M2160
Puoi guardare anche:
http://www.mathsoft.com/asolve/constant/catalan/dimer.html
Nei paraggi trovi anche una breve discussione del caso tridimensionale.
Che io sappia il problema generale e' insoluto con i trimini (1 x 3), mentre
per
rettangoli 3 x n e 4 x n si affronta facilmente (V. Golomb).
Ciao
Mauro

> Massimo Mondò wrote:
 > Cacchio !!!
Ti ha gia' detto tutto Mauro.
Puoi dare un'occhiata qui. Riporta parecchi articoli sull'argomento, e
spiega qualcosa sulla formula:
http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/domino