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

(Solution)
Line 4: Line 4:
 
== Solution ==
 
== Solution ==
  
If <math>S=|a_1-b_1|+|a_2-b_2|+\cdots +|a_{999}-b_{999}|</math>, then <math>S \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>.
 
   
 
   
For integers M, N we have <math>|M-N| \equiv M-N \equiv M+N \bmod{2}</math>.
+
Also, for integers M, N we have <math>|M-N| \equiv M-N \equiv M+N \bmod{2}</math>.
 
    
 
    
So 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 <math>S \equiv 9\bmod{10}</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.
  
 
==See Also==
 
==See Also==

Revision as of 00:08, 13 February 2015

Problem

Suppose that the set $\{1,2,\cdots, 1998\}$ has been partitioned into disjoint pairs $\{a_i,b_i\}$ ($1\leq i\leq 999$) so that for all $i$, $|a_i-b_i|$ equals $1$ or $6$. Prove that the sum \[|a_1-b_1|+|a_2-b_2|+\cdots +|a_{999}-b_{999}|\] ends in the digit $9$.

Solution

Notice that $|a_i - b_i| \equiv 1 \pmod 5$, so $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}$.

Also, for integers M, N we have $|M-N| \equiv M-N \equiv M+N \bmod{2}$.

Thus, we also have $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}$ also, so by the Chinese Remainder Theorem $S \equiv 9\bmod{10}$. Thus, $S$ ends in the digit 9, as desired.

See Also

1998 USAMO (ProblemsResources)
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. AMC logo.png

Invalid username
Login to AoPS