Trova l'amicone

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
kalu
Messaggi: 295
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

Trova l'amicone

Messaggio da kalu » 03 ago 2013, 21:20

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.
Pota gnari!

Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: Trova l'amicone

Messaggio da <enigma> » 03 ago 2013, 21:40

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
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)

Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: Trova l'amicone

Messaggio da Mist » 22 ago 2013, 22:20

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.
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102

Rispondi