OliForum Matematico

Problema simpatico... è possibile ricoprire un rettangolo 5x7 con dei L-trimini (ovvero, facendo un buco un un quadratino 2x2) in modo che:
- i trimini possono sovrapporsi, ma non uscire dal rettangolo
- sopra ogni casella ci sia lo stesso numero di trimini

?

Carino...

A quanto mi risulta è impossibile ma non sono riuscito ad elaborare una dimostrazione convincente!

Diciamo che per ottenere una possibile soluzione chairamente dovremmo coprire il rettangolo con 3 strati di trimini,

-2 strati da 12 trimini (con una casella in cui si sovrappongono)
-1 strato da 11 trimini (con 2 caselle libere)

Chiaramente le 2 caselle di sovrapposizione dei primi due strati dovranno corrispondere alle 2 caselle libere del 3° strato.

Provando a disporre i trimini noteremo che le caselle di sovrapposizione possono trovarsi solo su quelle caselle che hanno almeno una coordinata pari.

Però, in qualsiasi modo si scelgano le caselle libere del 3° strato, inevitabilmente una di esse andrà a cadere su una casella con entrambe le coordinate dispari.




Purtroppo non ho idea di come dimostrare quello che ho affermato...

Up!

Assicuro l'esistenza di una dimostrazione carina e convincente più corta del post di Zoidberg.

L'ho visto in una Cortona 2001 o 2002, se ricordo bene. Confermo che la dim è carina.

Coloro la tabella a scacchiera, in modo che la casella in alto a sinistra sia nera. Faccio poi un'ulteriore 'scacchieramento' colorando di rosso la seconda, quarta e sesta casella della seconda e della quarta riga (queste caselle risulteranno quindi colorate sia di rosso che di nero).
Definisco ora $ k $ il numero di pezzi su ogni casella in un'ipotetica configurazione che soddisfa le ipotesi, $ a $ il numero di pezzi usati che coprono due caselle nere e una bianca, $ b $ quelli che coprono due bianche ed una nera.
In totale i pezzi utilizzati sono: $ 35*k/3=a+b $.
Consideriamo ora i pezzi che coprono due caselle nere; si vede che tali pezzi devono per forza coprire una casella rossa. Ma i pezzi sulle caselle rosse, che sono 6 in totale, sono al massimo $ 6k $; quindi $ a\leq 6k $.
Allora le caselle nere ricoperte saranno in totale $ 1*b+2*a= (a+b)+a=35*k/3+a\leq (17+2/3)k $.
Ma, considerando che le caselle nere sono 18, esse dovrebbero essere ricoperte $ 18k $ volte in totale, quindi si ha un assurdo perche'$ (17+2/3)k<18k $.

Ok! La mia era:
Coloro di nero (considerando la casella in basso a sinistra come (0,0)) tutte le caselle che hanno entrambe le coordinate pari.
Sia k (numero di strati) come definito da Maria.
Ho scelto una colorazione in modo che un tassello non possa passare contemporaneamente sopra due caselle nere! Quindi il numero di tasselli è almeno (k * caselle nere). Le caselle nere sono 12. Quindi ci sono almeno 12k tasselli. Ma d'altra parte sappiamo che il numero di tasselli è k * 35 / 3! Quindi dovremmo avere 12k <= k * 35 / 3, che implica 36 <= 35, assurdo... ammiriamo il bound molto stretto del problema!

Anni fa avevo risolto il problema generale di caratterizzare i rettangoli tassellabili con L-trimini, quindi rilancio con questo:

Elencare i rettangoli "primitivi" tassellabili con L-trimini.

Notare che la richiesta è ben definita perché i rettangoli voluti sono finiti, ed esprimibili come coppie di interi.

Giusto un chiarimento: "tassellare" è da intendere in senso diverso da questo problema, cioè senza sovrapposizioni, no?

Sembra proprio il problema giusto per le lezioni di Promessi Sposi!

Sì, qui tassellare significa senza sovrapposizioni.