Question

Старик Хоттабыч придумал набор из n различных натуральных чисел таких, что все, кроме одного числа, делятся на 2, все, кроме двух чисел, делятся на 3, . . . , все, кроме n−1 чисел, делятся на n. Для какого наибольшего значения n это возможно?

Answer 1

Решение:

Представим, что получилось собрать такой набор из $n$ чисел, причем $n$ больше или равно $6$.

По условию, ровно $n-1$ число делится на $2$ ("все, кроме одного числа, делятся на $2$"), и ровно $n-2$ чисел делятся на $3$ ("все, кроме двух чисел, делятся на $3$"). Это означает, что на $6$ могут делиться максимум $n-2$ числа (когда все числа, делящиеся на $3$ также делятся на $2$), а минимум - $n-3$ числа (когда в наборе есть одно число, делящееся на $3$, но не делящееся на $2$).

Но нам сказано, что на $6$ должны делиться ровно $n-5$ чисел, а остальные $5$ чисел на $6$ не делятся. Но выходит, что на $6$ не делятся либо $2$ числа, либо $3$ числа (но не $5$ чисел).

Значит, $n=6$ - такое невозможно.

При этом $n=5$ уже имеет место быть (во всяком случае, мне так кажется). В этом случае набор чисел будет, например, такой: $\{1,2,6,24,120 \}$.

Ответ: n = 5 .