Wyobraź sobie, że kolega myśli o liczbie od 1 do 100, a Ty masz ją zgadnąć. Po każdej próbie słyszysz tylko: „za mało”, „za dużo” albo „trafiłeś”. Jak grać, żeby wygrywać szybko i za każdym razem? Najgorszy pomysł to zgadywać po kolei: 1, 2, 3… Przy pechu potrzebujesz stu prób. Istnieje strategia, która nigdy nie wymaga więcej niż siedmiu.
Zasada: strzelaj w środek
Za pierwszym razem powiedz 50. Jeśli kolega odpowie „za mało”, wiesz, że liczba leży między 51 a 100. Gdy usłyszysz „za dużo”, wiesz, że jest między 1 a 49. W obu przypadkach wyrzuciłeś z gry połowę liczb jedną próbą. Następną próbę ponownie wykonaj w środku tego, co zostało. I tak dalej.
Dlaczego siedem prób wystarczy?
Zobacz, jak szybko kurczy się liczba możliwości: 100 → 50 → 25 → 12 → 6 → 3 → 1. Po sześciu podziałach zostaje jedna liczba, a siódma próba ją trafia. Inaczej: k prób odróżnia aż 2ᵏ liczb. Siedem prób to 2⁷ = 128 możliwości, a to więcej niż 100. Sześć prób to tylko 2⁶ = 64, za mało na sto liczb.
Ile prób dla różnych zakresów?
Szukamy najmniejszego k, dla którego 2ᵏ jest co najmniej tak duże jak liczba możliwości.
- Liczby od 1 do 10: 2³ = 8 to za mało, 2⁴ = 16 wystarczy, więc 4 próby.
- Od 1 do 20: 2⁴ = 16 to za mało, 2⁵ = 32 wystarczy, więc 5 prób.
- Od 1 do 100: 2⁶ = 64 to za mało, 2⁷ = 128 wystarczy, więc 7 prób.
- Od 1 do 1000: 2¹⁰ = 1024, więc 10 prób.
- Od 1 do miliona: 2²⁰ = 1 048 576, więc 20 prób.
To ogromna oszczędność. Zgadywanie po kolei dla miliona liczb zajmie do miliona prób, a dzielenie na połowy najwyżej dwadzieścia.
Gdzie spotkasz tę metodę?
To samo robisz, szukając słowa w słowniku: otwierasz książkę mniej więcej w połowie, sprawdzasz, czy szukane słowo jest wcześniej czy później, i znów dzielisz to, co zostało. Informatycy nazywają to wyszukiwaniem binarnym. Działa na uporządkowanych danych i potrzebuje liczby kroków rosnącej z logarytmem rozmiaru danych. Dlatego tak szybko wyszukuje wśród milionów elementów. Podobnie działa zabawa w „dwadzieścia pytań”: dobre pytanie „tak lub nie” dzieli możliwości mniej więcej na pół.
Czy zawsze trafisz najszybciej?
Przy odrobinie szczęścia można trafić szybciej, np. losowo od razu w 50. Ale strategia połowienia jest najlepsza w najgorszym przypadku: gwarantuje, że nie przekroczysz określonej liczby prób, niezależnie od tego, jaką liczbę wybrał kolega. Dlatego ma sens, gdy gra toczy się o stawkę.
Zadania
1. Ile prób wystarczy do zgadnięcia liczby od 1 do 50?
Pokaż rozwiązanie
2. Ukryta liczba to 64. Pokaż, jak ją zgadniesz w zakresie 1–100, strzelając w środek i zaokrąglając w dół.
Pokaż rozwiązanie
3. Ile liczb można rozróżnić dwudziestoma pytaniami „tak lub nie”?
Pokaż rozwiązanie
4. Zakres liczb powiększono dwukrotnie, z 1–100 do 1–200. O ile prób więcej trzeba w najgorszym przypadku?
Pokaż rozwiązanie
Typowe błędy
- Zgadywanie po kolei albo „na oko”.
- Strzelanie nie w środek, lecz tuż przy końcu przedziału, co odrzuca mało liczb.
- Zapominanie, że liczba, którą już sprawdziłeś, nie może być odpowiedzią.
Zapamiętaj
- Strzelaj w środek pozostałego przedziału.
- Każda próba odrzuca około połowę możliwości.
- k prób wystarcza dla 2ᵏ liczb: dla 1–100 to 7 prób.
- Podwojenie zakresu to tylko jedna próba więcej.
Sprawdź strategię w grze Zgadnij liczbę.
Komentarze