В начале электронной книги, содержащей 16 страниц, приведена теория и задачи, напечатанные крупным шрифтом, а дальше идут ответы, напечатанные мелким шрифтом. Перед ними напечатан заголовок "Ответы". Мы пытаемся поскорее дойти до ответов, открывая книгу на некоторой странице. За какое наименьшее количество попыток можно узнать номер страницы, на которой начинаются ответы? Гарантируется, что на первой странице приведена только теория. В каждый момент времени показывается только одна страница.

Для того, чтобы найти нужную страницу наиболее быстро, достаточно воспользоваться бинарным алгоритмом поиска. Первую страницу мы не учитываем, так как на ней точно нет ответов. Для начала откроем книгу на середине (9 страница). Если на ней текст напечатан крупным шрифтом, то далее мы откроем середину от второй половины книги.

Вторая половина книги будет занимать 7 страниц и начинаться с 10, потому откроем 13 страницу. Если же на девятой странице текст напечатан мелким шрифтом, то откроем середину первой половины книги, то есть 5 страницу.

Далее, если открытая страница не является нужной, открываем одну из половин уже открытой половины. Так, если мы находимся на странице 13, то далее откроем либо страницу 15, либо 11.

Если страница вновь не та, то открываем последнюю оставшуюся страницу (в зависимости от того, какой шрифт нам попался на странице, мы откроем либо следующую, либо предыдущую страницу). Итого необходимо 4 попытки, чтобы найти нужную страницу.

Ответ: 4.