Zadanie 5
2020
Etap II
★★★★☆Kombinatoryka
Logika
Zdalne przyjęcie urodzinowe
Treść zadania
Tomek zaprosił na zdalne przyjęcie urodzinowe 11 swoich znajomych, którzy kolejno będą dołączać do spotkania. Tomek dobrał gości w taki sposób, aby niezależnie od kolejności w jakiej będą dołączać, zawsze nowo przybyła osoba znała co najmniej połowę już obecnych osób, wliczając Tomka. Wykaż, że wśród zaproszonych gości istnieje taki, który zna wszystkich pozostałych 10 znajomych Tomka.
*Uwaga:* Przyjmujemy, że jeśli osoba zna osobę , to również zna .
*Uwaga:* Przyjmujemy, że jeśli osoba zna osobę , to również zna .
Umiejętności (3)
Wymagane umiejętności:
Grafy
Zdobywane umiejętności:
Zasada ekstremalna
Dowód nie wprost
Wskazówki (0/4)
Wskazówka 1
Zinterpretuj znajomości jako graf. Warunek 'niezależnie od kolejności' oznacza, że możesz testować dowolną, nawet bardzo nietypową kolejność dołączania gości, aby znaleźć sprzeczność.
Wskazówka 2
Załóż nie wprost, że każdy gość kogoś nie zna. Spróbuj doprowadzić to założenie do sprzeczności, konstruując sprytną kolejność dołączania gości.
Wskazówka 3
Wybierz dowolnego gościa, nazwijmy go C. Rozważ kolejkę, w której najpierw dołączają wszyscy jego nieznajomi, a zaraz po nich dołącza sam C. Jaki warunek musi wtedy spełnić C?
Wskazówka 4
Z warunku dla C wynika, że każdy gość ma co najwyżej jednego nieznajomego. Co to oznacza dla grafu nieznajomości i dlaczego jest to niemożliwe dla 11 gości?