Difference between revisions of "1998 USAMO Problems/Problem 5"

Latest revision as of 08:44, 20 July 2016

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

@@ Line 10: / Line 10: @@
 {{USAMO newbox|year=1998|num-b=4|num-a=6}}
 {{MAA Notice}}
+[[Category:Olympiad Number Theory Problems]]

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

Page

Toolbox

Search

Difference between revisions of "1998 USAMO Problems/Problem 5"

Latest revision as of 08:44, 20 July 2016

Problem

Solution

See Also