Piastrellare un quadrato

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
zirklaf
Messaggi: 3
Iscritto il: 25 feb 2009, 19:32
Località: Bologna

Piastrellare un quadrato

Messaggio da zirklaf » 01 mar 2009, 20:10

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
Allegati
C_tetramino.pdf
(10.48 KiB) Scaricato 215 volte

Enrico Leon
Messaggi: 237
Iscritto il: 24 nov 2008, 18:08
Località: Gorizia

Messaggio da Enrico Leon » 01 mar 2009, 21:09

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

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 01 mar 2009, 22:35

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

Avatar utente
Fedecart
Messaggi: 522
Iscritto il: 09 mar 2008, 22:49
Località: Padova

Messaggio da Fedecart » 01 mar 2009, 23:40

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
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 02 mar 2009, 00:17

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
Messaggi: 185
Iscritto il: 27 dic 2008, 01:08
Località: Chiavari (Genova)

Messaggio da Veluca » 02 mar 2009, 12:19

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
Allegati
quadrato 2^n.jpeg
quadrato 2^n.jpeg (8.42 KiB) Visto 2593 volte

Avatar utente
Haile
Messaggi: 515
Iscritto il: 30 mag 2008, 14:29
Località: Bergamo

Messaggio da Haile » 02 mar 2009, 14:24

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.
[i]
Mathematical proofs are like diamonds: hard and clear.

[/i]

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 02 mar 2009, 15:01

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

Veluca
Messaggi: 185
Iscritto il: 27 dic 2008, 01:08
Località: Chiavari (Genova)

Messaggio da Veluca » 02 mar 2009, 15:13

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)

Avatar utente
Haile
Messaggi: 515
Iscritto il: 30 mag 2008, 14:29
Località: Bergamo

Messaggio da Haile » 02 mar 2009, 15:35

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 :roll:
[i]
Mathematical proofs are like diamonds: hard and clear.

[/i]

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

Messaggio da Tibor Gallai » 02 mar 2009, 16:43

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
Messaggi: 185
Iscritto il: 27 dic 2008, 01:08
Località: Chiavari (Genova)

Messaggio da Veluca » 02 mar 2009, 16:58

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?

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 02 mar 2009, 17:20

direi di si.
volendo si dimostra pure quello per induzione
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

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

Messaggio da Tibor Gallai » 02 mar 2009, 17:20

Veluca ha scritto:non basta per dire che si può ottenere il quadratino verde in una qualsiasi posizione?
Ah, non avevo letto quel post!! :oops:
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.

Rispondi