Question

В орфографическом словаре 120 страниц, причем на каждой из них по 60 слов. Петя открыл словарь на случайной странице и загадал случайное слово с этой страницы. Сможет ли Витя угадать его за 13 вопросов? А за меньшее число?

Answer 1

Ответ:

Может за 13 вопросов.

Пошаговое объяснение:

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

Сначала угадаем страницу:

120 ∈ (64; 128] = (2^6; 2^7]

Чтобы угадать страницу, нужно 7 вопросов, каждый из которых делит промежуток пополам.

Теперь угадываем слово на странице:

60 ∈ (32; 64] = (2^5; 2^6]

Значит, чтобы угадать слово, нужно задать 6 вопросов.

Всего получается 7 + 6 = 13 вопросов.

За меньшее число можно угадать, если очень сильно повезёт.

Answer 2

Чтобы определить, сможет ли Витя угадать слово, загаданное Петей, за 13 вопросов или за меньшее число, нужно рассмотреть количество возможных вариантов слов, которые Петя мог загадать.

В каждой странице орфографического словаря содержится 60 слов. Предположим, что Петя может загадать любое из этих слов. Тогда общее количество возможных слов составляет 60 * 120 = 7200.

Если Витя задает 13 вопросов, то он может получить 13 различных ответов от Пети: "да" или "нет". Это означает, что максимальное количество различных слов, которые Витя может исключить после каждого вопроса, равно 2^13 = 8192.

Таким образом, Витя сможет исключить не более 8192 различных слов за 13 вопросов. Это число меньше общего количества возможных слов (7200), поэтому существует возможность, что Петя загадал слово, которое Витя не сможет угадать за 13 вопросов.

Значит, Витя не сможет гарантированно угадать слово за 13 вопросов или за меньшее число вопросов.