Задача выглядит простой, но в ней скрыто несколько интересных моментов: нужно определить все возможные варианты числа, подумать о том, как Ване можно сократить пространство поиска и какие вопросы помогут угадать число за минимальное количество ходов.
Постановка задачи
Таня записала в блокнот трехзначное целое число, которое делится на 28 без остатка. Ване известно только это условие; он может задавать вопросы типа «число больше X?», «число чётное?», «какая цифра на месте сотен?» и т.д., пока не угадает точное значение.
Все возможные числа
Сначала найдём все трёхзначные числа, кратные 28.
- Наименьшее трёхзначное число – 100. Делим 100 на 28: 100 ÷ 28 ≈ 3,57 → следующее целое кратное – 28·4 = 112.
- Наибольшее трёхзначное число – 999. Делим 999 на 28: 999 ÷ 28 ≈ 35,68 → последнее целое кратное – 28·35 = 980.
- Таким образом, все подходящие числа образуют арифметическую прогрессию: 112, 140, 168, …, 980 с шагом 28.
Количество членов прогрессии:
n = ((последний – первый) / шаг) + 1 = ((980 – 112) / 28) + 1 = (868 / 28) + 1 = 31 + 1 = 32
Стратегии угадывания
Чтобы минимизировать количество вопросов, Ване полезно использовать метод двоичного поиска (или его вариант, адаптированный под дискретное множество).
Вариант 1: Вопросы «больше/меньше»
- Первый вопрос: «Число больше 546?» (среднее значение между 112 и 980 ≈ 546).
- В зависимости от ответа диапазон сужается примерно вдвое.
- После каждого вопроса остаётся не более половины оставшихся вариантов.
- Для 32 вариантов достаточно
⌈log₂ 32⌉ = 5вопросов.
Вариант 2: Вопросы о цифрах
Поскольку число трёхзначное, можно спрашивать отдельно о каждой позиции:
- «Какая цифра на месте сотен?» – сужает варианты до группы из 10‑12 чисел (например, все числа от 100 до 199, кратные 28).
- Затем вопрос о цифре десятков – дальше сокращает до 1‑2 вариантов.
- Наконец, вопрос о единице – определяет число точно.
- В худшем случае потребуется 3 вопроса, но иногда достаточно 2, если после первого ответа остаётся единственный кандидат.
Вариант 3: Комбинированный подход
Можно сначала спросить о чётности (все кратные 28 уже чётны, поэтому этот вопрос бесполезен), затем спросить о делимости на 7 или 4 (так как 28 = 4·7). Например:
- «Делится ли число на 7 без остатка?» – ответ всегда «да», так что не помогает.
- «Делится ли число на 8?» – это уже полезно, потому что среди кратных 28 только некоторые также кратны 8 (например, 112, 168, 224 …).
Такой подход может сократить число вариантов до 8‑10 после одного вопроса, а затем потребуется ещё 3‑4 вопроса типа «больше/меньше».
Пример диалога (вариант с вопросами о цифрах)
Таня: Я записала число.
Ваня: Какая цифра на месте сотен?
Таня: 6.
Ваня: Какая цифра на месте десятков?
Таня: 2.
Ваня: Какая цифра на месте единиц?
Таня: 4.
Ваня: Значит, число 624. Проверяю: 624 ÷ 28 = 22,33… Ой, не делится!
Таня: Я ошиблась, давайте снова.
Ваня: (повторяет вопросы) … finalement получает 616, потому что 616 ÷ 28 = 22.
В этом примере видно, что вопросы о цифрах позволяют быстро сузить поиск, но требуют проверки полученного числа на делимость на 28.
Задача «Таня написала в блокноте трехзначное число, делящееся на 28; Ване нужно угадать его» демонстрирует, как даже seemingly простая условие приводит к конечному набору из 32 вариантов. Применяя логические методы – двоичный поиск, вопросы о позициях цифр или проверку дополнительных делимостей – Ваня может угадать число за минимальное количество шагов (от 2 до 5 вопросов в зависимости от выбранной стратегии).
Таким образом, ключ к успеху – системное сужение пространства возможных ответов и использование информации о структуре числа (его разрядов) совместно с арифметическими свойствами делимости на 28.