Difference between revisions of "1998 USAMO Problems/Problem 1"
(→Solution) |
m (→Solution) |
||
| Line 6: | Line 6: | ||
Notice that <math>|a_i - b_i| \equiv 1 \pmod 5</math>, so <math>S=|a_1-b_1|+|a_2-b_2|+\cdots +|a_{999}-b_{999}| \equiv 1+1+\cdots + 1 \equiv 999 \equiv 4 \bmod{5}</math>. | Notice that <math>|a_i - b_i| \equiv 1 \pmod 5</math>, so <math>S=|a_1-b_1|+|a_2-b_2|+\cdots +|a_{999}-b_{999}| \equiv 1+1+\cdots + 1 \equiv 999 \equiv 4 \bmod{5}</math>. | ||
| − | Also, for integers M, N we have <math>|M-N| \equiv M-N \equiv M+N \bmod{2}</math>. | + | Also, for integers <math>M, N</math> we have <math>|M-N| \equiv M-N \equiv M+N \bmod{2}</math>. |
Thus, we also have <math>S \equiv a_1+b_1+a_2+b_2+\cdots +a_{999}+b_{999} \equiv 1+2+ \cdots +1998 \equiv 999*1999 \equiv 1 \bmod{2}</math> also, so by the Chinese Remainder Theorem <math>S \equiv 9\bmod{10}</math>. Thus, <math>S</math> ends in the digit 9, as desired. | Thus, we also have <math>S \equiv a_1+b_1+a_2+b_2+\cdots +a_{999}+b_{999} \equiv 1+2+ \cdots +1998 \equiv 999*1999 \equiv 1 \bmod{2}</math> also, so by the Chinese Remainder Theorem <math>S \equiv 9\bmod{10}</math>. Thus, <math>S</math> ends in the digit 9, as desired. | ||
Revision as of 23:09, 12 February 2015
Problem
Suppose that the set 
has been partitioned into disjoint pairs 
(
) so that for all 
, 
equals 
or 
. Prove that the sum ![\[|a_1-b_1|+|a_2-b_2|+\cdots +|a_{999}-b_{999}|\]](http://latex.artofproblemsolving.com/c/9/8/c986d59da1a579f6d783633ebe60315bc9ede782.png)
ends in the digit 
.
Solution
Notice that 
, so 
.
Also, for integers 
we have 
.
Thus, we also have 
also, so by the Chinese Remainder Theorem 
. Thus, 
ends in the digit 9, as desired.
See Also
| 1998 USAMO (Problems • Resources) | ||
| Preceded by First Question |
Followed by Problem 2 | |
| 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. 
