Kilka zadań rozruchowych przed studiami (problem)

[rzexnik]

Witam
Mam problem z kilkoma zadaniami - wlasciwie, jezeli zrozumialbym 2 z nich to myślę, że reszta poleciałby z górki. Proszę bardzo o cierpliwe i dokladnie wytlumaczenie i rozwiazanie zadan

1. Panstwo X zostali zaproszeni na imprezę, na której łacznie bylo 6 osob. Kazdy z uczestników znał trzy inne, biorące w niej udział. Udowodnij, że byly w tym gronie cztery osoby, które mogłyby usiaść przy czteroosobowym stole tak, aby kazdy znał swoich sasiadów po prawej i lewej stronie, a nikt nie znał osoby siedzącej naprzeciwko.

2. W pewnym klubie zagościła "wielka osobistość". W klubie było już X klientów i wszyscy znali ową wielką personę, natomiast ona nie znała tam nikogo. Do klubu przyszedł mężczyzna Y który był obcokrajowcem i bardzo chciał poznać "wielką osobistość", ale potrafił spytać tylko " czy znasz tego pana" (wtedy wskazuje palcem)
a) ile pytan [1)pesymistycznie; 2)optymistycznie] musi zadać obecnym, żeby rozponać "wielką osobistość"? tzn, jaka ilosc pytan przy odpowiedniej strategii okaże się wystarczająca?

Bardzo proszę o pomoc.

[TMac]

1. Podejrzewam, że to przez grafy można zrobić. Tzn. rysujesz sobie graf 6-wierzchołkowy, z każdego wierzchołka wychodzą po 3 krawędzie (wierzchołki to osoby, krawędzie to "znajomości") i jakoś pokazujesz, że możesz wybrać... No właśnie, może najpierw napisz co masz wybrać?
2. No chyba przynajmniej optymistyczną wersję to powinieneś wymyślić, może dam podpowiedź w miarę sporą. Załóżmy, że obcokrajowiec podbił akurat do tej "wielkiej osobistości". No i jak się teraz zorientuje, że ona to ona (tzn. jak odróżni ją od innych, bo jest jedna cecha z zadania, która ją odróżnia)?
A pesymistycznie to spójrz tak: z tego rozumowania wyżej wychodzi, że skoro optymistyczna sytuacja zajdzie gdy podejdzie od razu do "wielkiej osobistości" to pesymistyczna chyba wtedy gdy "zostawi ją" na koniec? Ok, a więc podchodzi do normalnego człowieka, powiedzmy Zbyszka. Zaczyna pytać o różnych ludzi. Co może wywnioskować o pozostałych na podstawie tego ilu ludzi i jakich zna Zbyszek? No jeśli nie zna Mieczysława to wiadomo, że Mieczysław nie jest "wielką osobistością" i już mu się zawęża krąg poszukiwań, a więc najgorzej jest gdy Zbyszek zna...? I co z następnym do którego podchodzi?

[rzexnik]

1. A żebym ja wiedzial - takie polecenie jest ( zgadzam sie ze to jest na grafach ale nie mam pojecia jak to wszystko kartkowo udowodnić.
2. Nie nie nie - on może tylko i wyłącznie spytać "czy znasz tego pana". Tylko i wyłacznie bo przyjmijmy ze wszedł do polskiego klubu i jest brazolem. Ale faktycznie, nie pomyslalem o tak prostym rozwiazaniu tego zadania:)

[TMac]

1. A żebym ja wiedzial - takie polecenie jest (

To pomyśl, 4 osoby to ile wierzchołków? I jak mają być te wierzchołki połączone krawędziami?

2. Nie nie nie - on może tylko i wyłącznie spytać "czy znasz tego pana".

A gdzie napisałem, że może coś więcej? Nie pisałem przecież o tym, że Zbyszek jest ubrany jak Elvis i po tym go pozna tylko po jego odpowiedziach. A jak Zbyszek (czyli nasza "wielka osobistość") będzie odpowiadał na każde pytanie "Czy znasz tego gościa?"? No i czym będzie się ten zbiór odpowiedzi różnił od zbioru odpowiedzi każdej innej osoby?

[rzexnik]

Pierwsze rozwiązane.
W drugim można założyć(zał1) optymistycznie, ze ludzie będący w tym barze beda znali siebie nawzajem.
Zatem gdy spytamy kogokolwiek o Zbyszka to odpowie ze albo to wlasnie jest zbyszek albo to jest ktos inny - co wyklucza nam możliwość, że spytalismy właśnie Zbycha. Wiec kiedy spotkamy własnie zbycha to on nam powie, że nikogo nie zna.
Jednakże (zał2) jeżeli osoby bedace w tym barze nie beda znali siebie nawzajem... no to wlasnie klapa.
Poza tym, zrozumienie istoty zadania to jedno, ale napisanie tego "po matematycznemu" to druga sprawa - której wlasnie nie potrafie.
Proszę o dalsze wskazówki i wyrozumiałość

[TMac]

Nie wiem czy dobrze Cię zrozumiałem, ale "optymistyczność" rozwiązania nie może polegać na tym, że założysz coś dodatkowego (tak jak Ty chcesz, że wszyscy znają się nawzajem), ale na tym, że przy odpowiedniej kolejności pytań do odpowiednich osób wszystko (a tutaj właściwie kto jest "wielką osobistością") będziesz wiedział najszybciej jak się da. Także według treści zadania nie mogą mu powiedzieć "tak, to jest znana osobistość", tylko co najwyżej "tak, znam go", a zatem nie możesz sobie powiedzieć, że obcokrajowiec podejdzie do pierwszej osoby i akurat zapyta o Zbyszka, powie ktoś mu "tak, to jest ten znany", więc wystarczy jedno pytanie. Zadanie polega na zawężaniu grona kandydatów na "wielką osobistość" na podstawie odpowiedzi tak i nie na pytanie "czy znasz go?". Miałem na myśli to, że w optymistycznym przypadku podejdziemy od razu do tej znanej osobistości i zaczniemy ją pytać po kolei o wszystkich - jako że nie będzie znała nikogo to po zadaniu \(\displaystyle{ n-1}\) pytań (o ile jest \(\displaystyle{ n}\) osób nie licząc obcokrajowca) będziemy wiedzieli, że to jest ta znana osobistość, bo nie zna nikogo, a kazdy inny człowiek w klubie na \(\displaystyle{ n-1}\) pytań "czy znasz go?" odpowiedziałby na przynajmniej jedno twierdząco (bo przynajmniej jedno byłoby o "wielką osobistość", którą z założeń zadania zna).
I właściwie nie trzeba tego jakoś matematycznie zapisywać o ile to tak przedstawisz (tzn. przynajmniej na moim wydziale to nie jest tak, że rozwiązanie każdego zadania musisz napisać matematycznymi znaczkami jeśli jest takiego typu i możesz poprawnie opisać je słownie).

Co do pesymistycznego przypadku to wpadłem na trochę inny sposób działania tego obcokrajowca, który pozwoli mu na znalezienie odpowiedzi też już po \(\displaystyle{ n-1}\) pytaniach, ale jest trochę bardziej skomplikowany, więc może poczekam aż napiszesz czy zrozumiałeś to, co napisałem wyżej i dam Ci samemu pomyśleć nad pesymistycznym przypadkiem.
Podpowiedź:

Ukryta treść:    

Jeżeli pyta osobę A o to, czy zna B i A mówi, że zna B, to już A nie może być "wielką osobistością", a jeżeli powie, że nie zna B to B nie może być "wielką osobistością".