Treść zadania
Na przyjęciu spotkało się sześć osób. Okazało się, że każda z nich ma wśród pozostałych dokładnie trzech znajomych. Wykaż, że pewne cztery z tych osób mogą usiąść przy okrągłym stole w taki sposób, aby każda z nich siedziała pomiędzy swoimi dwoma znajomymi.
Umiejętności (3)
Wymagane umiejętności:
Grafy
Analiza przypadków
Zdobywane umiejętności:
Grafy
Wskazówki (0/4)
Wskazówka 1
Przedstaw sytuację jako graf: osoby to wierzchołki, a znajomości to krawędzie. Co w języku teorii grafów oznacza, że cztery osoby mogą usiąść przy okrągłym stole, aby każda siedziała między znajomymi?
Wskazówka 2
Zauważ, że szukany układ czterech osób istnieje, jeśli w grafie znajdziemy dwie osoby, które się nie znają, ale mają co najmniej dwóch wspólnych znajomych. Spróbuj udowodnić, że taka para osób musi istnieć.
Wskazówka 3
Wybierz dowolną osobę, nazwijmy ją A. Ma ona trzech znajomych i dwie osoby, których nie zna. Wybierz jedną z osób, której A nie zna (nazwijmy ją B) i zastanów się, kim mogą być znajomi osoby B.
Wskazówka 4
Rozważ dwie możliwości dotyczące znajomych osoby B. Albo zna ona drugą osobę nieznajomą dla A, albo jej nie zna. Co w każdym z tych przypadków możesz powiedzieć o liczbie wspólnych znajomych osób A i B?