Questo post poteva benissimo raggiungere il record di post della staffetta più lungo, ma ovviamente Talete deve rovinare tutto (
).
Possiamo immaginarci la situazione come un grafo di $n=2k$ vertici in cui due vertici sono collegati se e solo se i due tizi sono amici. Come prima cosa, dimostro che nel caso peggiore non ci sono tre persone, tutte amiche tra di loro.
Prendo una configurazione in cui ci sono dei triangoli. Se per ogni scelta di tre persone $A,B,C$ tutte amiche tra di loro, NON c'è una perla che usano tutti e tre, allora c'è una distribuzione di perle che usa meno colori che assegna ai tre tizi una sola perla (al contrario di tre per identificare la loro reciproca amicizia); inoltre non ci sono problemi del tipo "ma la perla $x$ che usano A e B non può essere sostituita con un'altra perla $y$ che useranno A, B e C perché la perla $x$ la usa pure $D$ e dovrei aggiungere altre perle" perché cosi si andrebbe contro l'ipotesi di questo caso. In parole povere: ci sono (almeno) tre amici che usano la stessa perla.
Ora, creo un'altra configurazione in cui due di questi tre amici sono diventati nemici: avrò bisogno di usare almeno due perle per collegare i due amici al posto di quella singola di prima.
Non direi che è una dimostrazione molto formale... ma sorvoliamo
Ora che ho fatto la parte brutta, noto che se non ho triangoli allora per ogni coppia di amici ho bisogno di una perlina, il che è equivalente a trovare il numero massimo di archi (caso peggiore) in un grafo del genere.
Metodo 1, suggerito da xXStephXx:
Chiamo $f(x)$ il numero massimo di archi che può avere un grafo senza triangoli con $x$ vertici. Cerco di ottenere ricorsivamente $f(n)$. Prendo due vertici collegati, $A$ e $B$ e guardo gli altri $n-2$ vertici; in questi, ci saranno al massimo $f(n-2)$ collegamenti. $A$ e $B$ non possono essere entrambi collegati ad uno stesso vertice; d'altronde, nel caso migliore, se ci fosse un vertice non collegato né ad $A$ né a $B$, potrei collegarlo ad uno dei 2 senza avere paura di avere tre vertici collegati perché l'altro non è collegato. Il numero massimo di archi è quindi: $f(n)=1+(n-2)+f(n-2)$ (arco $AB$, archi da $A$ e da $B$, archi nel resto del grafo) ovvero ricordando che n è pari:
$f(2k)=2k-1+f(2k-2)=2k-1+2(k-1)-1+f(2k-4)=\sum\limits_{i=1}^{k} 2i-1=$
$=2\sum\limits_{i=1}^{k}i-\sum\limits_{i=1}^{k}1=
2\frac{k(k+1)}{2}-k=k^2=\frac{n^2}{4}$
Anche qua, andrebbe formalizzato meglio con l'induzione...
Metodo 2 figo:
Prendo i vertici $v_1\ldots v_n$ ed ad ognuno assegno un numero reale $x_1\ldots x_n$ con le condizioni $\sum\limits_{i=1}^n x_i=1$ e $x_i \geq 0 \; \forall i$.
Considero la somma $S=\sum x_ix_j$, dove è presente il termine $x_ix_j$ se e solo se $v_i$ e $v_j$ sono collegati. Cerco il massimo di S. Siano $v_A$ e $v_B$ due vertici NON collegati, sia $n=\sum x_i$ tali che $v_i$ e $v_A$ sono collegati e $m=\sum x_i$ tali che $v_i$ e $v_B$ sono collegati. WLOG $n\geq m$. Posso scrivere $S$ come:
$S=D+x_An+x_Bm$ dove $D$ è il contributo delle coppie di vertici che non hanno né $v_A$ né $v_B$.
Ora noto che sostituendo a $(x_A,x_B)$ la coppia $(x_A+x_B,0)$, le condizioni sugli $x_i$ restano verificate, ma $S$ aumenta:
$S'=D+(x_A+x_B)\cdot n+0\cdot m=D+x_An+x_Bn \geq D+x_An+x_Bm$ siccome ho presupposto $n\geq m$.
Rifacendo il procedimento taaante volte, visto che non ci sono triangoli arrivo ad un momento in cui ci sono solo due $x_k, x_l$ diversi da $0$.
$S\leq S^{''\ldots '}=x_kx_l \leq \left( \frac{x_k+x_l}{2} \right)^2=\frac{1}{4}$ (la disuguaglianza vale per AM-GM)
Se pongo $x_i=\frac{1}{n} \; \forall i$, ho:
$S=\sum\frac{1}{n}\cdot \frac{1}{n}=|\mathrm{E}|\frac{1}{n^2}\leq \frac{1}{4}$, dove E è l'insieme degli archi del grafo.
Segue che il numero degli archi è $\leq \frac{n^2}{4}$ ( e si noti che in questo caso non è necessario $n$ pari)
Per la configurazione che funziona, basta dividere il grafo in due parti ciascuna con $\frac{n}{2}$ abitanti e collegare i vertici di una parte a tutti quelli dell'altra parte, per un totale di $\frac{n^2}{4}$ archi e quindi lo stesso numero di perline.
..... Su quest'isola però c'è un problema (ovviamente).... presi due abitanti qualsiasi, essi sono reciprocamente o amici o nemici, senza vie di mezzo...
