Question

В англо-русском словарике 80 страниц, на каждой из который по 50 слов. Петя открыл словарь на случайной странице и загадал случайное слово с этой страницы. Сможет ли Витя угадать его за 12 вопросов? Петя отвечает на вопросы только "да" или "нет". (Если вы считаете, что Витя сможет отгадать, то нужно написать эти 12 вопросов. Если вы считаете, что он не сможет, то нужно доказательство этого факта)

Answer 1

В данном случае наилучшей является стратегия половинного деления. Сначала определяем страницу. Будем делить каждый раз количество страниц, содержащих нужную, пополам.
Первый вопрос: "Нужная страница имеет номер больше 40?" Если да, то рассматриваем страницы с 41 по 80, если нет - то страницы с 1 до 40.
Второй вопрос для случая, когда номер страницы был больше 40 будет выглядеть так: "Нужная страница имеет номер больше 60?". А если номер страницы был не больше 40, то спрашиваем "Нужная страница имеет номер больше 20?".
При такой схеме количество необходимых вопросов будет равно 7 ( 2⁶<80<2⁷).

Найдя нужную страницу по такой же схеме ищем номер слова (от 1 до 50).
Поскольку 2⁵<50<2⁶, то потребуется задать 6 вопросов.

7 вопросов для определения номера страницы и 6 для определения номера слова на ней - всего 13 вопросов. Поэтому за 12 вопросов отгадать слово не удастся.

В то же время, если бы можно было пронумеровать все слова от 1 до 4000 (50х80=4000) и задавать вопросы по порядковым номерам слов, то 12 вопросов хватило бы (2¹¹<4000<2¹²)