3*n! alieni, n linguaggi

[pi_greco_quadro]

Siano dati $ \displaystyle 3*n! $ alieni e $ \displaystyle n $ linguaggi conosciuti su tutto il pianeta. Ogni coppia di alieni parla tra sè in uno di questi linguaggi (se A parla con B un linguaggio, allora B parla con A lo stesso linguaggio ). Si dimostri che esistono $ \displaystyle 3 $ alieni che tra loro parlano lo stesso linguaggio.

[salva90]

Sembra uno spudorato Pigeonhole... piuttosto lungo, a dire il vero. Su un testo di Santos c'è qualcosa di molto simile

[edriv]

È il teorema di Ramsey per il caso n=3... però qua si chiede una sovrastima sul numero di nodi necessari.

Però non è così immediato da dimostrare da dire "spudorato pigeonhole"

[salva90]

Chiedo scusa . Ad una prima occhiata sembrava che fosse così; forse mi sono confuso con un esercizio comunque molto simile.

[piever]

Beh, in fondo è uno spudorato pigeonhole...

Proviamo per induzione (trasformando il problema in: un grafo completo con 3*n! vertici i cui archi sono colorati di n colori diversi, contiene almeno un triangolo monocromatico):
per n=1 è vero (si verifica moolto facilmente)
Ora dimostriamo che se è vero per n, allora è vero anche per n+1.
Scegliamo un vertice V a caso. Ad esso si collegano 3*(n+1)!-1 archi. Per il pigeonhole (eccolo!) ne esistono almeno 3*n! dello stesso colore (diciamo il rosso). Consideriamo il grafo G composto dai 3*n! vertici collegati a V con un arco rosso e da tutti gli archi che hanno come estremi due di questi vertici. Se un arco appartenente a G è rosso, allora i 2 punti che esso collega e V formano un triangolo monocromatico rosso. Se nessun arco appartenente a G è rosso, allora G è un grafo completo con 3*n! vertici i cui archi sono colorati con n colori, dunque per ipotesi induttiva contiene almeno un triangolo monocromatico. QED

[edriv]

Ok, sono solo io lo sfigato che va a complicarsi inutilmente tutte le soluzioni di combinatoria
E la mia, oltre che complicata, era anche sbagliata,vedo ora!

[pi_greco_quadro]

Mi è piaciuto molto l'intervento di edriv perché anche a me a prima vista è riuscito spontaneo attaccare il problema usando il teorema di Ramsey. Tuttavia, bevendo il caffè (che è uno tra i momenti migliori per riflettere devo dire ) lo spudorato pigeonhole ha avuto la meglio, come dice piever. An p.s. era un Hong Kong TST 2006, ed il quel caso si aveva $ n=2005 $ ma come potete vedere attaccandolo per induzione era molto molto più semplice. Soluzione identica alla mia piever clap clap