3784497988

Ekstremalny element, czyli o tym, co naj... 17

skujemy, iż zarówno B\, jak i B₂ mają co najmniej n znajomych w zbiorze {Ai, A₂, • ■ A₂m}-

Spójrzmy teraz na parę (Ai, A2). Jeśli B1 zna Ai, to B₂ nie może znać A₂: w przeciwnym razie moglibyśmy zakwaterować A\ z B\ oraz A₂ z B₂, uzyskując łącznie m+1 par znajomych, co byłoby sprzeczne z definicją liczby m. Analogicznie, jeśli B\ zna A₂, to B₂ nie może znać A\. Wynika stąd, iż suma liczb znajomych uczestników B\ i B₂ w zbiorze {Ai, A₂} nie przekracza 2.

Rozumowanie to powtarzamy dla par (A3, A4), (A5, Aq), ..., {A_2m-i,A_2m), stwierdzając ostatecznie, iż suma liczb znajomych uczestników B\i B₂w zbiorze {Ai, A₂,..., A_2m} nie przekracza 2m. Z drugiej strony, wykazaliśmy wyżej, iż liczba ta wynosi co najmniej 2n. Przeczy to założeniu m<n przyjętemu na wstępie; wobec tego mamy m = n i teza zadania jest prawdziwa.

Zadanie 5. Na przyjęciu spotkało się n osób (n ^ 5). Wiadomo, że wśród dowolnych trzech osób pewne dwie znają się. Dowieść, że spośród uczestników przyjęcia można wybrać nie mniej niż n/2 osób i posadzić przy okrągłym stole tak, aby każdy siedział między dwoma swoimi znajomymi.

Rozwiązanie

Niech m będzie największą liczbą naturalną o następującej własności: można wybrać takie osoby Ai, A₂,..., A_m, że Ai oraz A{+1 znają się dla i=l,2,...,m — 1. Niech S oznacza zbiór pozostałych n — m osób.

Rozważmy trzy przypadki:

1.    rnS^n/2. Zbiór S ma co najmniej n/2 elementów oraz A_m nie zna żadnej osoby z tego zbioru, co na mocy warunków zadania oznacza, iż każde dwie osoby w tym zbiorze muszą się znać. Jeśli osoby te usiądą dowolnie przy okrągłym stole, to każda z nich będzie siedzieć obok dwóch swoich znajomych.

2.    n/2<m<n — 1. Zbiór S jest niepusty i żadna osoba z tego zbioru nie zna ani A\, ani A_m, na mocy maksymalności liczby m. Wynika stąd, że osoby Ai i A_m się znają, a zatem Ai,A₂,...,A_m można usadzić przy okrągłym stole zgodnie z warunkami zadania.

3.    m = n. Niech 1= L(n+1)/2J. Z założenia pewne dwie osoby spośród Ai, Ai oraz A_m znają się. Stąd wynika, że osoby należące do co najmniej jednego spośród zbiorów

{Ai, A2,..., Ai}, {Ai,Ai₊i,...,A_m}, {Ai,A2,...,A_m} mogą usiąść przy okrągłym stole zgodnie z warunkami zadania. Pozostaje zauważyć, że każdy z tych trzech zbiorów liczy co najmniej n/2 osób.