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,...…') |
(formatting fixes) |
||
| Line 1: | Line 1: | ||
| + | ==Problem== | ||
| + | Prove that for each <math>n\geq 2</math>, there is a set <math>S</math> of <math>n</math> integers such that <math>(a-b)^2</math> divides <math>ab</math> for every distinct <math>a,b\in S</math>. | ||
| + | |||
| + | ==Solution== | ||
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,...a_n</math> which satisfy the condition. The key is to note that if <math>m=a_1a_2...a_n</math>, then if we define <math>b_i=a_i + km</math> for all <math>i\le n</math>, where k is a positive integer, then <math>a_i \mid b_i</math> and <math>b_i - b_j = a_i - a_j</math>, and so <math>(b_i - b_j)^2 = (a_i - a_j)^2 \mid a_ia_j \mid b_ib_j</math>. | 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,...a_n</math> which satisfy the condition. The key is to note that if <math>m=a_1a_2...a_n</math>, then if we define <math>b_i=a_i + km</math> for all <math>i\le n</math>, where k is a positive integer, then <math>a_i \mid b_i</math> and <math>b_i - b_j = a_i - a_j</math>, and so <math>(b_i - b_j)^2 = (a_i - a_j)^2 \mid a_ia_j \mid b_ib_j</math>. | ||
Let <math>b_{n+1}=m +km</math>. Consider the set <math>T = (b_1,b_2,...,b_n,b_{n+1})</math>. To finish the proof, we simply need to choose a k such that <math>(b_{n+1}-b_i)^2 \mid b_{n+1}b_i</math> for all <math>i\le n</math>. Since <math>(b_{n+1}-b_i)^2 = (m-a_i)^2</math>, simply choose k so that <math>k+1 = (m-a_1)^2(m-a_2)^2...(m-a_n)^2</math>. | Let <math>b_{n+1}=m +km</math>. Consider the set <math>T = (b_1,b_2,...,b_n,b_{n+1})</math>. To finish the proof, we simply need to choose a k such that <math>(b_{n+1}-b_i)^2 \mid b_{n+1}b_i</math> for all <math>i\le n</math>. Since <math>(b_{n+1}-b_i)^2 = (m-a_i)^2</math>, simply choose k so that <math>k+1 = (m-a_1)^2(m-a_2)^2...(m-a_n)^2</math>. | ||
| + | |||
| + | ==See Also== | ||
| + | {{USAMO newbox|year=1998|num-b=4|num-a=6}} | ||
Revision as of 14:20, 3 June 2011
Problem
Prove that for each 
, there is a set 
of 
integers such that 
divides 
for every distinct 
.
Solution
Proof by induction. For n=2, the proof is trivial, since 
satisfies the condition. Assume now that there is such a set S of n elements, 
which satisfy the condition. The key is to note that if 
, then if we define 
for all 
, where k is a positive integer, then 
and 
, and so 
.
Let 
. Consider the set 
. To finish the proof, we simply need to choose a k such that 
for all . Since 
, simply choose k so that 
.
See Also
| 1998 USAMO (Problems • Resources) | ||
| Preceded by Problem 4 |
Followed by Problem 6 | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All USAMO Problems and Solutions | ||
