Чтобы угадать единицу, Мише понадобится проверить как минимум все простые делители от 2 до 19, так что не менее восьми вопросов. Покажем, что этого хватит.
До тех пор, пока Саша отвечает "нет", будем перебирать эти делители в порядке возрастания. Пусть он впервые скажет "да" на:
- двойке. Осталось десять чётных чисел. Вопросом "делится ли на 4?" мы сократим это количество вдвое: осталось пять чисел и шесть вопросов. Очевидно, перебрав в качестве делителей эти числа, от большего к меньшему, мы найдём нужное максимум за 4 вопроса.
- тройке. Возможные варианты - 3, 9, 15. Достаточно ещё двух вопросов, и два уже было использовано.
- 5, 7, 11, 13, 17 или 19 - названное простое число. Поскольку делимость на 2 и 3 мы уже исключили, они сами остаются единственными числами, обладающими нужной делимостью на этом диапазоне.
- на все вопросы ответит "нет" - единица.
В задаче не указано, каким образом Миша задаёт вопросы. Если все вопросы Миша задаёт сразу, и лишь потом получает ответы Саши, то потребуется не менее 12 вопросов (в противном случае единичку не отличить от простого числа, а простое - от степени простого (скажем, двойку от четвёрки)). Если же постановка каждого вопроса, кроме первого, зависит от ответа на предыдущий, тогда, очевидно, 8.
08.01.2012, 12:20 
