Условие
Нужно узнать пятизначный номер телефона, задавая вопросы, на
которые возможен ответ "да" или "нет".
За какое наименьшее число вопросов это гарантированно можно сделать (при условии,
что на вопросы даются правильные ответы)?
Подсказка
Надо задавать вопросы так, чтобы каждый последующий вопрос уменьшал
примерно вдвое количество остающихся возможных вариантов.
Решение
Вначале, когда мы ничего не знаем о номере телефона, имеется
10
5=100000 возможных вариантов для телефонного номера.
Мы задаем вопрос: "Верно ли, что номер больше 50000?".
Вне зависимости от ответа, мы уменьшаем вдвое количество
оставшихся возможных вариантов. Итак, после первого вопроса
остается не более 50000 возможных вариантов для телефона.
Если ответ на первый вопрос - "да", то
задаем вопрос: "Верно ли, что номер больше 75000?".
После ответа на этот вопрос останется не более
2500 вариантов.
И так далее - если после n-го вопроса осталось k возможных
вариантов, то можно задать (n+1)-ый вопрос таким образом, чтобы
после ответа на него осталось не более [k/2]+1
возможных вариантов.
Тем самым, получаем следующую зависимость количества
оставшихся возможных вариантов от количества заданных вопросов:
После первого вопроса - 50000 вариантов, после 2-го - 25000,
3 - 12500, 4 - 6250, 5 - 3125, 6 - 1563, 7 - 782,
8 - 391, 9 - 196, 10 - 98, 11 - 59, 12 - 30, 13 - 15, 14 - 8, 15 -
4, 16 - 2, 17 - 1.
Итак, после 17-ти вопросов останется один вариант, т.е. можно
будет угадать телефон.
С другой стороны, за 16 вопросов угадать номер нельзя.
Действительно, после 16-ти вопросов имеется
2
16<100000 последовательностей ответов на вопросы.
Значит, какой-то из последовательностей ответов соответствует по
крайней мере два варианта номера телефона. Таким образом,
если искомый номер - любой из этих двух номеров, то
последовательности ответов на вопросы будут одинаковыми,
т.е. однозначно определить номер не удастся.
Ответ
17 вопросов.
Источники и прецеденты использования
