Петя задумал однозначное натуральное число. Вася может назвать любое натуральное число и спросить, чему равен НОД этого и задуманного чисел. Какое число нужно подобрать Васе, чтобы по ответу наверняка узнать число, задуманное Петей? В ответ запишите наименьшее такое число.
Владимир
Стаж: 3 года 8 месяцев
Баллы: 2926 (Учёный)
#573: Решение задачи №6354
Условие
Итак, могли быть загаданы числа 1, 2, 3, 4, 5, 6, 7, 8, 9.
Сделаем так, чтобы НОД нашего числа и загаданного было равно загаданному. Очевидно, что для этого в наше число должны входить множители из чисел 1, 2, 3, 4, 5, 6, 7, 8, 9.
Так как может быть загадано число 9, то в наше число должно входить два множителя 3.
Так как может быть загадано число 8, то в наше число должно входить три множителя 2.
Так как может быть загадано число 7, то в наше число должен входить множитель 7.
Так как может быть загадано число 6, то в наше число должны входить множители 2 и 3, но они входят в любом случае (см. числа 8 и 9), так что этот случай не рассматриваем.
Так как может быть загадано число 5, то в наше число должен входить множитель 5.
Так как может быть загадано число 4, то в наше число должны входить два множителя 2, но они входят в любом случае (см. число 8), так что этот случай не рассматриваем.
Так как может быть загадано число 3, то в наше число должен входить множитель 3, но он входит в любом случае (см. число 9), так что этот случай не рассматриваем.
Так как может быть загадано число 2, то в наше число должен входить множитель 2, но он входит в любом случае (см. числа 4 или 8), так что этот случай не рассматриваем.
Итого мы получаем наше число как 3 * 3 * 2 * 2 * 2 * 7 * 5 = 2520