Nie za bardzo wiem jak ruszyć to zadanie:
Udowodnij, że w każdej grupie 6 osób czekających na przystanku są trzy, które znają się każda z każdą lub trzy nieznające się nawzajem.
Wiem że trzeba tutaj jakoś skorzystać z zasady szufladkowej Dirichleta ale nie wiem jak.
Osoby na przystanku.
-
- Użytkownik
- Posty: 323
- Rejestracja: 3 sty 2013, o 16:16
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Pomógł: 62 razy
Osoby na przystanku.
O ile wiem to dowodzi się z teorii grafów.
Jeśli wyobrazimy sobie osoby jako wierzchołki grafu, a relacje (zna)-(nie zna) jako dwa kolory krawędzi to dowodzi się, że w grafie pełnym o 6 wierzchołkach istnienie co najmniej jeden trójkąt pokolorowany tym samym kolorem.
Wrzucisz w Google "problem Ramseya" lub "liczby Ramseya" to pewnie wyskoczy jakiś dowód.
Jeśli wyobrazimy sobie osoby jako wierzchołki grafu, a relacje (zna)-(nie zna) jako dwa kolory krawędzi to dowodzi się, że w grafie pełnym o 6 wierzchołkach istnienie co najmniej jeden trójkąt pokolorowany tym samym kolorem.
Wrzucisz w Google "problem Ramseya" lub "liczby Ramseya" to pewnie wyskoczy jakiś dowód.