1998 USAMO Problems/Problem 5

Proof by induction. For n=2, the proof is trivial, since $S = (1,2)$ satisfies the condition. Assume now that there is such a set S of n elements, $a_1, a_2,...a_n$ which satisfy the condition. The key is to note that if $m=a_1a_2...a_n$ , then if we define $b_i=a_i + km$ for all $i\le n$ , where k is a positive integer, then $a_i \mid b_i$ and $b_i - b_j = a_i - a_j$ , and so $(b_i - b_j)^2 = (a_i - a_j)^2 \mid a_ia_j \mid b_ib_j$ .

Let $b_{n+1}=m +km$ . Consider the set $T = (b_1,b_2,...,b_n,b_{n+1})$ . To finish the proof, we simply need to choose a k such that $(b_{n+1}-b_i)^2 \mid b_{n+1}b_i$ for all $i\le n$ . Since $(b_{n+1}-b_i)^2 = (m-a_i)^2$ , simply choose k so that $k+1 = (m-a_1)^2(m-a_2)^2...(m-a_n)^2$ .

Page

Toolbox

Search

1998 USAMO Problems/Problem 5