OliForum Matematico

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

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.

Soluzione troppo compilicata! Si può fare di più mai sentito parlare del principio dei cassetti(o per gli inglesi nidi di piccione):

se ho n+1 oggetti e li ripartisco in n cassetti avrò un cassetto in cui ci sono almeno 2 oggetti.

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.