Problema cino/vicentino: tassellazioni 2x1 di un 8x8

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
HarryPotter
Moderatore
Messaggi: 354
Iscritto il: 01 gen 1970, 01:00
Località: Pavia

Problema cino/vicentino: tassellazioni 2x1 di un 8x8

Messaggio da HarryPotter » 10 feb 2009, 23:16

Premessa saltabile:

Oggi ho fatto una lezione di combinatoria + teoria dei numeri a Vicenza. Come esempio di colorazione ho fatto il classico problema che mostra l'impossibilità di tassellare con 31 pezzi 2x1 una scacchiera 8x8 a cui sono stati tolti lo scacco in alto a sinistra e quello in basso a destra (per chi non lo sapesse coloro a scacchiera: i pezzi 2x1 tolgono ognuno uno scacco bianco e uno nero, quindi 31 di loro tolgono 31 neri e 31 bianchi, mentre gli scacchi che abbiamo tolto sono dello stesso colore quindi ho 32 neri e 30 bianchi oppure 30 neri e 32 bianchi).

Durante la pausa mi si avvicina una delegazione di due persone: Angela, detta Angila e una simpatica ragazza del classico dagli occhi a mandorla (presumo di orgini cinesi, da cui il titolo del topic) di nome Maz Dong o qualcosa di simile. Le due ragazze mi hanno chiesto il problema qua sotto.

Io non ho la più pallida idea di come risolverlo. Induzione? Ho promesso loro che l'avrei postato qua. Voi ce la fate? Orsù, so benissimo che quando si tratta di aiutare due donzelle in difficoltà matematica non vi tirate mai indietro! :wink: Ricchi premi e cotillons per chi risolve.

Fine premessa

Problema:

In quanti modi posso tassellare una scacchiera 8x8 con dei pezzi 2x1? La scacchiera è supposta con gli scacchi numerati (a1 a2.... h8 ), quindi una rotazione cambia la tassellazione.

Edit: Jordan mi ha appena mandato un messaggio privato, scrivendomi che il problema dovrebbe essere tutt'altro che facile da risolvere. Aspettiamo lumi da qualcuno che ne sa qualcosa. Intanto suggerisce anche di dare un'occhiata qui.

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 13 feb 2009, 04:50

Per la 8x8 non so, ma la 4x8 si tassella in 1782 modi.
Ho risolto mezzo problema, quindi mi spetta una delle 2 ragazze, no? :roll:


Btw, il problema nell'altro thread è tratto dall'Engel.

Avatar utente
HarryPotter
Moderatore
Messaggi: 354
Iscritto il: 01 gen 1970, 01:00
Località: Pavia

Messaggio da HarryPotter » 13 feb 2009, 12:04

Tibor Gallai ha scritto:Per la 8x8 non so, ma la 4x8 si tassella in 1782 modi.
Non so perché, ma questo risultato mi puzza di computer. Almeno finché non avrò visto come ci sei arrivato...:roll:
Tibor Gallai ha scritto:Ho risolto mezzo problema, quindi mi spetta una delle 2 ragazze, no? :roll:
No.

Ale90
Messaggi: 135
Iscritto il: 14 mar 2007, 18:46
Località: Genova

Messaggio da Ale90 » 13 feb 2009, 14:14

Tibor Gallai ha scritto:Per la 8x8 non so, ma la 4x8 si tassella in 1782 modi.
Ho risolto mezzo problema, quindi mi spetta una delle 2 ragazze, no? :roll:
Scusate l'OT, ma non trovo più il mio aspirapolvere... :roll:

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 13 feb 2009, 15:03

HarryPotter ha scritto:Non so perché, ma questo risultato mi puzza di computer. Almeno finché non avrò visto come ci sei arrivato...:roll:
Eh, in quel caso avrei risolto il problema completo. Soprattutto, in quel caso sarebbe un risultato giusto, cosa che dubito. (EDIT: appunto, rifacendo bene i calcoli mi viene 2030. :D)
Il modo in cui ci sono arrivato non ha molto di istruttivo o illuminante, ho tassellato qualche classe di rettangoli "significativi" più piccoli, ho diviso il 4x8 a metà in 4x4 + 4x4, ed ho contato rispetto al numero di tasselli che attraversano la linea di separazione. Questi tasselli possono essere solo 0, 2 o 4, per un totale di 5 casi diversi da trattare, che non sono nemmeno molti. Per la simmetria della figura, basta in realtà tassellarne solo metà, e farne il quadrato in tutti e 5 i casi: questo è un bel vantaggio. Per esempio, con 0 tasselli che attraversano la linea, abbiamo 2 quadrati 4x4 da tassellare. Poiché sappiamo che un quadrato 4x4 si tassella in 35 modi, l'"addendo parziale" che otteniamo qui è $ 35^2 $. Etc...
Il tutto mi ha preso circa mezz'ora (più altri tentativi a vuoto di attaccare l'8x8).
La cosa più notevole (e stranota) che ho trovato è che le tassellazioni dei 2xn sono i numeri di Fibonacci.

In ogni caso, ci tengo a far notare che già per l'8x8 l'uso della calcolatrice, se non proprio del computer, è quasi d'obbligo, visti i numeri in gioco.
Avendo molta voglia, un algoritmo lineare per contare le tassellazioni delle scacchiere 8xn si trova... O anche per le kxn, con k costante qualsiasi. Infatti basta tassellare in tutti i modi possibili un "lato" lungo k, ed esplicitare una ricorsione lineare (sort of... lineare "per casi", in realtà) che avrà un numero di termini dipendente solo da k e non da n (ma purtroppo esponenziale in k). Però non mi pare un approccio particolarmente attraente, sebbene computazionalmente eccelso...

carlop
Messaggi: 13
Iscritto il: 16 gen 2008, 06:45
Località: Pisa

Messaggio da carlop » 05 apr 2009, 03:25

Su wiki come al solito si trova più o meno di tutto: http://en.wikipedia.org/wiki/Dimer_model

Sembra che la scacchiera 8x8 sia tassellabile in 12988816 modi, ma non credo esista una dimostrazione "olimpica"..

Rispondi