Le belle piastrelle di Mamino

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Le belle piastrelle di Mamino

Messaggio da edriv » 06 ott 2006, 22:30

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

Re: Le belle piastrelle di Mamino

Messaggio da MindFlyer » 06 ott 2006, 23:21

edriv ha scritto:questo è un teorema della logica di primo ordine
E' uno dei teoremi di compattezza.

Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 » 07 ott 2006, 14:24

NO..volevo proporlo io questo :twisted:
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) :wink:

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

Buon lavoro.
"Tu che lo vendi cosa ti compri di migliore?"

Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.

Avatar utente
Sisifo
Messaggi: 604
Iscritto il: 01 gen 1970, 01:00
Località: Scorzè (VE)/Pisa

Messaggio da Sisifo » 07 ott 2006, 14:40

Denis :D

Ancora questo.. Non volete proprio lasciarci dormire! :D:D:D
"Non è certo che tutto sia incerto"(B. Pascal)
Membro dell'associazione "Matematici per la messa al bando del sudoku" fondata da fph

Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 » 06 feb 2008, 17:29

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

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!
"Tu che lo vendi cosa ti compri di migliore?"

Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.

Avatar utente
Nonno Bassotto
Site Admin
Messaggi: 970
Iscritto il: 14 mag 2006, 17:51
Località: Paris
Contatta:

Messaggio da Nonno Bassotto » 06 feb 2008, 19:26

enomis_costa88 ha scritto: Comunque rilancio con altri problemi sempre dello stesso tipo:

1) tutti i grafi planari infiniti sono 4 colorabili.
:shock:
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill

Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 » 06 feb 2008, 21:54

Vabbè mi pareva chiaro...

1) dimostrare che:
(ogni grafo planare finito è 4-colorabile) ==> (ogni grafo planare è 4-colorabile)
"Tu che lo vendi cosa ti compri di migliore?"

Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.

Avatar utente
Nonno Bassotto
Site Admin
Messaggi: 970
Iscritto il: 14 mag 2006, 17:51
Località: Paris
Contatta:

Messaggio da Nonno Bassotto » 07 feb 2008, 09:02

Ah ok. :) Se no era difficilino...
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill

Stoppa2006
Messaggi: 51
Iscritto il: 28 nov 2006, 20:12

Messaggio da Stoppa2006 » 08 feb 2008, 19:48

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

Rispondi