Математикадан облыстық олимпиада, 2003-2004 оқу жылы, 10 сынып

Әрбір $a,b\in S$ үшін ЕҮОБ$(a,b)={|a-b|}$ болатындай әртүрлі 2004 оң бүтін саннан тұратын $S$ жиынын табуға бола ма?

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

Комментарии от администратора Комментарии от администратора №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$ не существует.

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