Pagina 1 di 1
Piastrellare un quadrato
Inviato: 01 mar 2009, 20:10
da zirklaf
Dimostra che è possibile tassellare con dei tetramini (c) un quadrato di lato $ 2^n $ a cui è stata tolta una casella.
Per tetramino (c) intendo un quadrato 2*2 senza un qualsiasi quadretto.
Per maggiore chiarezza lo metto in allegato.
Ciao,
zirklaf
Inviato: 01 mar 2009, 21:09
da Enrico Leon
Ma non sono questi i tetramini.......
Inviato: 01 mar 2009, 22:35
da SkZ
tetra=4 ergo un tetramino e' composto da 4 quadretti (i pezzi del tetris)
il tuo e' un triomino, ma manca quello coi 3 quadretti allineati
Inviato: 01 mar 2009, 23:40
da Fedecart
Ci provo...
Colorando il quadrato come una scacchiera ci si accorge che il nostro "pezzo" (poi come vogliamo chiamarlo è indifferente) in qualunque modo sia messo copre due caselle di un colore e una di un altro. Ora togliendo una casella al quadrato esso avrà k caselle di un colore, diciamo il nero, e k-1 bianche. Ogni due piastrelle tolgono lo stesso numero di bianchi e neri, ma l'ultima, se il numero di piastrelle è dispari toglie due caselle di un colore e una di un altro, quindi funziona.
Dimostriamo ora che il numero di piastrelle e dispari. Equivale a dire che l'equazione $ 3k= 2^{2n}-1 $ ha sempre soluzione, ovvero $ 2^{2n}-1\equiv 0 (\mod 3) $ per ogni n. Il che è vero perchè $ 2^{2n} \equiv 1 (mod 3) $
Fatemi sapere se qualcosa non va! =)
Inviato: 02 mar 2009, 00:17
da Tibor Gallai
Eh, non hai dimostrato che è piastrellabile.
Hai dimostrato che se è piastrellabile, le piastrelle sono dispari.
In genere, argomenti come colorazioni e conteggi di parità si usano per dimostrare che una cosa
non è piastrellabile.
Inviato: 02 mar 2009, 12:19
da Veluca
proviamo per induzione: per n=1 ovviamente ci si riesce
se è piastrellabile per n, lo è anche per n+1: infatti basta riempire la zona "nuova" con 3 copie del quadrato $ 2^n $, ruotate in modo che i quadrati tolti si trovino tutti affiancati.
Allego un'immagine per chiarezza ^^'... quello in verde è il quadrato tolto, quelli in rosso sono i "tetramini" che si formano con i quadrati tolti affiancati
Inviato: 02 mar 2009, 14:24
da Haile
Veluca ha scritto:infatti basta riempire la zona "nuova" con 3 copie del quadrato $ 2^n $, ruotate in modo che i quadrati tolti si trovino tutti affiancati.
Non ho capito:
"basta riempire la zona nuova con 3 copie in modo che
i quadrati tolti si trovino tutti affiancati"
Non hai dimostrato che è sempre possibile farlo...
per n=1 il quadretto tolto è in basso a destra, mettiamo. Se metti 4 tetramini come dici tu, ottieni un 4x4 con un buco di mezzo, che riempi di un altro tetramino. E quindi hai un quadrato 4x4 con un buco nella casella di coordinate (3,3), poniamo. Ora, per poter ripetere il passaggio riempiendo il quadrato di 8x8, devi dimostrare che è possibile ricondurre il tuo 4x4 piastrellato ad uno con una piastrellazione che faccia rimanere un buco in una casella sull'angolo... e che questo si può fare con tutte le configurazioni successive.
Inviato: 02 mar 2009, 15:01
da SkZ
E' giusto
per tapezzare n+1 si prendono 4 piastrellature n di cui la sup sx ruotata di 90gradi in senso orario e la inf dx ruotata di 90 gradi in senso antiorario. Noterai che i 3 buchi al centro formano un triomino (non tetramino) e nell'angolo in alto a dx rimano il quadrato tolto
Inviato: 02 mar 2009, 15:13
da Veluca
ruotando i quadrati di lato $ 2^a $ è possibile far occupare al quadrato verde una qualsiasi posizione
(se ruoti il quadrato di lato 2 puoi far occupare tutte le 4 posizioni al quadrato verde, se ruoti quello di lato 4 il quadrato 2x2 può finire ovunque e di conseguenza quello verde, etc)
Inviato: 02 mar 2009, 15:35
da Haile
LoL
si, grazie, ora ho capito. In effetti bastava farsi 2 disegni per vedere che non c'è nulla di complicato nel fare configurazioni con il buco nell'angolo; mi ero incasinato un po' immaginandomi tutto a mente
Inviato: 02 mar 2009, 16:43
da Tibor Gallai
Sì, ma avete dimostrato soltanto che la tassellazione è possibile se il quadratino tolto è in un angolo. Ma zirklaf non ha specificato dove vada tolto il quadratino!
Poco male, la soluzione di Veluca si generalizza facilmente.
Inviato: 02 mar 2009, 16:58
da Veluca
Veluca ha scritto:ruotando i quadrati di lato $ 2^a $ è possibile far occupare al quadrato verde una qualsiasi posizione
(se ruoti il quadrato di lato 2 puoi far occupare tutte le 4 posizioni al quadrato verde, se ruoti quello di lato 4 il quadrato 2x2 può finire ovunque e di conseguenza quello verde, etc)
non basta per dire che si può ottenere il quadratino verde in una qualsiasi posizione?
Inviato: 02 mar 2009, 17:20
da SkZ
direi di si.
volendo si dimostra pure quello per induzione
Inviato: 02 mar 2009, 17:20
da Tibor Gallai
Veluca ha scritto:non basta per dire che si può ottenere il quadratino verde in una qualsiasi posizione?
Ah, non avevo letto quel post!!
Sì, per dirla leggermente meglio (ma va bene!), per ipotesi induttiva puoi mettere il quadratino dove vuoi nel quadratone da $ ~\displaystyle 2^{n-1} $. Ora, togliendo un quadratino dal $ ~\displaystyle 2^n $, esso deve trovarsi in uno dei 4 sotto-quadrati da $ ~\displaystyle 2^{n-1} $. Tappezzi gli altri 3 come hai fatto, e poi tappezzi il 4° in modo da togliere il quadratino nel punto giusto.