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:

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]

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]

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]

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.

[dan952]

"axpgn":Quindi "induci" su di me

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

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

[dan952]

@alex

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

[axpgn]

... mmm ... troppo generico, troppo vago ... secondo me, eh ...

[dan952]

@alex

Ho aggiunto qualcosina per essere più preciso nel ragionamento.

Comunque se c'è qualcosa che non torna dimmelo sono qui apposta

[axpgn]

Ecco la mia soluzione ...

Per induzione

Passo base:
Per $n=2$ la colorazione richiesta è evidente.

Passo induttivo:
Supponiamo che per $n$ punti ($n$ pari) sia possibile suddividere il disco in modo tale che sia possibile colorarlo come richiesto.
Consideriamo $n+2$ punti sul bordo del disco, $(n+2)/2$ curve che li collegano e $(n+2)/2+1$ regioni.
Se togliamo una curva qualsiasi e i due punti alle sue estremità torniamo alla situazione con $n$ punti quindi colorata come richiesto.
Rimettiamo al loro posto i due punti appena tolti e li ricolleghiamo.
Possiamo avere due casi:
- i due punti sono consecutivi; in questo caso la nuova regione che si viene a creare è una parte di una regione più grande e non confina con altre; per giungere a quanto richiesto è sufficiente colorare la nuova regione con il colore opposto a quello della regione da cui discende.
- i due punti non sono consecutivi; in questo caso la nuova curva che si viene a creare divide in due parti la regione attraversata; per giungere a quanto richiesto è sufficiente colorare una delle due parti con il colore opposto a quello che aveva ed invertire i colori di tutte le regioni che si trovano dalla stessa parte.

Cordialmente, Alex

[Mathita]

[ot]Sono un pessimo matematico. l'idea di fondo ricalca un po' quella di axpgn, tuttavia il formalismo mi ha distratto troppo e mi sono perso nelle notazioni. Che babbalucco che sono![/ot]

[axpgn]

Esagerato!