Newsgroup: it.hobby.enigmi
Titolo: Scacchiera

Qual'e' il massimo numero di pezzi tutti differenti che si possono
ottenere tagliando una scacchiera 8*8 lungo i bordi delle caselle?  
I pezzi possono essere differenti per forma o per colore. Di caselle
singole ad es. ne posso ricavare solo 2, una bianca ed una nera, di
domino soltanto 1 ecc..
Una volta stabilito il num. massimo di pezzi ottenibili, trova una
soluzione dove nessun pezzo e' formato da piu' di 5 caselle.
ciao :)dario

Dario Uri wrote:

Ottimo problema, Dario
Mi sembra complicato.
Non credo sia nota una formula per il numero di pezzi, dato il lato
della scacchiera,
perche' ho la sensazione che "conterrebbe" una formula per il numero di
polimini
di un dato ordine, che non e' ancora stata trovata.
Pero' enumerare le soluzioni e' un'impresa impossibile, senza un
calcolatore, e
forse difficile anche usandolo.
Vi sono oltre 500 polimini fino a 8 celle, molti dei quali vanno contati
2 volte,
per via dei colori. Oltre le 8 celle alcuni sono troppo lunghi o larghi
per entrare
nella scacchiera, ma la maggioranza sara' valida. Il numero di polimini
a 24
celle ha gia' 12 cifre e azzarderei che il numero di soluzioni a questo
problema
abbia tra le 12 e le 15 cifre. Carta e penna non bastano.
Il numero e' sicuramente inferiore al numero di sottoinsiemi di caselle:
2^64;
anche dividendo per 4 per eliminare rotazioni e riflessioni, resta un
limite superiore
di 4*10^18 circa.
Ci vuole un'idea MOLTO astuta. Rinuncio. :-(
Ciao
Mauro Fiorentini

 Ci vuole un'idea MOLTO astuta. Rinuncio. :-(
Scusate, forse mi sono spiegato male. 
Provo cosi': Quale' il massimo numero di pezzi, tutti differenti, tali
che , se avvicinati (non sovrapposti) possono formare una scacchiera.
Non e' cosi' difficile.
In altre parole, se ad es. volessi sezionare una scacchiera in 30
polimini, non potrebbero essere tutti diversi fra loro.
:( dario

ciao :)dario
Quanto piu' piccoli saranno i pezzi, tanto maggiore sara' il loro numero; se
non ci fosse la limitazione di dover avere tutti pezzi differenti, si
avrebbe la soluzione banale con 64 pezzi singoli.
Dovendo necessariamente avere pezzi maggiori dei singoli, il max diminuisce.
Non ho trovato la soluzione, ma alcuni valori limite di 18 (o 17) pezzi, a
seconda che siano ammissibili o meno pezzi speculari.
Accettando i pezzi speculari, posso avere:
2 singoli
1 domino
4 trimini (due lineari e due ad angolo)
8 tetramini (uno lineare, quattro ad L, due a Z, un quadrato)
utilizzando tutti questi 15 pezzi, copro 48 caselle; ne rimangono 16 che
posso coprire con due pentamini ed un esamino (si dice cosi?), in tutto 18
pezzi.
Eliminando l'esamino ed un tetramino, e sostituendoli con due pentamini,
ottengo sempre il valore di 18 pezzi.
Se i pezzi speculari non sono ammissibili, i dati diventano:
2 singoli
1 domino
4 trimini (due lineari e due ad angolo)
5 tetramini (uno lineare, due ad L, uno a Z, un quadrato)
quindi 12 pezzi per 36 caselle.
Rimangono 28 caselle che posso coprire con 4 pentamini ed un ottomino, in
tutto 17 pezzi.
Elimino l'ottomino ed un domino, e li sostituisco con altri due pentamini,
ho sempre 17 pezzi di non piu' di 5 casele.
Non so se le soluzioni proposte siano realmente praticabili, ma i valori
ottenuti dovrebbero essere i limiti max, in quanto ogni altra
soluzione,dovendo utilizzare pezzi piu' grossi, dara' ncessariamente valori
minori o uguali a 18 (17).
ciao
paolo

 minori o uguali a 18 (17).
Perfetto, e' proprio quello che intendevo. Le immagini speculari sono
ammesse, cosi' e' possibile ottenere il sezionamento in 18 pezzi es:
01 02 02 02 03 04 05 06
01 01 02 03 03 04 05 07
01 11 11 03 04 04 09 08
11 11 10 10 10 10 09 08
12 12 12 13 13 13 09 08
14 14 12 13 15 16 16 17
14 14 15 15 15 16 17 17
18 18 18 18 18 18 18 18
Dove e' impiegato l'ottamino. La sfida era appunto trovare una soluzione
con pezzi di 5 caselle max.
ciao dario