Pupilla Libertatis
Myślę, politykuję, rozważam, polemizuję, szukam, prowokuję, dyskutuję, dociekam, analizuję, filozofuję.
119 obserwujących
1462 notki
1850k odsłon
717 odsłon

Stu szpiegów

Wykop Skomentuj38
Mamy wakacje więc wracam do mojego cyklu notek zagadkowych. Leżycie sobie na plaży i czytacie, nie? Więc zamiast czytać książki, czy jakieś głupie blogi, spróbujcie porozwiązywać zagadki. Dziś jest nowa, ale można wrócić do starych - są w lubczasopiśmie: Zagadki. Nie zalecam czytania - polecam myślenie.
A tymczasem dziś mamy stu szpiegów. Każdy z nich zna jakiś sekret - każdy inny. Czyli jest sto różnych sekretów. Każdy szpieg ma telefon komórkowy i zna numery do wszystkich innych szpiegów. Ale niestety nie mają oni opcji rozmów konferencyjnych - jeden szpieg może jednorazowo zadzwonić tylko do jednego innego szpiega - nie może dzwonić do kilku na raz. Szpiedzy są od siebie daleko i mogą się komunikować tylko telefonicznie.
No i teraz oni do siebie dzwonią i zdradzają sobie nawzajem wszystkie sekrety jakie znają. Jaka jest minimalna liczba rozmów, po której wszyscy szpiedzy będą znać wszystkie sekrety?
Zagadka ta ma dwa warianty:
  1. Pojedyncza rozmowa jest jednostronna - jeden szpieg dzwoni do drugiego i zdradza mu wszystkie sekrety jakie zna, a tamten milczy.
  2. Pojedyncza rozmowa jest dwustronna - jeden szpieg dzwoni do drugiego i zdradza mu wszystkie sekrety jakie zna, a tamten w tym samym połączeniu zdradza mu wszystkie sekrety, które sam zna.
Proszę podać minimalną liczbę rozmów, po której wszyscy szpiedzy będą znać wszystkie sekrety w wariancie 1 i 2. No i oczywiście druga, wielokroć trudniejsza część zagadki: należy udowodnić, że odpowiedź jest poprawna, czyli, że nie istnieje mniejsza liczba rozmów. No i na koniec podaję jeszcze trudniejszy wariant zagadki: szpiegów jest nie stu, ale N > 1.
Wariant 1 jest bardzo łatwy do rozwiązania, a wariant 2 bardzo trudny. Wariant 1 rozwiąże każdy od razu. Liczbę będącą rozwiązaniem w wariancie 2 poda prawie każdy po dłuższym myśleniu, ale mało kto poda dowód w wariancie 2 dla N szpiegów.
 
Grzegorz GPS Świderski

PS. Inne ciekawe zagadki:

W sprawie sztuki filmowej  <- poprzednia notka
następna notka -> Obywatel

 

Wykop Skomentuj38
Ciekawi nas Twoje zdanie! Napisz notkę Zgłoś nadużycie

Więcej na ten temat

Salon24 news

Co o tym sądzisz?

Inne tematy w dziale Technologie