Strategia w zgadywaniu liczby

Dzielenie na połowy: jak zgadnąć liczbę od 1 do 100 w co najwyżej 7 próbach i dlaczego ta strategia działa zawsze.

Łamigłówki i gry logiczneKlasy 3–8

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.

Środek przedziałuJeśli możliwe liczby to od a do b, strzelaj w (a + b) ÷ 2. Gdy wynik nie jest całkowity, zaokrąglij w dół lub w górę, dowolnie, byle konsekwentnie.

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ół.

Zgadujemy 37Próba 1: 50 – za dużo (zostaje 1–49). Próba 2: (1 + 49) ÷ 2 = 25 – za mało (zostaje 26–49). Próba 3: (26 + 49) ÷ 2 = 37,5, bierzemy 37 – trafione. Trzy próby.

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⁵ = 32 to za mało, 2⁶ = 64 wystarczy. Odpowiedź: 6 prób.

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
Próba 1: 50, za mało (zostaje 51–100). Próba 2: (51 + 100) ÷ 2 = 75, za dużo (zostaje 51–74). Próba 3: (51 + 74) ÷ 2 = 62, za mało (zostaje 63–74). Próba 4: (63 + 74) ÷ 2 = 68, za dużo (zostaje 63–67). Próba 5: (63 + 67) ÷ 2 = 65, za dużo (zostaje 63–64). Próba 6: 63, za mało, więc zostaje 64. Siódma próba trafia.

3. Ile liczb można rozróżnić dwudziestoma pytaniami „tak lub nie”?

Pokaż rozwiązanie
2²⁰ = 1 048 576, czyli ponad milion.

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
Dla 200 liczb: 2⁷ = 128 to za mało, 2⁸ = 256 wystarczy, czyli 8 prób. Dwukrotnie większy zakres to tylko 1 próba więcej.

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ę.

Zagraj w temacie

Komentarze

Dodaj komentarz

Komentarz pojawi się po zatwierdzeniu. Adres e-mail nie będzie widoczny. Nie podawaj danych osobowych dziecka.