szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 22 lut 2017, o 14:33 
Użytkownik

Posty: 48
Lokalizacja: Warszawa
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ę :mrgreen:


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ą.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 22 lut 2017, o 15:29 
Użytkownik

Posty: 149
Lokalizacja: obecnie Łódź
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ś.
Góra
Mężczyzna Offline
PostNapisane: 22 lut 2017, o 16:36 
Użytkownik

Posty: 48
Lokalizacja: Warszawa
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?
Góra
Mężczyzna Offline
PostNapisane: 22 lut 2017, o 18:07 
Użytkownik

Posty: 1086
Lokalizacja: Lublin/Warszawa
Rozwiązanie:

Bierzemy dowolnych dwóch takich którzy się znają (muszą istnieć). Mają oni po co najmniej 10 znajomych, ale znają się nawzajem więc mają po co najmniej 9 znajomych poza swoją dwójką. Poza nimi jest łącznie 19 - 2 = 17 osób, a oni mają łącznie 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ę A. Zna ona min. 10 osób - nazywamy ich zbiorem X. Tych którzy nie znają A nazywamy zbiorem Y. X zawiera przynajmniej 10 osób, Y co najwyżej 8 osób. Bierzemy dowolną osobę B z X, zna ona min. 10 osób, ale zna A, więc poza osobą A zna jeszcze 9 osób. Zbiór Y ma co najwyżej 8 osób, więc B musi znać przynajmniej jedną osobę C w zbiorze X. Ale A zna też C, więc A, B i C tworzą trójkąt.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile jest dzielnikow liczby  Anonymous  6
 ustawianie osob w rzedzie, liczby n-cyfrowe itp  Anonymous  16
 winda - 8 pieter, 5 osob  Anonymous  12
 ile jest liczb 2cyfr/3cyfr, 5cyfr o pocz 12, bez cyfr 4 i 5?  Anonymous  1
 Zjazd 10 osob - ile bedzie powitan?  Anonymous  8
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl