orientarsi tra le tri-tessere

[phi]

Uhm, visto che nell'ultimo problema di tasselli su questo forum si parlava di tetris e tetramini, ecco qua un problemino coi trimini...
(E non mi venite a dire cose come "ahah, ma è noto, è stato postato sul forum e risolto circa 2000 anni fa", ok? )

Data una scacchiera da dama formata da $ 2^n \times 2^n $ quadrati, togliamo uno di questi quadrati. Mostrare che è sempre possibile ricoprire esattamente questa scacchiera con tessere "a L" da tre quadrati.

(Fonte, lo stand del corso di matematica al "Salone dello Studente" di Pisa, un po' di tempo fa... ti regalavano pure la maglietta se risolvevi qualche problema
P.S. Oh, mi raccomando, 'sta qua è chiaramente roba per olimpicamente giovani, magari giovanissimi... se uno pensa "ma che cazzata" magari non posti la sol )

[jim]

Visto chre nessuno posta, lo faccio io...
Lemma 1)è possibile tassellare con 4 trimini a l una figura che abbia la stessa forma del trimino a l ma con lati lunghi il doppio. La dimostrazione è grafica, fai conto che qui sotto ci sia il disegno, trovarla è banale. Per induzione affermiamo che è possibile pastrellare anche figure simili con i lati lunghi $ 4, 8, 16, ...2^k $ volte.

step i): -numero righe e colonne la scacchiera quadrata da $ 1 $ a $ 2^n $ da sx verso dx e dall'alto verso il basso in modo da poter definire ogni casella con una coppia di numeri.
- abbia il quadratino tolto coordinate $ (a;b) $ (dove $ a $ è la riga e $ b $ è la colonna) : noi vogliamo posizionare un trimino "attorno" al quadratino, cioè che l'unione del trimino e del quadratino sia un quadrato 2x2. Ora, questo lo possiamo fare in quattro modi.
-di questi quattro, ne scegliamo uno, definito così:
sia $ h $ il quadratino centrale del trimino, allora:
-se $ a $ è p. e $ b $ è p. $ \longmapsto $ $ h:=(a-1;b-1) $
-se $ a $ è p. è $ b $ è d.$ \longmapsto $ $ h:=(a-1;b+1) $
-se $ a $ è d. è $ b $ è p.$ \longmapsto $ $ h:=(a+1;b-1) $
-se $ a $ è d. è $ b $ è d.$ \longmapsto $ $ h:=(a+1;b+1) $
così facendo avremo in ogni direzione del quadrato 2x2 un numero pari di caselle.

step ii): a questo punto cambio il "sistema di riferimento della scacchiera" considerando ora come caselle i quadratini 2x2 (posso farlo, visto che la scacchiera originale ha $ 2^n $ caselle) e considerando come casella "vuota" il quadrato 2x2 definito nello step i). Ora mi ritrovo con lo stersso problema di prima per una scacchiera di $ 2^{n-2} $ caselle.

Grazie al lemma 1), posso ripetere lo step i), e quindi definire un nuovo quadrato "vuoto" 4x4, per poi procedere con lo step ii) ecc. Ripetendo questo procedimento si giungerà in un numero finito di mosse ad aver piastrellato tutta la scacchiera.

Ciao!
Edo

[Sisifo]

Tanto per cambiare... era già stato postato da EvaristeG e risolto (da me!) nel vecchio forum... Comunque posto la mia soluzione.

Si risolve per induzione, il passo n=1 è banale (e anche quello n=0, come mi faceva giustamente notare marco).
Se è possibile tassellare una scacchiera $ 2^n x 2^n $ , vediamo se è possibile farlo anche nel caso n+1..
Dividiamo la scacchiera in quattro quadranti, sia $ Q_1 $ quello che contiene il quadrato tolto. Si tratta di un quadrato $ 2^n x 2^n $ cui è stato tolto un quadratino, perciò è possibile tassellaro completamente per il passo induttivo. Agli altri tre quadranti rimuoviamo i quadratini che si trovano più vicini al centro della scacchiera e li riempiamo con un trimino a L. Lo spazio rimanente dei tre quadranti può essere così riempito per il passo induttivo. CVD

Ciao!