Сколько минимальных вопросов должен задать Вася, чтобы точно узнать номер страницы, которую отметила карандашом Маша?

Паровоз

19

Чтобы определить номер страницы, которую отметила карандашом Маша, Васе нужно задать вопросы, которые сужают возможные варианты ответа до одного.

Предположим, что книга содержит \(n\) страниц. Вася может задать последовательные вопросы, чтобы определить номер страницы:
1. Вопрос: "Маша отметила страницу в первой половине книги?" Если ответ "Да", то остается только первая половина книги, то есть страницы от 1 до \(n/2\).
2. Вопрос: "Маша отметила страницу во второй половине первой половины книги?" Если ответ "Да", то остается только первая четверть книги, то есть страницы от 1 до \(n/4\).
3. Вопрос: "Маша отметила страницу в первой половине второй половины первой половины книги?" Если ответ "Да", то остается только первая восьмая часть книги, то есть страницы от 1 до \(n/8\).
И так далее...

Таким образом, Васе потребуется \(k\) вопросов, где \(k\) - минимальная степень двойки, большая или равная \(n\). Решим неравенство \(2^k \geq n\) относительно переменной \(k\):
\[
\begin{align*}
2^k &\geq n \\
k &\geq \log_2{n} \\
\end{align*}
\]

Таким образом, Васе потребуется задать \(\lceil \log_2{n} \rceil\) вопросов, чтобы точно узнать номер страницы, которую отметила Маша. Возьмем, например, книгу с 500 страницами. В этом случае, Васе потребуется \(\lceil \log_2{500} \rceil = \lceil 8.965784 \rceil = 9\) вопросов.

Таким образом, Васе нужно задать минимум 9 вопросов, чтобы точно узнать номер страницы, которую отметила Маша.