Mam wymyśloną przyjaciółkę, która ma na imię Ada. Niech Ada zapamięta liczbę od 1 do 1000. Twoim zadaniem jest znalezienie numeru, zadając mu pytania, aby dowiedzieć się, co to za numer. Ale niech od początku będą jakieś zasady. Załóżmy na przykład, że Ada zawsze mówi prawdę. Dodatkowo na zadane pytania możesz odpowiedzieć tylko „tak”, „nie” lub „nie wiem”. Nasza łamigłówka zadaje ci to pytanie. Jakie minimum pytań musisz zadać, aby dowiedzieć się, jaki numer ma Twój znajomy?
Jeśli nie do końca rozumiesz, podpowiemy. Zacznij od zapytania, czy numer, który ma, mieści się w przedziale od 1 do 500 (od 1 do 500 włącznie). Kiedy odpowiesz na to pytanie, liczba kandydatów na numer, który musisz znaleźć, zmniejszy się o połowę. Następnie kontynuuj w ten sposób, za każdym razem dzieląc pozostałe liczby na dwie równe części. Załóżmy na przykład, że Ada miała numer 358. W takim przypadku pytania, które powinieneś mu zadać, brzmiałyby: (Obok nich są odpowiedzi Ady.)
Czy Twój numer mieści się w przedziale od 1 do 500? Tak.
1 i 250? NIE.
251 i 375? Tak.
251 i 313? NIE.
314 i 345? NIE.
346 i 361? Tak.
346 i 354? NIE
355 i 358? Tak
355 i 356? NIE
358? Tak!
Zadając takie pytania, na pewno znajdziesz liczbę, którą twój przyjaciel ma na myśli w 10 pytaniach. Cóż, czy można uzyskać solidny wynik przy mniejszej liczbie pytań? Odpowiedź brzmi tak! Jeśli skupisz się na odpowiedziach na powyższe pytania, nasze pytania testowe odpowiadają tylko tak lub nie ADA.
Jednak od początku wiedzieliśmy, że Ada faktycznie może nam odpowiedzieć tak, nie lub nie wiem. Musimy odpowiedzieć na pytania wyboru z trzema możliwymi odpowiedziami. W rezultacie, biorąc pod uwagę odpowiedź „nie wiem”, obecne liczby można każdorazowo zmniejszyć o jedną trzecią.
Rozwiązaniem jest zapamiętanie liczby
Zróbmy szybki eksperyment, aby lepiej zrozumieć. Na przykład Twoje pierwsze pytanie może brzmieć: „Myślę o liczbie między 333 a 666. Czy liczba, którą masz na myśli, jest mniejsza niż moja liczba? W tym przypadku, jeśli Ada odpowie twierdząco, wiesz, że jej liczba jest między 1 a 332. Ale jeśli odpowie nie, wiesz, że jej liczba wynosi między 667 a 1000. Ada odpowiada: Nie wiem, ale wiesz, że jej liczba to między 333 a 666.
Zmniejszyłeś cel do jednej trzeciej tego, co było wcześniej. Jeśli zawężasz cel o jedną trzecią na raz, możesz znaleźć numer Ady w siedmiu pytaniach. Należy tutaj zauważyć, że konieczne jest zadawanie pytania, które zadaliśmy powyżej, za każdym razem w środku co trzeciego interwału.
Każde pytanie możesz utworzyć w następujący sposób:[a + (b-a)/3] z [a + 2(b-a)/3] Myślę o numerze. Czy twój numer jest mniejszy niż mój? Spróbujmy teraz. Weźmy na przykład liczbę Ada 680. Poniżej znajduje się eksperyment, w jaki sposób znaleźć tę liczbę w 7 krokach.
Między 333 a 666? Numer (w tym 333 i 666)
778 i 890 nr
704 i 738 nr
679 i 691 Nie wiem
683 i 687 am
680 i 681 nie wiem (w tym 680 i 681)
680 mil? Tak.
W tym przypadku pokonałeś Adę jej własną bronią.
„Guru podróży. Webaholik. Miłośnik Twittera. Hipsterski znawca bekonu. Wielokrotnie nagradzany odkrywca”.