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:
- Pojedyncza rozmowa jest jednostronna - jeden szpieg dzwoni do drugiego i zdradza mu wszystkie sekrety jakie zna, a tamten milczy.
- 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:
