Piastrellare un quadrato
Piastrellare un quadrato
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
Per tetramino (c) intendo un quadrato 2*2 senza un qualsiasi quadretto.
Per maggiore chiarezza lo metto in allegato.
Ciao,
zirklaf
- Allegati
-
- C_tetramino.pdf
- (10.48 KiB) Scaricato 398 volte
-
- Messaggi: 237
- Iscritto il: 24 nov 2008, 18:08
- Località: Gorizia
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
il tuo e' un triomino, ma manca quello coi 3 quadretti allineati
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
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! =)
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! =)
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
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
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
- Allegati
-
- quadrato 2^n.jpeg (8.42 KiB) Visto 4926 volte
Non ho capito: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.
"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.
[i]
Mathematical proofs are like diamonds: hard and clear.
[/i]
Mathematical proofs are like diamonds: hard and clear.
[/i]
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
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
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
non basta per dire che si può ottenere il quadratino verde in una qualsiasi posizione?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)
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Ah, non avevo letto quel post!!Veluca ha scritto:non basta per dire che si può ottenere il quadratino verde in una qualsiasi posizione?
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.