Puzzle #71. Номер телефона

Разбор

Так как в качестве ответа мы получим либо да, либо нет, то следует использовать стратегию, при которой каждый последующий вопрос уменьшал бы примерно вдвое кол-во возможных вариантов.

Итак, в самом начале мы имеем 10^5 = 100000 всевозможных вариантов для номера телефона. Тогда 1й вопрос будет таким: "Верно ли, что ваш номер больше 50000 ?" Таким образом, вне зависимости от ответа, мы сокращаем кол-во вариантов вдвое.

После 1го вопроса остается не более 50000 вариантов. Во 2м вопросе повторяем стратегию, уменьшая кол-во вариантов вдвое. После 2го ответа останется не более 25000 вариантов. 

Получаем следующую зависимость. После 1го вопроса - 50000, после 2го - 25000, 3-го - 12500, 4го - 6250, 5го - 3125, 6го - 1563, 7го - 782, 8го - 391, 9го - 196, 10го - 98, 11го - 49, 12го - 25, 13го - 13, 14го - 7, 15го - 4, 16го - 2, 17го - 1.

Необходимо минимум 17 вопросов для однозначного определния номера телефона.