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

(Solution: removed solution tag)
(added box)
Line 9: Line 9:
 
    
 
    
 
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 (mod 2)</math> also, so <math>S \equiv 9 (mod 10)</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 (mod 2)</math> also, so <math>S \equiv 9 (mod 10)</math>.
 +
 +
==See Also==
 +
{{USAMO newbox|year=1998|before=First Problem|num-a=2}}

Revision as of 10:44, 6 June 2011

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

If $S=|a_1-b_1|+|a_2-b_2|+\cdots +|a_{999}-b_{999}|$, then $S \equiv 1+1+\cdots + 1 \equiv 99 \equiv 4 (mod 5)$.

For integers M, N we have $|M-N| \equiv M-N \equiv M+N (mod 2)$.

So 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 (mod 2)$ also, so $S \equiv 9 (mod 10)$.

See Also

1998 USAMO (ProblemsResources)
Preceded by
First Problem
Followed by
Problem 2
1 2 3 4 5 6
All USAMO Problems and Solutions
Invalid username
Login to AoPS