Pagina 1 di 1
3*n! alieni, n linguaggi
Inviato: 05 nov 2006, 17:19
da 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.
Inviato: 05 nov 2006, 18:45
da salva90
Sembra uno spudorato Pigeonhole... piuttosto lungo, a dire il vero. Su un testo di Santos c'è qualcosa di molto simile
Inviato: 05 nov 2006, 19:06
da 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"
Inviato: 05 nov 2006, 19:42
da salva90
Chiedo scusa
. Ad una prima occhiata sembrava che fosse così; forse mi sono confuso con un esercizio comunque molto simile.
Inviato: 05 nov 2006, 21:45
da 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
Inviato: 05 nov 2006, 22:01
da 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!
Inviato: 05 nov 2006, 23:48
da 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