Le belle piastrelle di Mamino
Le belle piastrelle di Mamino
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!
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!
Re: Le belle piastrelle di Mamino
E' uno dei teoremi di compattezza.edriv ha scritto:questo è un teorema della logica di primo ordine
- enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
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.
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.
"Tu che lo vendi cosa ti compri di migliore?"
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
- enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
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!
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.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
- Nonno Bassotto
- Site Admin
- Messaggi: 970
- Iscritto il: 14 mag 2006, 17:51
- Località: Paris
- Contatta:
- enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
- Nonno Bassotto
- Site Admin
- Messaggi: 970
- Iscritto il: 14 mag 2006, 17:51
- Località: Paris
- Contatta:
-
- Messaggi: 51
- Iscritto il: 28 nov 2006, 20:12
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] .
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] .