OliForum Matematico

Ci sono 9 delegati ad una conferenza, ciascuno parla al più 3 lingue.
Comunque dati 3 delegati ce ne sono almeno 2 che parlano almeno una lingua in comune.
Dimostrare che vi sono almeno 3 delegati che parlano la stessa lingua.
(usamo 5, 1978)

PS: non è difficilissimo (anche se secondo me è molto carino), quindi piever pleaze non ucciderlo subitissimo

E' facile dimostrare che esiste una coppia di persone, tale che ogni altra persona condivida con una di queste due almeno una lingua (stasera la posto: l'idea comunque è di prendere una coppia di persone e prendere gli insiemi di 3 persone contenenti queste 2 e ognuna delle altre 7 a turno).
Delle altre 7 persone, per pigeonhole 4 condividono una lingua con la stessa persona della coppia. Sia P1 questa persona.
Prendiamo l'insieme di queste 5 persone: per Pigeonhole, delle 4 persone che non sono P1, due condividono con P1 la stessa lingua (infatti P1 parla al massimo 3 lingue), quindi questa lingua è parlata da tre persone, c.v.d.

Ciao!

Allora, si diceva...
Siano P1...P9 le persone in questione. Allora si ha il lemma: esiste una coppia di persone, P1 e P2, tali che ognuna delle altre 7 persone P3...P9 condivide almeno una lingua con almeno uno fra P1 e P2.
Dimostrazione: prendiamo una qualunque coppia di persone P1 e P2. Consideriamo l'insieme $ P_1, P_2, P_i $: per ipotesi almeno due di queste persone condividono una lingua. Se $ P_1 $ e $ P_2 $ non condividono alcuna lingua, siamo a posto, perchè per ipotesi P_i condivide una lingua o con P1 o con P2.
Se così non è, o $ P_i $ condivide una lingua con P1 o P2 per ogni $ i \geq 3 $ (dimostrando il lemma), oppure P_i e P1 non condividono alcuna lingua e dunque si ricade nel caso di prima, di due persone che non parlano alcuna lingua comune.
Da questo lemma si conclude come sopra.

Ciao!

Hum..rispondo un po' a scoppio ritardato, sorry.
In realtà c'è anche una soluzione un po' più immediata usando i grafi.

Do solo un piccolo hint: il dato che comunque scelte 3 persone 2 parlano la stessa lingua vuole dire che un certo grafo non ha sottografi G_3 completi.