Ciao a tutti,
qualche giorno fa mi sono posto questo problema: qual è, se esiste, il numero massimo di figure che si possono disporre nel piano in modo tale che ciascuna tocchi tutte le altre con più di un punto?
Penso di aver trovato uno spunto per risolverlo ma vorrei prima sentire le vostre idee.
P. S. per figura intendo un'area di piano delimitata da una linea chiusa non intrecciata.
Figure adiacenti nel piano
Figure adiacenti nel piano
Nessun uomo è un'isola (J. Donne)
Ciao!
Se ho capito bene il problema, credo che il teorema dei quattro colori risponda proprio al tuo problema. Se appunto quattro colori sono sempre sufficienti a colorare qualsiasi mappa nel piano in modo che due zone adiacenti non abbiano lo stesso colore, ovviamente non possono esistere più di quattro zone a due a due confinanti. Comunque non conosco la dimostrazione e credo sia piuttosto difficile!
Se ho capito bene il problema, credo che il teorema dei quattro colori risponda proprio al tuo problema. Se appunto quattro colori sono sempre sufficienti a colorare qualsiasi mappa nel piano in modo che due zone adiacenti non abbiano lo stesso colore, ovviamente non possono esistere più di quattro zone a due a due confinanti. Comunque non conosco la dimostrazione e credo sia piuttosto difficile!
-
pic88
- Messaggi: 741
- Iscritto il: 16 apr 2006, 11:34
- Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...
Re: Figure adiacenti nel piano
In realtà non è sufficiente la condizione "più di un punto" per evitare che la risposta sia "infinite"... devono essere un'infinità continua di punti.marcuz ha scritto:Ciao a tutti,
qualche giorno fa mi sono posto questo problema: qual è, se esiste, il numero massimo di figure che si possono disporre nel piano in modo tale che ciascuna tocchi tutte le altre con più di un punto?
Penso di aver trovato uno spunto per risolverlo ma vorrei prima sentire le vostre idee.
P. S. per figura intendo un'area di piano delimitata da una linea chiusa non intrecciata.
Re: Figure adiacenti nel piano
Penso sia giusto, ma sapresti trovare una soluzione senza il teorema dei quattro colori?Ciao!
Se ho capito bene il problema, credo che il teorema dei quattro colori risponda proprio al tuo problema. Se appunto quattro colori sono sempre sufficienti a colorare qualsiasi mappa nel piano in modo che due zone adiacenti non abbiano lo stesso colore, ovviamente non possono esistere più di quattro zone a due a due confinanti. Comunque non conosco la dimostrazione e credo sia piuttosto difficile!
Effettivamente ho trovato su wikipedia il controesempio della torta a fette ma non capisco una cosa: come fanno le fette a toccarsi tutte nel centro con più di un punto? Vi avviso che non so nulla di topologia...In realtà non è sufficiente la condizione "più di un punto" per evitare che la risposta sia "infinite"... devono essere un'infinità continua di punti.
Nessun uomo è un'isola (J. Donne)
In realtà per due punti è molto semplice (puoi ad esempio immaginare le figure delimitate da archi che hanno per vertici due punti fissati), ma per più di due non credo sia possibile... dipende da cosa si intende con esattezza per "area di piano delimitata da una linea chiusa non intrecciata". Togliendo qusta condizione, però la risposta è effettivamente "infinite" per un insieme finito o numerabile di intersezioni.Effettivamente ho trovato su wikipedia il controesempio della torta a fette ma non capisco una cosa: come fanno le fette a toccarsi tutte nel centro con più di un punto? Vi avviso che non so nulla di topologia...
Se lasciamo la condizione di pic88, il tuo problema è equivalente al teorema dei quattro colori, quindi non credo esista la soluzione da te chiesta.Penso sia giusto, ma sapresti trovare una soluzione senza il teorema dei quattro colori?
-
Nonno Bassotto
- Site Admin
- Messaggi: 970
- Iscritto il: 14 mag 2006, 17:51
- Località: Paris
- Contatta:
Beh, non è proprio vero. Anche sapendo che non si trovano più di 4 regioni che si toccano mutuamente, non si arriva al teorema dei 4 colori. Potrebbe esistere una cartina in cui sistemati i primi colori gli altri sono forzati a catena, e dopo aver fatto un giro con questa catena si torna al punto di partenza con il colore sbagliato.alessio ha scritto:Se lasciamo la condizione di pic88, il tuo problema è equivalente al teorema dei quattro colori, quindi non credo esista la soluzione da te chiesta.
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill
Mmm ok forse è il momento di sfoderare tutta la mia ignoranza 
Leggendo per caso le schede olimpiche di Gobbino sono venuto a conoscenza dei grafi, così dopo qualche ricerca su internet ho pensato di applicarli al mio problema. Vi illustro l'idea:
Ad ogni gruppo di figure è possibile associare un grafo avente i vertici nelle figure e un lato incidente nei vertici di ogni coppia di figure confinanti. Viceversa, ad ogni grafo è possibile associare un gruppo di figure tagliando ciascun lato con un solo confine di adiacenza e congiungendo tra loro gli estremi di questi confini in modo tale che formino figure contenenti ognuna un vertice. Considerata la relazione "ha lo stesso grafo di", essa ripartisce in classi di equivalenza l'insieme di tutti i gruppi di figure possibili. Quindi possiamo stabilire una corrispondenza biunivoca tra la famiglia delle classi di gruppi di figure equivalenti e l'insieme dei grafi corrispondenti ad ogni classe. Ora, per soddisfare le condizioni del problema il grafo deve essere completo e planare. Dobbiamo trovare quindi, se esiste, il massimo grado di questo grafo. Per ordini 1, 2, 3 la sua esistenza è banale. Vediamo per ordine 4:
Un grafo planare completo di ordine superiore a questo è impossibile, infatti ogni altro vertice deve essere adiacente ad A, B, C e D, ma per farlo deve attraversare almeno un lato del grafo. Quindi la risposta è 4.
È corretto?
Leggendo per caso le schede olimpiche di Gobbino sono venuto a conoscenza dei grafi, così dopo qualche ricerca su internet ho pensato di applicarli al mio problema. Vi illustro l'idea:
Ad ogni gruppo di figure è possibile associare un grafo avente i vertici nelle figure e un lato incidente nei vertici di ogni coppia di figure confinanti. Viceversa, ad ogni grafo è possibile associare un gruppo di figure tagliando ciascun lato con un solo confine di adiacenza e congiungendo tra loro gli estremi di questi confini in modo tale che formino figure contenenti ognuna un vertice. Considerata la relazione "ha lo stesso grafo di", essa ripartisce in classi di equivalenza l'insieme di tutti i gruppi di figure possibili. Quindi possiamo stabilire una corrispondenza biunivoca tra la famiglia delle classi di gruppi di figure equivalenti e l'insieme dei grafi corrispondenti ad ogni classe. Ora, per soddisfare le condizioni del problema il grafo deve essere completo e planare. Dobbiamo trovare quindi, se esiste, il massimo grado di questo grafo. Per ordini 1, 2, 3 la sua esistenza è banale. Vediamo per ordine 4:
Un grafo planare completo di ordine superiore a questo è impossibile, infatti ogni altro vertice deve essere adiacente ad A, B, C e D, ma per farlo deve attraversare almeno un lato del grafo. Quindi la risposta è 4.
È corretto?
Nessun uomo è un'isola (J. Donne)
Beh, non è proprio vero. Anche sapendo che non si trovano più di 4 regioni che si toccano mutuamente, non si arriva al teorema dei 4 colori. Potrebbe esistere una cartina in cui sistemati i primi colori gli altri sono forzati a catena, e dopo aver fatto un giro con questa catena si torna al punto di partenza con il colore sbagliato.
E' vero, hai ragione. Oggi c'ho riflettuto un attimo ed effettivamente avevo preso una cantonata
