Osoby na przystanku.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
1608
Użytkownik
Użytkownik
Posty: 245
Rejestracja: 9 wrz 2010, o 21:36
Płeć: Mężczyzna
Lokalizacja: Krakow
Podziękował: 133 razy
Pomógł: 1 raz

Osoby na przystanku.

Post autor: 1608 »

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.
Powermac5500
Użytkownik
Użytkownik
Posty: 323
Rejestracja: 3 sty 2013, o 16:16
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 62 razy

Osoby na przystanku.

Post autor: Powermac5500 »

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.
ODPOWIEDZ