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.

Wyszukiwarka

Podobne podstrony:
Ekstremalny element, czyli o tym, co naj.. . Adam Osękowski i Łukasz Rajkowski Celem niniejszego art
Ekstremalny element, czyli o tym, co naj... 19 jeżeli zaś zbiór D jest pusty, kładziemy A = C, B = {
File0021 Według W. Pietrasa rządzenie składają się z cztery elementy: 1)    decydowan
Papierowe rytmy w edukacji dzieci, czyli o tym w co lubi bawić się mózgmgr Dorota Dziamska REFERATPr
CCF20090831029 34 Przedmowa
4) przerwy zimowe, wiosenne i letnie trwające łącznie nie krócej niż 6 tygodni, w tym co najmniej 4
WYKŁADY DO WYBORU (należy wybrać co najmniej 180 godzin, w tym co najmniej 16 punktów ECTS - w każdy
z
1 11 Próbny arkusz maturalny R-3 Poziom rozszerzonyZadanie 10. (6 pkt) W pudełku jest 15 kul, w ty
CCF20090521013 spożywanie 600-800 g węglowodanów dziennie, w tym co najmniej 35% powinny stanowić c
najmniej 1000 pracowników w państwach członkowskich, w tym co najmniej po 150 pracowników w co najmn
Rzecz nie w tym, co mówisz Ty - lecz w tym, co słyszą inni...... czyli jak uniknqć błędów przygotowu
IMGE76 Izabella Lignowska 258 I Mów
Technik Mechatronik Już dzisiaj pomyśl o tym, co chcesz robić w przyszłości, Czyli czym zajmuje

więcej podobnych podstron