Азиатско-Тихоокеанская математическая олимпиада, 2004 год

Определите все конечные непустые множества $S$ натуральных чисел, для которых $\frac{i+j}{(i,j)}$ является элементом $S$ для всех чисел $i$ и $j$ из $S$.

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

$P(i,j)=(i,i) \rightarrow 2 \in S$

Допустим что $S$ имеет больше одного элемента

$(i)P(i,j)=(2,2k+1)$

$\dfrac{2k+3}{(2,2k+1)}=2k+3$

$P(i,j)=(2,2k+3) \rightarrow 2k+5 \in S$

Продолжая получим что каждое нечетное число большее чем $2k+1$ входит в множество $S$

Но $S$ конечное. Противоречие

$(ii)P(i,j)=(2,2k)$

$\dfrac{2k+2}{2}=k+1$

$P(i,j)=(2,k+1)$

$k+1 \ne 2l+1$

$\dfrac{k+3}{(2,k+1)}=\dfrac{k+1}{2}+1$

$2k,\dfrac{2k+2}{2},\dfrac{2k+2}{4}+1,\dots, \dfrac{2k+2}{2^l}+1 \in S$

Если $\dfrac{2k+2}{2^l}+1 \ne 2$ то противоречие

Т.к. в $S$ конечное кол-во элементов

$2k+2=2^l$

Предыдущий элемент:

$\dfrac{2k+2}{2^{l-1}}+1=3$

Противоречие по $(i)$

Значит в $S$ один элемент

Ответ: $S=2$

не пон, а например с $3,5$ выходит же не целое число