Артём загадал натуральное число N ⩽ 12. Вася может назвать натуральное число M, после чего Артём сообщит ему, чему равен наибольший общий делитель чисел M и N?

Решение. Докажем, что НОД(M, k) = k для всех 1 ⩽ k ⩽ 12. Предположим, что это неверно. Выберем наименьшее k, для которого это не выполняется. Пусть НОД(M, k) = l ̸= k. Поскольку l является делителем k, то l < k. Но тогда НОД(M, k) = НОД(M, l) = l, и в случае, если Артём ответит число l, Вася не
сможет гарантированно определить загаданное число (оно может быть равно и k, и l). Противоречие.
Итак, НОД(M, k) = k для всех 1 ⩽ k ⩽ 12, т. е. M делится на все числа от 1 до 12. Наименьшее такое число равно наименьшему общему кратному чисел от 1 до 12, т. е. 2^3 · 3^2 · 5 · 7 · 11 = 27720. Очевидно, такое число подходит под условие, ведь для разных возможных значений N получаются разные ответы Артёма.
Ответ: 27720.