Corrispondenze
Corrispondenze
70 persone si corrispondono per e-mail l'un l'altro- ognuno con il resto degli altri. Nelle loro dicussioni vengono trattati solo 3 argomenti differenti. Ogni paio di persone che si corrispondono trattano solo 1 di questi argomenti. Dimostrate che ci sono almeno 3 persone che si corrispondono l'un l'atro sullo stesso argomento
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Riscrivo il problema:
Ho un grafo completo con almeno 17 (ok il problema diceva 70? in realtà ne bastano 17
) vertici, i cui lati sono colorati con 3 colori differenti(rosso, giallo e verde).
Devo dimostrare che ho comunque un triangolo monocromatico.
E' noto che $ R(3,3,3) = 17 $ (cui segue la tesi..)
ovvero il minimo n tale che $ G_n $ , grafo completo (con n vertici) i cui lati sono colorati con 3 colori, abbia un sottografo $ G_3 $ completo e monocromatico è 17.
Dimostrazione
Da un vertice A partono almeno 16 lati almeno 6 dei quali dello stesso colore(suppongo sia il rosso).
Considero il vertice A e i 6 vertici di arrivo dei 6 lati rossi.
Se anche solo uno dei lati che connettono due qualsiasi di questi vertici (senza perdita di generalità lo chiamo BC) fosse rosso allora avrei 3 lati rossi: AB,AC,BC e un triangolo monocromatico rosso.
Se nessun lato che connette due qualsiasi di questi vertici è rosso allora ho un grafo completo di 6 vertici da colorare con 2 colori(giallo e verde).
Ma poichè R(3,3)=6 (per una dimostrazione vedere il problema precedente ) esiste sicuramente un triangolo monocromatico o giallo o verde.
Anche se non richiesto dal problema si può provare che con n=16 esiste almeno una configurazione in cui non ci sia alcun triangolo monocromatico.
Buona serata, Simone.
Ho un grafo completo con almeno 17 (ok il problema diceva 70? in realtà ne bastano 17
) vertici, i cui lati sono colorati con 3 colori differenti(rosso, giallo e verde).Devo dimostrare che ho comunque un triangolo monocromatico.
E' noto che $ R(3,3,3) = 17 $ (cui segue la tesi..)
ovvero il minimo n tale che $ G_n $ , grafo completo (con n vertici) i cui lati sono colorati con 3 colori, abbia un sottografo $ G_3 $ completo e monocromatico è 17.
Dimostrazione
Da un vertice A partono almeno 16 lati almeno 6 dei quali dello stesso colore(suppongo sia il rosso).
Considero il vertice A e i 6 vertici di arrivo dei 6 lati rossi.
Se anche solo uno dei lati che connettono due qualsiasi di questi vertici (senza perdita di generalità lo chiamo BC) fosse rosso allora avrei 3 lati rossi: AB,AC,BC e un triangolo monocromatico rosso.
Se nessun lato che connette due qualsiasi di questi vertici è rosso allora ho un grafo completo di 6 vertici da colorare con 2 colori(giallo e verde).
Ma poichè R(3,3)=6 (per una dimostrazione vedere il problema precedente ) esiste sicuramente un triangolo monocromatico o giallo o verde.
Anche se non richiesto dal problema si può provare che con n=16 esiste almeno una configurazione in cui non ci sia alcun triangolo monocromatico.
Buona serata, Simone.