Областная олимпиада по математике, 2004 год, 10 класс

Можно ли найти множество $S$ из 2004 различных целых положительных чисел такое, что для любых $a$, $b \in S$ имеет место равенство ${\mathop{\hbox{НОД}}\nolimits} (a,b)=|a-b|$?

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. Можно.
Построим данное множество индукцией по числу элементов $n > 2.$ При $n = 2$ пусть $a = 3,$ $b = 2.$ Если такое множество из $k$ чисел уже построено, то для построения набора из $k + 1$ числа достаточно прибавить к каждому из них по $N!$ и добавить $(k +1)$-е число, равное $N!$, где $N$ — число, большее любого из имевшихся чисел.

Ответ: нельзя

Решение. Рассмотрим два произвольных элемента множества $S$ :$a_i$ и $a_j$. Рассмотрим два случая:

1) НОД$(a_i;a_j)=1$, то есть эти два числа взаимопростые. Имеем $$1=|a_i-a_j|$$

2) НОД$(a_i;a_j)>1$, то есть эти два числа имеют общий множитель $m>1$ . Имеем $m=m|a_i-a_j|;$ откуда$$1=|a_i-a_j|$$

То есть для любых $a_i$ и $a_j$ должно выполниться условие $1=|a_i-a_j|$. Понятно, что 2004 целых и неравных между собой целых чисел, удовлетворяющих этому условию, собрать нельзя. Отсюда следует, что $S$ не существует.

Можно построить пример такого множества.