OliForum Matematico

A Biancavilla, comunque si scelgano $4$ abitanti, almeno uno è amico degli altri $3$. Dimostrare che almeno un abitante è amico di tutti gli altri.
L'amicizia (ovviamente) è simmetrica.

Una variante più famosa e cazzuta: se ogni coppia di persone ha un amico in comune, allora una persona è amica di tutti. http://en.wikipedia.org/wiki/Friendship_graph

La tesi per $n=4$ è banalmente verificata. Supponiamo che sia verificata per $n$. Guardiamo al caso $n+1$. Disposti gli $n+1$ abitanti a formare un $n+1-$ agono regolare, colleghiamo quelli che sono amici tra loro con una cordicella azzurra e quelli che non lo sono con una cordicella nera. Esiste, per ipotesi induttiva, un abitante $V_1$ che sarà collegato con cordicelle azzurre con $n-1$ altri abitanti. Sia $V_{n+1}$ l'abitante non collegato con $V_1$ con una cordicella azzurra. Consideriamo ora tutti i quadrilateri composti da $V_1V_nV_{n+1}V_x$ con $V_n$ fissato (e tale che sia collegato con una cordicella azzurra con $V_{n+1}$ (esiste per ipotesi)) e $V_x$ variabile. Se $V_1V_{n+1}$ è diagonale di tale quadrilatero, allora la diagonale $V_xV_n$ deve essere azzurra, altrimenti le ipotesi non sono rispettate. Se $V_1V_{n+1}$ è lato del quadrilatero, allora $V_nV_{x}$ dev'essere comunque azzurra altrimenti le ipotesi non vvarrebbero.