Disco da colorare

[axpgn]

Sul bordo di un disco, selezionare un numero pari di punti $n$.
Disegnare nel disco $n/2$ curve, non intersecantisi, i cui estremi siano due degli $n$ punti.
Per esempio, nel caso $n=10$, potremmo avere una figura simile a questa:

Testo nascosto, fai click qui per vederlo

Le curve dividono il disco in $n/2+1$ regioni.

Provare che si può colorare il disco con solo due colori in modo tale che due regioni adiacenti abbiano un colore differente.


Cordialmente, Alex

[Quinzio]

Testo nascosto, fai click qui per vederlo

Prima che scriva $n$ righe di testo di dubbia utilita', vorrei solo fare una domanda:
il teorema della curva di Jordan c'entra qualcosa con la dimostrazione ?

[axpgn]

Scusa la mia ignoranza ma quale sarebbe? Quella che dice che c'è un interno e un esterno?
Comunque no, non serve, niente di complicato

[Mathita]

Testo nascosto, fai click qui per vederlo

Avevo pensato di riscrivere il problema in termini di colorabilità dei grafi: l'obiettivo era quello di dimostrare che esiste una funzione colorante, procedendo per induzione sul numero di regioni, ma mi sono arreso per due motivi: 1. l'induzione, per come l'avevo imposta io, non funzionava. 2. L'esercizio ha certamente una soluzione più furba, perché conosco bene Alex.

[axpgn]

Quindi "induci" su di me

[Mathita]

Testo nascosto, fai click qui per vederlo

Sai qual è il mio problema? Il mio cervello ha deciso che questo problema si deve risolvere con la teoria dei grafi e non ci sarà modo di fargli cambiare idea: è de coccio. Intuitivamente riesco a vedere che il grafo associato a una configurazione del genere è un albero, e in quanto tale è bicolorabile. Problema: come dimostro che problema è riducibile a un albero? Non sono ferrato su queste cose: mi sono avvicinato alla teoria dei grafi questa estate, per conto mio, e non ho mai approfondito la questione.

[dan95]

Quindi "induci" su di me

Testo nascosto, fai click qui per vederlo

Procediamo per induzione $n=2$ funziona infatti dividiamo il cerchio in due regioni di colore diverso.


Ora supponiamo valga per i primi k pari e aggiungiamo due punti. Colleghiamo questi due punti, essi dividono il cerchio in due regioni, ognuna delle due regioni ha un numero pari di punti, non può esistere una curva che divide il cerchio in due regioni con un numero dispari di punti poiché rimarrebbero all'interno di ognuna delle due regioni un punto non collegabile a nessun altro punto poiché non possono intersecarsi due curve. Le due regioni in cui è stato diviso il cerchio possono essere visti come due cerchi più piccoli con meno punti di quello iniziale quindi per ipotesi induttiva si ha la tesi.

[axpgn]

... mmm ... non mi convince e non mi è chiaro ...

Testo nascosto, fai click qui per vederlo

Cosa significa "una regione interna e una esterna"? Sono entrambe interne al disco ed esterne a cosa?
E poi anche il fatto che dividi il disco in due regioni che sicuramente sono colorate come richiesto, non implica, di per sé, che la loro unione sia colorata correttamente.
Manca qualcosa, manca una procedura precisa

Cordialmente, Alex

[axpgn]

@Mathita
Ho letto solo ora il tuo messaggio "post-induzione"
Il fatto è che io so ben poco di grafi e come hai ben intuito ( ) spesso posto quesiti che si possono risolvere in modo non molto complicato (anche perché se no, non saprei come risolverli io )


Cordialmente, Alex

[dan95]

@alex

Testo nascosto, fai click qui per vederlo

Chiaramente le due regioni $R_1$ e $R_2$ adiacenti che forma la curva sono colorati in maniera differente e proprio questi due colori determinano il colore di ciascuna regione presente in $R_1$ e $R_2$.