Ambasciatori

[axpgn]

Ad una cena di gala sono invitati $2n$ ambasciatori che si siedono attorno ad un tavolo rotondo.
Ogni ambasciatore ha, al massimo, $n-1$ nemici tra gli altri ambasciatori.

Provare che tutti gli ambasciatori possono sedersi attorno al tavolo senza che nessuno di loro abbia nemici seduti ai suoi fianchi (sia a destra che a sinistra).


Cordialmente, Alex

[Quinzio]

Provo a mettere una soluzione, che non mi convince troppo e la vedo incompleta, ma ci va vicino.
Sarebbe anche bello che partecipassero altre persone alla soluzione di questi problemi,come notava gia' qualcun altro.
Per il momento, teniamo viva questa simpatica "rubrica".

La situazione e' quella di un grafo $G(V, A)$ con $2n$ vertici e al massimo $n-1$ archi per ogni vertice.
Adesso si prende il grafo complemento $\bar G$, ossia con tutti e solo gli archi che non sono presenti nel grafo originale.
Ogni vertice avra' quindi almeno $n$ archi collegati.
Chiamiamo $A^\star(\bar G)$ l'insieme dei vertici nel grafo complemento collegati al vertice $A$.
Consideriamo l'intersezione di due di questi insiemi.
Nel primo caso: $A^\star(\bar G) \cap B^\star(\bar G) \ne \emptyset$ e allora i vertici $A$ e $B$ sono collegati in modo indiretto da qualche vertice $C$.
Nel secondo caso $A^\star(\bar G) \cap B^\star(\bar G) = \emptyset$ e siccome
$A^\star(\bar G) \cup B^\star(\bar G) = V$
$A \notin A^\star(\bar G) $
$B \notin B^\star(\bar G) $
deve essere
$B \in A^\star(\bar G) $
$A \in B^\star(\bar G) $
ossia esiste un collegamento diretto tra i vertici $A$ e $B$.
Abbiamo quindi stabilito che esiste un ciclo completo che tocca tutti i vertici (ciclo hamiltoniano) in quanto i vertici sono tutti a due a due collegabili.
Nella situazione originale (degli ambasciatori) questo ciclo sarebbe il "circolo degli amici", ovvero prendendo i rapporti di amicizia (due ambasciatori non nemici) e' possibile fare il giro completo degli ambasciatori e quindi farli sedere al tavolo avendo ai fianchi solo amici.
L'unico dubbio che mi rimane e' che non riesco ad escludere che un vertice possa essere visitato due volte nel ciclo hamiltoniano e che quindi non sia un vero ciclo hamiltoniano.

[axpgn]

Sarà anche corretto ma non ci ho capito niente
Ma è un problema mio, che non so nulla di grafi, mi spiace
Presumo però che alle superiori siano pochi quelli che ne capiscano qualcosa

[axpgn]

Una soluzione più a portata di mano

Inizialmente gli ambasciatori si siedono a caso e quindi avremo in generale $N$ coppie "nemiche".
Se esiste un algoritmo che ad ogni opportuno scambio di posto di due ambasciatori riduce $N$ siamo a cavallo.
L'algoritmo esiste ed è questo:
Sia $(A,B)$ una coppia "nemica" con $B$ alla destra di $A$.
Supponiamo che esista una coppia $(A'B')$ tale che se scambiamo $B$ con $A'$, le nuove coppie $(A,A')$ e $(B,B')$ siano entrambe amiche; se una coppia simile esiste sempre allora possiamo sempre ridurre $N$.
Si può dimostrare che tale coppia esiste sempre.
Dimostrazione:
Partiamo da $A$ e percorriamo il tavolo in senso antiorario.
Incontreremo almeno $n$ amici di $A$.
Alla loro destra ci sono $n$ sedie, le quali NON possono essere occupate tutte da nemici di $B$ in quanto al massimo possono essere $n-1$ quindi ci sarà sicuramente un amico $A'$ di $A$ con alla sua destra un amico $B'$ di $B$.

Cordialmente, Alex

[Quinzio]

"axpgn":

Inizialmente gli ambasciatori si siedono a caso e quindi avremo in generale $N$ coppie "nemiche".

Perche'
Sarebbe il caso peggiore, il caso medio ?

[axpgn]

Era solo un'introduzione per dire che, in generale, c'è ALMENO una coppia di nemici seduti vicini; se non ce ne fosse nessuna avremmo già finito la dimostrazione, non ti pare?

[Quinzio]

"axpgn":

Era solo un'introduzione per dire che, in generale, c'è ALMENO una coppia di nemici seduti vicini; se non ce ne fosse nessuna avremmo già finito la dimostrazione, non ti pare?

Non ti pare ? Molto divertente... non ci sarei mai arrivato. Grazie.
Peccato che non c'entra nulla con la domanda, la quale era sul fatto che "in generale" ci siano N coppie di nemici.
E' un affermazione che non vuol dire nulla.

[Quinzio]

"axpgn":Una soluzione più a portata di mano

Inizialmente gli ambasciatori si siedono a caso e quindi avremo in generale $N$ coppie "nemiche".
Se esiste un algoritmo che ad ogni opportuno scambio di posto di due ambasciatori riduce $N$ siamo a cavallo.
L'algoritmo esiste ed è questo:
Sia $(A,B)$ una coppia "nemica" con $B$ alla destra di $A$.
Supponiamo che esista una coppia $(A'B')$ tale che se scambiamo $B$ con $A'$, le nuove coppie $(A,A')$ e $(B,B')$ siano entrambe amiche; se una coppia simile esiste sempre allora possiamo sempre ridurre $N$.
Si può dimostrare che tale coppia esiste sempre.
Dimostrazione:
Partiamo da $A$ e percorriamo il tavolo in senso antiorario.
Incontreremo almeno $n$ amici di $A$.
Alla loro destra ci sono $n$ sedie, le quali NON possono essere occupate tutte da nemici di $B$ in quanto al massimo possono essere $n-1$ quindi ci sarà sicuramente un amico $A'$ di $A$ con alla sua destra un amico $B'$ di $B$.

Cordialmente, Alex

Sara' piu' a portata di mano (forse), sicuramente lo e' per chi ha difficolta' ad afferrare il concetto di grafo, ma peccato che...

la dimostrazione non regge, perche' dipende anche da chi c'e' dall'altra parte delle coppie AB e A'B'.

[axpgn]

Certo che regge ...

forse ti è sfuggito il fatto che in questo modo si riducono le coppie nemiche UNA ALLA VOLTA, l'altra la risolvi DOPO (la coppia "a sinistra" non è altro che un'altra coppia "a destra" )

[Quinzio]

"axpgn":Certo che regge ...

forse ti è sfuggito il fatto che in questo modo si riducono le coppie nemiche UNA ALLA VOLTA, l'altra la risolvi DOPO (la coppia "a sinistra" non è altro che un'altra coppia "a destra" )

Va bene, puo' essermi sfuggito il mondo intero mentre ero distratto.

Quello che ti voglio dire e' che parli di algoritmo, ma io non vedo un algoritmo completo, vedo solo una cosa che secondo me non e' completa.
Un algoritmo deve essere una lista di istruzioni che potrebbe essere data in pasto a un computer o a un robot.
Facciamo un caso pratico: ho un file la cui prima riga definisce $n$.
Poi c'e' la lista dei collegamenti di nemici. Ad es:

n = 100
1-25
57-99
33-34
....

Possiamo fa sedere gli ambasciatori in ordine di numero, cioe' 1, 2, 3, 4, 5, ...
Se non ci sono nemici seduti accanto, abbiamo finito, ma probabilmente ce ne saranno piu' di uno.
Ad es. sono il 33 e il 34, che sarebbero $A$ e $B$.
Bene ora che faccio ? Come seleziono $A'$ e $B'$ ?

[axpgn]

Nel modo che ho scritto: dato che ci sono almeno $n$ amici di $A$ e al massimo $n-1$ nemici di $B$, andando in senso antiorario trovero sicuramente una coppia $A'B'$ con $A'$ amico di $A$ e $B'$ amico di $B$ e prendo la prima che incontro.

[Quinzio]

"axpgn":

Nel modo che ho scritto: dato che ci sono almeno $ n $ amici di $ A $ e al massimo $ n-1 $ nemici di $ B $, andando in senso antiorario trovero sicuramente una coppia $ A'B' $ con $ A' $ amico di $ A $ e $ B' $ amico di $ B $ e prendo la prima che incontro.

Ho capito. Ma...

[axpgn]

Mi sono espresso male, correggo ... sorry ...

Non scambio solo $B$ con $A'$ ma inverto tutto il blocco che va da $B$ ad $A'$

[Quinzio]

Okkk... direi che adesso c'e' tutto.