Piastrellare un quadrato

[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

[Enrico Leon]

Ma non sono questi i tetramini.......

[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

[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! =)

[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.

[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

[Haile]

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.

[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

[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)

[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

[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.

[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)

non basta per dire che si può ottenere il quadratino verde in una qualsiasi posizione?

[SkZ]

direi di si.
volendo si dimostra pure quello per induzione

[Tibor Gallai]

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.