Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(Created page with 'Proof by induction. For n=2, the proof is trivial, since <math>S = (1,2)</math> satisfies the condition. Assume now that there is such a set S of n elements, <math>a_1, a_2,...…')
(No difference)

Revision as of 13:17, 3 June 2011

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1998_USAMO_Problems/Problem_5&oldid=39061"