Le belle piastrelle di Mamino

[edriv]

Breve storia del problema: questo è stato raccontato durante lo stage senior da Mamino a me e simone (enomis). Siamo stati circa due ore di sera in mensa a pensare su questo, ed è stato uno dei momenti più belli dello stage, assieme al proseguimento della notte quando siamo passati a raccontarlo a Dennis (sisifo) e Pietro (piever) sul terrazzo dell'albergo.
Secondo me sia il problema sia la soluzione sono entrambi bellissimi. Ecco qui il primo, a voi la seconda.


Per pavimentare il piano abbiamo a disposizione delle piastrelle quadrate (di grandezza fissa) . Ogni tipo di piastrella ha ciascun bordo colorato; il numero totale di colori è finito mentre abbiamo una quantità infinita di piastrelle per ogni tipo.
Per un certo senso estetico, però, dobbiamo pavimentare in modo che due piastrelle adiacenti abbiano il lato in comune dello stesso colore.
Ah, inoltre, non le possiamo ruotare o ribaltare: ci sono date già nel verso in cui le dobremo mettere.

Sapendo che con le piastrelle date è possibile pavimentare ogni quadrato, arbitrariamente grande, dimostrare che esiste una pavimentazione per l'intero piano.


Ci ha spiegato che questo è un teorema della logica di primo ordine, del tipo "data una teoria con infiniti assiomi, se esiste un modello per ogni sottoinsieme finito di assiomi, allora esiste un modello per l'intera teoria". Quello delle piastrelle è solo un altro modo per esporlo.

Piever mi ha detto che l'ha risolto ieri durante l'ora di filosofia, esattamente la stessa soluzione trovata a Pisa, ma chiaramente aspetterà un po' prima di mettere qui la soluzione.
Magari anche se non viene subito la soluzione, se trovate o congetturate qualcosa di interessante sul problema scrivete pure!

[MindFlyer]

questo è un teorema della logica di primo ordine

E' uno dei teoremi di compattezza.

[enomis_costa88]

NO..volevo proporlo io questo
Si quella..è stata una delle sere migliori dello stage (prima mamino che smontava quasi tutte le nostre idee, poi la soluzione abbagliante e poi sul terrazzo con pietro e dennis..poveretti li abbiamo fatti un po' impazzire mi sa)

PS: pietro..appena ci si sente su msn mi racconti la tua..

Buon lavoro.

[Sisifo]

Denis

Ancora questo.. Non volete proprio lasciarci dormire! :D:D

[enomis_costa88]

Visto che allora l'avevamo risolto in modo quasi olimpico direi che ora che sono un vecchiaccio puzzone posso usare il teorema di compattezza

Abbiamo i seguenti insiemi di assiomi:

Per ogni $ l \in {1,2,3,4}; i,j \in Z $ ho che:

i) $ A_{i,j,l}\in \{c_1,\dots c_n \} $
e la quadrupla $ (A_{i,j,1},A_{i,j,2},A_{i,j,3},A_{i,j,4})\in $ "insieme delle quadruple ordinate permesse".

e per ogni i,j:
ii) $ A_{i,j,1}=A_{i,j+1,3} $
e
iii) $ A_{i,j,2}=A_{i+1,j,4} $.

Dimostriamo che un qualsiasi insieme finito di assiomi esso ha un modello:
Associo ad ogni A_ij una piastrella e l indica uno dei quattro bordi della stessa piastrella.
La prima serie di assiomi dice come possono essere fatte le piastrelle.
La seconda e la terza serie di assiomi ci dicono che date due piastrelle confinanti il confine deve essere dello stesso colore.

Ora dato un insieme finito di assiomi esso coinvolge un numero finito di "mattonelle" A_ij, posso considerare il quadrato che copre tutte queste A_ij e la sua copertura è un modello di questo insieme finito di assiomi.

Per il teorema di compattezza posso quindi coprire tutto il piano!

Ora per la soluzione olimpica do un hint (dato un'albero infinito t.c. ogni vertice abbia grado finito che posso dire?)

Comunque rilancio con altri problemi sempre dello stesso tipo:

1) tutti i grafi planari infiniti sono 4 colorabili.

E poi il mio preferito...
2) In una città ho un insieme (anche infinito) di persone maschie o femmine.
So che comunque scelto un'insieme finito S di maschi l'insieme A delle femmine che piacciono ad almeno un maschio è finito ed è tale che |A|>=|S|.

Dimostrare che si può sposare ogni maschio con una femmina che gli piace!

[Nonno Bassotto]

Comunque rilancio con altri problemi sempre dello stesso tipo:

1) tutti i grafi planari infiniti sono 4 colorabili.

[enomis_costa88]

Vabbè mi pareva chiaro...

1) dimostrare che:
(ogni grafo planare finito è 4-colorabile) ==> (ogni grafo planare è 4-colorabile)

[Nonno Bassotto]

Ah ok. Se no era difficilino...

[Stoppa2006]

Secondo me il problema si può fare anche senza compattezza. Si usa:

Lemma: Ogni albero infinito tale che ogni elemento ha un numero finito di figli ha un ramo infinito.

Ad ogni tessere associo un albero nel modo seguente:
Prendo una tessera, i suoi figli sono le tassellazioni 3x3 che hanno la tessera al centro, i figli delle tassellazioni 3x3 sono tassellazioni 5x5 che hanno quella tassellazione 3x3 al centro e così via.
Essendo tassellabile un intero quadrante esisterà almeno un albero infinito. Ed essendoci un numero finito di tipi, siamo nelle ipotesi del lemma quindi quest'albero avrà un ramo infinito che ci fornisce la tassellazione del piano cercata.

[In realtà il lemma è equivalente alla compattezza nel caso numerabile... ma almeno non c'è bisogno di conoscere la logica del primo ordine per usarlo] .