We say that distinct positive integers $n, m$ are $friends$ if $\vert n-m \vert$ is a divisor of both ${}n$ and $m$. Prove that, for any positive integer $k{}$, there exist $k{}$ distinct positive integers such that any two of these integers are friends.
Problem
Source: Estonia TST 2023
Tags: combinatorics
starchan
03.08.2023 13:38
Problem is trivialised by this USA TST problem.
giannis2006
03.08.2023 15:28
I will prove inductively that for all $N>1$ there exist a set of $N$ distinct positive integers satisfying the condition. For $N=2$ we have the set ${2,4}$. Suppose we have the set $ {a_1, ..., a_N} $ and let $P=\prod_{i=1}^{N} a_i*\prod_{1\leq i<j \leq N} (a_i-a_j)^2 $ Now for the inductive step $N->N+1$ choose the following set of $N+1$ numbers: $a_1+P,..., a_N+P, P$. It is trivial that all $N+1$ nunmbers are distinct. Obviously we have that $(a_i+P)-P=a_i$ divides both $a_i+P$ and $P$ for all $1 \leq i \leq N$ beacuse of the choice of $P$. Also we have that $(a_i+P)-(a_j+P)=a_i-a_j$ which also divides both $a_i+P$ and $a_j+P$ for all $1\leq i<j \leq N$ because of the choice of $P$ and the inductive ypothesis. Hence, from induction the proof is completed.