Conoscenze
Conoscenze
Dimostrare che in una stanza in cui ci sono 6 persone c'e ne saranno sempre almeno 3 che si conoscono o almeno 3 che non si conoscono tra di loro
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Riscrivo la tesi usando un po' di teoria dei grafi:
Ho un grafo completo con 6 vertici e 15 lati. Coloro ogni lato come segue:
di rosso se esso connette due vertici A,B e A "conosce" B.
di giallo se esso connette due vertici C,D e C "non conosce" D.
Devo dimostrare che ho comunque un triangolo monocromatico.
E' ben noto che: $ R(3,3)=6 $..cui segue la tesi
ovvero il minimo n tale che $ G_n $, grafo completo (con n vertici) i cui lati sono colorati con 2 colori, abbia un sottografo $ G_3 $ completo e monocromatico è 6.
Dimostrazione:
Da un vertice A partono 5 lati, almeno 3 dello stesso colore.
Ipotizzo senza perdita di generalità che questo colore sia rosso.
Chiamo B,C,D gli altri 3 estremi di questi 3 lati rossi.
Se anche solo uno dei lati che connettono due qualsiasi di questi vertici (senza perdita di generalità BC) fosse rosso allora avrei 3 lati rossi: AB,AC,BC e un triangolo monocromatico rosso.
Se nessuno dei 3 lati che connette tra loro i vertici B,C,D è rosso allora sono tutti e tre gialli e avrei BCD triangolo monocromatico giallo.
Inoltre si prova facilmente che con n=5 la tesi sarebbe falsa considerando ad esempio un pentagono i cui lati siano rossi e le cui diagonali gialle.
PS questo problema era già comparso tempo fa sul forum, mi pare che qualcuno avvesse proposto una dimostrazione analoga a questa.
Buona serata, Simone.
Ho un grafo completo con 6 vertici e 15 lati. Coloro ogni lato come segue:
di rosso se esso connette due vertici A,B e A "conosce" B.
di giallo se esso connette due vertici C,D e C "non conosce" D.
Devo dimostrare che ho comunque un triangolo monocromatico.
E' ben noto che: $ R(3,3)=6 $..cui segue la tesi
ovvero il minimo n tale che $ G_n $, grafo completo (con n vertici) i cui lati sono colorati con 2 colori, abbia un sottografo $ G_3 $ completo e monocromatico è 6.
Dimostrazione:
Da un vertice A partono 5 lati, almeno 3 dello stesso colore.
Ipotizzo senza perdita di generalità che questo colore sia rosso.
Chiamo B,C,D gli altri 3 estremi di questi 3 lati rossi.
Se anche solo uno dei lati che connettono due qualsiasi di questi vertici (senza perdita di generalità BC) fosse rosso allora avrei 3 lati rossi: AB,AC,BC e un triangolo monocromatico rosso.
Se nessuno dei 3 lati che connette tra loro i vertici B,C,D è rosso allora sono tutti e tre gialli e avrei BCD triangolo monocromatico giallo.
Inoltre si prova facilmente che con n=5 la tesi sarebbe falsa considerando ad esempio un pentagono i cui lati siano rossi e le cui diagonali gialle.
PS questo problema era già comparso tempo fa sul forum, mi pare che qualcuno avvesse proposto una dimostrazione analoga a questa.
Buona serata, Simone.
Riesumo un topic antichissimo
solo perchè ho letto che esiste una soluzione semplice con PigeonHole e dato che in combinatoria non sono una cima ho voluto provare.
Chiamiamo $ $a, b, c, d, e, f$ $ le 6 persone della stanza. Sia $ $A$ $ l'insieme delle persone che $ $a$ $ conosce, e $ $A'$ $ l'insieme delle persone che $ $a$ $ non conosce. Chiaramente $ $A$ $ e $ $A'$ $ non hanno elementi in comune e $ $A \cup A'$ $ è l'insieme di tutte le persone tranne $ $a$ $.
Se prendiamo una persona a caso, mettiamo $ $b$ $, essa apparterrà certamente a $ $A$ $ oppure a $ $A'$ $, apparterrà certamente a $ $C$ $ oppure a $ $C'$ $, e cosi via per tutti gli insiemi fino ad $ $F$ $ e $ $F'$ $.
Ovvero $ $b$ $ appartiene esattamente a $ $5$ $ tra i $ $10$ $ insiemi $ $\{ A, A', C, C', D, D', E, E', F, F' \}$ $.
Se riordiniamo cosi:
$ $\{\{ A, C, D, E, F \}, \{ A', C', D', E', F' \}\}$ $
Presi 4 elementi, due per parte, è chiaro che il quinto sarà nell'insieme "conosciuti da" o nell'insieme "non conosciuti da", ed andrà a formare con gli altri due una tripletta.
Esistono sempre quindi 3 persone che si conoscono oppure 3 che non si conoscono.
solo perchè ho letto che esiste una soluzione semplice con PigeonHole e dato che in combinatoria non sono una cima ho voluto provare.
Chiamiamo $ $a, b, c, d, e, f$ $ le 6 persone della stanza. Sia $ $A$ $ l'insieme delle persone che $ $a$ $ conosce, e $ $A'$ $ l'insieme delle persone che $ $a$ $ non conosce. Chiaramente $ $A$ $ e $ $A'$ $ non hanno elementi in comune e $ $A \cup A'$ $ è l'insieme di tutte le persone tranne $ $a$ $.
Se prendiamo una persona a caso, mettiamo $ $b$ $, essa apparterrà certamente a $ $A$ $ oppure a $ $A'$ $, apparterrà certamente a $ $C$ $ oppure a $ $C'$ $, e cosi via per tutti gli insiemi fino ad $ $F$ $ e $ $F'$ $.
Ovvero $ $b$ $ appartiene esattamente a $ $5$ $ tra i $ $10$ $ insiemi $ $\{ A, A', C, C', D, D', E, E', F, F' \}$ $.
Se riordiniamo cosi:
$ $\{\{ A, C, D, E, F \}, \{ A', C', D', E', F' \}\}$ $
Presi 4 elementi, due per parte, è chiaro che il quinto sarà nell'insieme "conosciuti da" o nell'insieme "non conosciuti da", ed andrà a formare con gli altri due una tripletta.
Esistono sempre quindi 3 persone che si conoscono oppure 3 che non si conoscono.