Zadanie 2

2012

Etap III

★★★★☆

Kombinatoryka

Logika

Przyjęcie 99 osób

Powiązane zadania:

Zad. 2 (2009)

Zad. 2 (2006)

Zad. 3 (2006)

Treść zadania

Na przyjęciu spotkało się

99

osób. Wiadomo, że wśród każdych trzech osób można wskazać taką, która zna dwie pozostałe osoby z tej trójki. Wykaż, że pewna osoba zna wszystkie inne osoby obecne na przyjęciu.

*Uwaga.* Przyjmujemy, że jeśli osoba

A

zna osobę

B

, to osoba

B

zna osobę

A

Zadania PDF Rozwiązania PDF

Zgłoś błąd

Umiejętności (5)

Wymagane umiejętności:

Zasada ekstremalna

Grafy

Dowód nie wprost

Zdobywane umiejętności:

Zasada ekstremalna

Grafy

Wskazówki (0/4)

Wskazówka 1

Przedstaw problem w języku teorii grafów: osoby to wierzchołki, a znajomość to krawędź. Załóż nie wprost, że nikt nie zna wszystkich pozostałych osób.

Wskazówka 2

Z założenia nie wprost wynika, że istnieje para osób,

A

B

, które się nie znają. Rozważ dowolną inną osobę

C

i zastosuj warunek z zadania do trójki {

A, B, C

Wskazówka 3

Osobą znającą dwie pozostałe w trójce {

A, B, C

} musi być

C

. To oznacza, że każda osoba spoza pary {

A, B

} zna i

A

, i

B

. Czy zbiór tych 97 osób też musi spełniać warunek z zadania?

Wskazówka 4

Tak, zbiór 97 osób również spełnia warunek zadania. Można więc powtórzyć ten sam argument, odkładając na bok kolejne pary nieznajomych. Co pozostanie na końcu tego procesu, skoro liczba osób jest nieparzysta?

Prześlij rozwiązanie

Zaloguj się, aby przesłać swoje rozwiązanie

Zaloguj się