Trimini inculcati

[MindFlyer]

Un L-trimino è una figura ottenuta prendendo un quadrato 2x2 e rimuovendo un quadratino 1x1 da un angolo.
Nel piano sono disposti 2005 L-trimini, in modo che il quadratino rimosso da ogni L-trimino è coperto da un altro L-trimino. Dimostrare che è possibile togliere un L-trimino in modo da preservare questa proprietà.

[Marco]

Bellino!

Rilancio: chiamo un insieme di trimini inculcato se ogni quadrato rimosso da un trimino è coperto da un altro trimino. Chiamo un insieme conculcato se è inculcato, ma ogni suo sottoinsieme proprio di trimini non lo è.

Per quali n esiste un insieme conculcato di n trimini?

[piever]

Provo a dimostrare quello di MindFLyer: i L-trimini si abbinano a 2 a 2 in 1002 coppie (a forma di rettangolo 2x3), il L-trimino residuo viene incastrato sul bordo: togliendo quel L-trimino si mantiene la proprietà di inculcazione...ehm, forse inculcatezza(???). Ciò è sempre possibile in qualsiasi modo siano disposti i 2005 L-trimini, perché un qualsiasi gruppo tale che, togliendo da esso un L-trimino a scelta, non è più inculcato, è pari, quindi se la quantità di L-trimini è dispari, come in questo caso, per forza ne va aggiunto uno che non copre nessun buco di altri L-trimini, togliendo il quale l'insieme resta inculcato.

Marco, potresti chiarire la definizione di conculcato: cos'è un sottoinsieme proprio di trimini?

[edriv]

Sottoinsieme proprio significa che devi togliere almeno un trimino.

[piever]

Allora un conculcato di n trimini esiste con n=2 (data una qualsiasi disposizione ogni sottoinsieme non è inculcato).

[edriv]

Sì ma lo puoi trovare anche con n più grandi... prova a disporli come in un cerchio uno che copre l'altro. Almeno credo di esserci riuscito, ma ora non ho tempo di completare gli esperimenti.

[piever]

Sì, hai ragione, ad esmpio funziona anche con 4. Sono fuso adesso, provo a determinare tutti i numeri domani.
Ciao

[Marco]

L-trimini si abbinano a 2 a 2 in 1002 coppie (a forma di rettangolo 2x3)

Questo è, in generale, falso.

la proprietà di inculcazione...ehm, forse inculcatezza(???)

Boh?! Che ne dite di inculcanza??

Marco, potresti chiarire la definizione di conculcato: cos'è un sottoinsieme proprio di trimini?

Un insime conculcato è un insieme inculcato minimale (cioè che non contiene insiemi inculcati [non vuoti] più piccoli): se togli una sua parte non è più inculcato.

Esempio di insieme inculcato, ma non conculcato: due coppie di trimini che formano due blocchi 2x3 disgiunti. E' inculcato, perché ogni trimino ha il suo partner che ne riempie l'angolo concavo. Non è conculcato, perché se prendi un solo blocco 2x3, trovi un insieme inculcato più piccolo.

Invece il blocco 2x3 è conculcato: se togli una sua parte (e l'unica possibilità è togliere un trimino) resta un trimino da solo, che non è chiaramente inculcato.

Meglio?

Sottoinsieme proprio significa che devi togliere almeno un trimino.

Per essere pign... precisi, significa, "devi togliere almeno un trimino, ma non tutti". L'insieme vuoto con zero trimini è un esempio banale di insieme inculcato. Se si ammettessero i sottoinsiemi vuoti, solo l'insieme vuoto sarebbe conculcato, rendendo stupida la definizione...

[piever]

L-trimini si abbinano a 2 a 2 in 1002 coppie (a forma di rettangolo 2x3)

Questo è, in generale, falso.

Sì, hai ragione, era un esempio idiota. Il punto è che non esistono n dispari conculcati: gli insiemi conculcati sono tutti pari. Per comodità definisco semiconculcato un insieme n tale che, togliendo da esso un trimino a scelta, resta inculcato (e.g. 2005), tutti gli insiemi dispari sono sempre semiconculcati. Si dimostra notando che non esistono n dispari conculcati: quindi ogni insieme inculcato dispari è composto da k, dove $ 0\leq k \leq {\frac{n-1}{2} $, insiemi conculcati pari + l insiemi dispari dove l è dispari.
Passiamo ora a determinare gli insiemi conculcati: il più piccolo conculcato è ovviamene 2 (rettangolo 2x3), quindi segue 4 disponendo i trimini facendoli ruotare su un punto fisso (non è molto chiaro ma se ci provate ve ne rendete conto, viene una specie di croce greca). In ogni insieme conculcato ciascun trimino copre almeno un buco, per definizione. Nessun trimino copre due buchi, altrimenti resterebbe un trimino che non ne copre alcuno. Insomma ogni trimino copre un buco e il suo buco è coperto da un altro trimino. Ciò è impossibile se il numero di trimini è dispari.

[edriv]

Provo a scrivere le mie (probabilmente inutili) divagazioni sul problema di Marco:

Per fare in modo che ogni sottoinsieme ottenuto togliendo un solo trimino sia ancora consulcato, deve essere che:
- ogni trimino ha il suo buco occupato da un (solo) trimino
- ogni trimino copre il buco di un trimino.

Consideriamo la struttura dell'insieme T dei trimini.
Verificato che:
- per [ŧex]|T| =1[/tex] non ci sono soluzioni
- per [ŧex]|T| =2[/tex] c'è una soluzione
- per $ |T| = |N| $ si trovano soluzioni
possiamo escludere questi casi (oltre all'insieme vuoto).

Definiamo la funzione "successivo" di un trimino A: il successivo di A è il trimino che copre il buco di A.
Per le osservazioni fatte finora:
- f ha come dominio e codominio T (l'insieme dei trimini).

Dimostro questo lemma:
- in un insieme finito I, ogni funzione suriettiva da I in I è anche iniettiva. Infatti, se non fosse così, esisterebbero due elementi x,y tali che f(x) = f(y). Ma allora la limitazione di f al dominio $ I - {x} $ sarebbe ancora suriettiva, ed avremmo una funzione suriettiva da $ I-{x} $ in I, suo sovrainsieme in senso stretto, quindi I sarebbe infinito, contro l'ipotesi.

Applicando il lemma, otteniamo che ogni trimino ha un solo precedente.

Definiamo la relazione "collegato": a è collegato a b se iterando un n volte (n > 0) la f a partire da b, si ottiene a. Oppure, per ogni a, f(a) è collegato ad a e se x è collegato ad a, anche f(x) lo è.
In T, vale la proprietà riflessiva. Infatti, se così non fosse:
sia A l'insieme degli elementi collegati ad a. f(A) sarebbe un sottoinsieme proprio di A, quindi A sarebbe infinito, il che non è accettabile.
Proprietà simmetrica: se b è collegato con a ed a non è collegato con b, indicando sembre con B l'insieme degli elementi collegati con b, a non è in B ed ogni elemento collegato con a non è in B. MA allora non lo sarebbe nemmeno b, contro la proprietà riflessiva.
Proprietà transitiva: b è collegato ad a, ogni elemento collegato a b è collegato ad a (induzione), quindi anche c.

Questa è una relazione di equivalenza. Dimostriamo che la f è [[come si dice quando $ a R b \LeftRightArrow f(a) R f(b) $ ]] rispetto alla relazione 'collegato'. Sembra molto facile.

Chiamiamo "catena di trimini" ogni classe di equivalenza (sempre in T). Dimostriamo che ogni catena di trimini è conculcata.
Infatti: è inculcata (esiste f(a) che è collegato ad a), se tolgo qualche elemento, almeno uno tra gli elementi rimasti è senza successivo, altrimenti quelli rimasti formerebbero una catena, ma si tratta di classi di equivalenza quindi non vale. Allora è conclulcata.

E finalmente giungiamo alla fine: in T c'è una ed una sola catena. Infatti, se ci fossero più catene, togliendone tutte tranne una, ciò che resta sarebbe conculcato.

Quindi dobbiamo semplicemente trovare una catena.
(so benissimo che quello che ho scritto sarà pieno di errori, sarà già stato scritto su ogni manuale di algebra, e serve ben poco al problema... però è servito a me)

[Marco]

Il punto è che non esistono n dispari conculcati

Grazie tante! "La soluzione è questa perché le cose stanno così".

Provo a scrivere le mie (probabilmente inutili) divagazioni sul problema di Marco:

Tutt'altro! Mi sembra un buon inizio. Anzi, ti dirò di più: il termine "conculcato" è nato proprio da "inculcato" + "connesso".

Magari hai tenuto un po' lunga la dimostrazione, ma è corretta: un insieme conculcato è un "ciclo di trimini".

Poi...?

Per il momento, abbiamo solo tre insiemi conculcati: il vuoto, il blocco 2x3 e la croce greca. Chi offre di più?

[edriv]

A parte che ho trovato catene di trimini conculcati con un numero arbitrariamente grande di trimini (di forma abbastanza quadrata), (ma non so se sono tutti).
A parte che comunque vale la pena di uppare questo problema.

Volevo fare una domanda di algebra (non credo valga la pena di creare una discussione nella sezione dedicata).

Per chi si è preso la briga di leggere questa parte della mia dimostrazione, che ho voluto formalizzare abbastanza:

Dimostro questo lemma:
- in un insieme finito I, ogni funzione suriettiva da I in I è anche iniettiva. Infatti, se non fosse così, esisterebbero due elementi x,y tali che f(x) = f(y). Ma allora la limitazione di f al dominio I - {x} sarebbe ancora suriettiva, ed avremmo una funzione suriettiva da I-{x} in I, suo sovrainsieme in senso stretto, quindi I sarebbe infinito, contro l'ipotesi.

Applicando il lemma, otteniamo che ogni trimino ha un solo precedente.

Definiamo la relazione "collegato": a è collegato a b se iterando un n volte (n > 0) la f a partire da b, si ottiene a. Oppure, per ogni a, f(a) è collegato ad a e se x è collegato ad a, anche f(x) lo è.
In T, vale la proprietà riflessiva. Infatti, se così non fosse:
sia A l'insieme degli elementi collegati ad a. f(A) sarebbe un sottoinsieme proprio di A, quindi A sarebbe infinito, il che non è accettabile.
Proprietà simmetrica: se b è collegato con a ed a non è collegato con b, indicando sembre con B l'insieme degli elementi collegati con b, a non è in B ed ogni elemento collegato con a non è in B. MA allora non lo sarebbe nemmeno b, contro la proprietà riflessiva.
Proprietà transitiva: b è collegato ad a, ogni elemento collegato a b è collegato ad a (induzione), quindi anche c.

Questa è una relazione di equivalenza. Dimostriamo che la f è [[come si dice quando a R b \LeftRightArrow f(a) R f(b) ]] rispetto alla relazione 'collegato'. Sembra molto facile.

Chiamiamo "catena di trimini" ogni classe di equivalenza (sempre in T). Dimostriamo che ogni catena di trimini è conculcata.
Infatti: è inculcata (esiste f(a) che è collegato ad a), se tolgo qualche elemento, almeno uno tra gli elementi rimasti è senza successivo, altrimenti quelli rimasti formerebbero una catena, ma si tratta di classi di equivalenza quindi non vale. Allora è conclulcata.

Ecco, dovrei fare lo stesso ragionamento (con le classi di equivalenza) per dimostrare abbastanza formalmente un altro problema (PreIMO 2006, combinatoria.6).

C'è qualche famoso teorema di algebra che spiega proprio questo?
Io non so niente di gruppi, ma molti di voi sì, e magari lo conoscete (sempre se è un fatto noto). Sarebbe più elegante citare questo che scrivere una pagina di scritte inutili.

[edriv]

No anzi, non serve niente.
C'è già scritto sulle schede del Gobbino che "ogni permutazione si scrive in modo unico come prodotto di cicli", era proprio questo che intendevo. Quindi posso usarlo come fatto noto

Il problema dei trimini è riaperto