1998 USAMO Problems/Problem 5

Problem

Prove that for each $n\geq 2$, there is a set $S$ of $n$ integers such that $(a-b)^2$ divides $ab$ for every distinct $a,b\in S$.

Solution

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$.

See Also

1998 USAMO (ProblemsResources)
Preceded by
Problem 4
Followed by
Problem 6
1 2 3 4 5 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png