Na przyjęciu jest 19 osób, gdzie każdy ma min. 10 znajomych

[Stefaniak1916]

1. Na dziewiętnastoosobowym przyjęciu okazało się, że każda z tych 19 osób ma wśród pozostałych obecnych na przyjęciu co najmniej 10 znajomych. Wykaż, że na tym spotkaniu można wskazać taką trójkę osób, wśród których każde dwie się znają (Pamiętaj, że jak osoba X zna osobę Y, to osoba Y zna osobę X).

Serdecznie proszę o pomoc w rozwiązaniu zadania.

-- 22 lut 2017, o 13:34 --
Może dałoby się to poniżej lepiej zapisać, może jest lepsze rozwiązanie, jakby ktoś miał to bardzo poproszę


Moje rozwiązanie:
Spróbujmy znaleźć taką trójkę osób na tym spotkaniu, że każde dwie się znają (czyli, że trójkę osób, gdzie te trzy osoby się wzajemnie znają, każda zna dwie pozostałe).
Spróbujmy obliczyć ile conajmniej wspólnych znajomych mają dwie osoby na tym przyjęciu. Weźmy przykładowe osoby X i Y.
Rozpatrzmy dwa przypadki:
a) gdy osoby X i Y się nie znają - wtedy mają ze sobą co najmniej 3 wspólnych znajomych.
b) gdy osoby X i Y się znają - wtedy mają ze sobą co najmniej 1 wspólnego znajomego.
Znajdziemy sposoby, żeby znaleźć taką trójkę osób w obu przypadkach.
Przypadek a) wybierzmy jedną osobę (nazwijmy ją N) z tej (co najmniej) trójki wspólnych znajomych osób X i Y. Wtedy tę osobę zna osoba X i osoba Y. Ale ta osoba też ma co najmniej 10 znajomych. I co najmniej dwóch z tych dziesięciu znajomych jest też znajomym osoby X lub Y. W tym wypadku ta trójka to osoby: (N, (X lub Y), znajomy Z, który jest jednocześnie znajomym osoby X lub Y).
Przypadek b): gdy osoby X i Y się znają to wybierzmy tą jedną z conajmniej jednej osoby, która jest wspólnym znajomym X i Y. Nazwijmy ją M. W tym wypadku ta trójka to osoby: (X, Y, M)

Wykazaliśmy, że dla wszystkich możliwości istnieje możliwość ułożenia takiej trójki osób spośród tych na przyjęciu, że każde dwie się znają.

[tomwanderer]

Rozpatrywanie przypadku nr 1 jest zbędne. Weźmy od razu dwie osoby takie, które się znają. A dalej jest tak, jak napisałeś.

[Stefaniak1916]

Dzięki! Jednak jeśli jeszcze ktoś inny to czyta i widzi jakieś własne rozwiązania tego zadania to jestem bardzo ciekaw. Np. jak uzasadnić, że dwie spośród tych 19 osób mają co najmniej 1 wspólnego znajomego? Rysować 19 kółeczek, zaznaczyć osoby X i Y i metodą prób i błędów udowodnić, że mogą mnieć co najmniej 1 znajomego (chyba można teź to wykazać, że gdy te 2 osoby się nie znają i mają 3 wspólne znajomości, to najmniej wspólnych znajomosci mogą mieć gdy się wzajemnie znają, bo wtedy liczba wspólnych znajomości to 3-2=1). Może jest jakiś inny sposób?

[Mruczek]

Rozwiązanie:

Bierzemy dowolnych dwóch takich którzy się znają (muszą istnieć). Mają oni po co najmniej \(\displaystyle{ 10}\) znajomych, ale znają się nawzajem więc mają po co najmniej \(\displaystyle{ 9}\) znajomych poza swoją dwójką. Poza nimi jest łącznie \(\displaystyle{ 19 - 2 = 17}\) osób, a oni mają łącznie \(\displaystyle{ 9 \cdot 2 = 18}\) znajomych poza swoją dwójką, więc któraś z osób musi być ich wspólnym znajomym i tworzyć z nimi trójkąt.
Tyle na temat Twojego sposobu.

Inaczej:

Bierzemy dowolną osobę \(\displaystyle{ A}\). Zna ona min. \(\displaystyle{ 10}\) osób - nazywamy ich zbiorem \(\displaystyle{ X}\). Tych którzy nie znają \(\displaystyle{ A}\) nazywamy zbiorem \(\displaystyle{ Y}\). \(\displaystyle{ X}\) zawiera przynajmniej \(\displaystyle{ 10}\) osób, \(\displaystyle{ Y}\) co najwyżej \(\displaystyle{ 8}\) osób. Bierzemy dowolną osobę \(\displaystyle{ B}\) z \(\displaystyle{ X}\), zna ona min. \(\displaystyle{ 10}\) osób, ale zna \(\displaystyle{ A}\), więc poza osobą \(\displaystyle{ A}\) zna jeszcze \(\displaystyle{ 9}\) osób. Zbiór \(\displaystyle{ Y}\) ma co najwyżej \(\displaystyle{ 8}\) osób, więc \(\displaystyle{ B}\) musi znać przynajmniej jedną osobę \(\displaystyle{ C}\) w zbiorze \(\displaystyle{ X}\). Ale \(\displaystyle{ A}\) zna też \(\displaystyle{ C}\), więc \(\displaystyle{ A}\), \(\displaystyle{ B}\) i \(\displaystyle{ C}\) tworzą trójkąt.