Tavole rotonde e tanti nemici

[wall98]

\(\displaystyle 2n \) ambasciatori sono invitati a un banchetto.Ogni ambasciatore ha al massimo \(\displaystyle n-1 \) nemici.Dimostrare che gli ambasciatori possono sedersi intorno ad una tavola rotonda in modo che nessuno sia seduto vicino ad un suo nemico
buon divertimento!

[Luca9712]

[ot]E' sul forum Olimpiadi della Matematica Torino ...vediamo se qualcuno ci riesce [/ot]

[wall98]

[ot]Già
non volevo spiattellare la soluzione cosi, qualcuno deve provare l'ebrezza di risolverlo! [/ot]
comunque, se volete qualche hint, chiedete pure ok?

[milizia96]

Questo l'avevo già visto alle olimpiadi di informatica...
Se non lo risolve nessuno allora metto il mio procedimento.

[wall98]

@Milizia96
[ot]in allenamento vero? perche se l'hai visto in gara è davvero preoccupante...[/ot]

[Luca9712]

"wall98":[ot]Già
non volevo spiattellare la soluzione cosi, qualcuno deve provare l'ebrezza di risolverlo! [/ot]
comunque, se volete qualche hint, chiedete pure ok?

[ot]No no, niente hint . Ciao[/ot]

[milizia96]

E' l'esercizio "camelot" delle olimpiadi nazionali di informatica del 2005:

A Camelot, nel periodo di maggior splendore, ogni amicizia è corrisposta. Ogni cavaliere è amico di oltre la metà dei suoi compagni d'arme, ossia, se N è il numero dei cavalieri, ciascuno di essi può contare su almeno N/2 validi amici.
La tavola rotonda è disposta in un enorme salone, circondata da N sedie, con una sedia per cavaliere. Com'è facilmente immaginabile, ogni cavaliere pretende di avere amici ai suoi due lati, altrimenti rifiuta di sedersi al tavolo.

Aiuta Merlino, nei limiti delle tue possibilità, a disporre i cavalieri intorno al tavolo in modo che ogni cavaliere abbia degli amici ai suoi lati.

[wall98]

[ot]Acc. allora la cosa è grave, praticamente se uno avesse visto questo problema sarebbe stato mooolto avvantaggiato in gara, e dico mooolto perche la soluzione del problema in termini matematici potrebbe risultare simile in termini informatici,certo poi c'è da crearlo l'algoritmo
Tra l'altro questo è anche un problema molto famoso e piuttosto vecchio (piu del 2005)[/ot]

[milizia96]

Nessuno si fa avanti, quindi metto il punto principale della mia argomentazione, senza però dimostrare niente: chi vorrà potrà prendere spunto per elaborare una dimostrazione.

Immaginiamo di voler mettere gli ambasciatori (non necessariamente tutti!), invece che in cerchio, su una bella fila lineare.
Per fare questo, cominciamo creando una semplicissima fila in cui c'è un solo ambasciatore. Poi aggiungiamo ambasciatori finché possiamo, mettendoli uno alla volta in testa o in coda alla fila, sempre vicino a colleghi "amici".
A un certo punto non potremo più aggiungere ambasciatori o perché sono tutti in fila, o perché quelli rimasti fuori sono tutti nemici dei due che stanno agli estremi.

Bene, praticamente tutta la mia dimostrazione si basa su questo lemma:
"Data una fila costruita nel modo descritto, è sempre possibile disporre gli ambasciatori che sono nella fila attorno ad una tavola rotonda, in modo che nessuno sia mai seduto vicino a un nemico."

Poi se non si farà vivo ancora nessuno metterò la dimostrazione completa.

[wall98]

vabbe,direi che ora puoi tranquillamente postare la dimostrazione

[milizia96]

Dimostrazione del lemma:
Per "chiudere il cerchio" a partire dalla fila lineare costruita è sufficiente trovare una coppia di ambasciatori vicini in cui il primo di essi è amico del chiudi-fila mentre il secondo di essi è amico dell'apri-fila. Infatti a quel punto basta invertire l'ordine di tutti gli ambasciatori dall'apri-fila fino al primo elemento di una tale coppia, e così facendo nella fila si rispettano ancora i vincoli di amicizia e in più in nuovo apri-fila (che era il primo elemento della coppia) è amico del chiudi-fila. Quindi li posso chiudere in cerchio.

Per vedere che effettivamente esiste una tale coppia, basta osservare che nella fila devono necessariamente comparire tutti gli amici dell'apri-fila e tutti gli amici del chiudi-fila, altrimenti se uno di questi amici fosse rimasto fuori, allora avrei potuto continuare a allungare la fila in costruzione.
Quindi: nella fila ci sono almeno $n$ amici dell'apri-fila, almeno $n$ amici del chiudi-fila, ma tra apri-fila e chiudi-fila ci sono al massimo $2n-2$ persone. Insomma, non sto a precisare molto ma per il principio del pigeonhole ho che quella coppia che dicevo esiste veramente.

Benissimo, lemma dimostrato.
Quindi io posso fare così: costruisco questo cerchio a partire da una fila. Se non è rimasto nessuno fuori, allora ho finito. Altrimenti considero uno di quelli rimasti fuori. Egli ha sicuramente almeno un amico che sta nel cerchio, perché come ho detto prima, nel cerchio ci sono più di $n$ persone, quindi fuori sono rimaste meno di $n$ persone, che non possono includere tra loro TUTTI gli amici di un certo ambasciatore. Quindi "riapro" il cerchio facendo in modo che la fila che ne risulti abbia come apri-fila un amico dell'ambasciatore che sto considerando. Quindi amplio la fila finché posso (di sicuro almeno di 1) e richiudo il nuovo cerchio, che sarà sicuramente più grosso di quello di prima. Andando avanti così, il cerchio comprenderà tutti gli ambasciatori in tempo finito.