; Trivial: Zadanie dla chętnych: Adam i Marek zabawiali się w następującą grę. Adam wymyślał liczbę z zakresu od 0 do n−1. Zadaniem Marka było odgadnąć tę liczbę zadając Adamowi pytania, na które mógł odpowiadać jedynie TAK lub NIE. Znajdź najmniejszą liczbę pytań, po której Marek zawsze odnajdzie szukaną liczbę.

bart: ja bym ciagle zawezal o polowe, ale nie chce mi sie kombinowac z zapisem

Jack: pyta w której z połówek jest liczba, potem znów w której połówce itd. Tych kroków będzie hm... log₂ (n−1)? Strzelam...

Trivial: Zauważ, że jest n liczb do wyboru. Odpowiedź dla n postaci potęgi dwójki to log₂n, ale ja pytałem o odpowiedź dla dowolnego n.

Jack: jeśli n jest zupełnie dowolną liczbą n>1, to wydaje mi się, że może tak w nieskończoność zgadywać...

Trivial: Domyślnie n jest naturalne.

Jack: a idź Ty!

Trivial: ok.

Jack: nie chce liczyć, ale może tak: log₂ (n−1) +n−1 (co drugi krok możemy trafiać na liczbę nieparzystą i po podzieleniu przez 2 dostać ułamek postaci k,5 − wówczas należy zapytać o dwie liczby k oraz k+1). Generalnie wychodzę z założenia, że mechanizm dzielenia na połowy jest najszybszy...

Jack: hmm chociaż... ciężko uwierzyć, że to że liczba nie jest postaci n=2^k miało powodować przyrost aż o n−1...

Wezyr: Wystarczy, zapisać liczbę n−1 w zapisie dwójkowym. Minimalna ilość pytań to ilość cyfr w zapisie dwójkowym tej liczby. Przykład liczby z zakresu (0 − 7) 7₁₀ = 111₂ należy zadać 3 pytania.

Trivial: Odpowiedź to: sufit z lgn, gdzie lgn = log₂n. Po podpowiedzi Wezyra to już proste.