Sum Differences. Topic: Algebra/NT. Level: Olympiad.

Problem: (USAMO 1998 - #1) Suppose that the set $\{1,2,\ldots, 1998\}$ has been partitioned into disjoint pairs $\{a_i,b_i\} (1\le i\le 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: Let's make things simpler by first getting rid of the absolute values by assuming WLOG that $a_i > b_i$. If this is not true, we can simply switch the two and we have the same problem.

So the given sum becomes $\displaystyle \sum a_i-\sum b_i$ (all sums taken from $i = 1$ to $i = 999$).

But we also have $ \displaystyle \sum a_i+\sum b_i = 1+2+\cdots+1998 = \frac{(1998)(1999)}{2} = 999 \cdot 1999$, which is odd.

Hence $\displaystyle \sum a_i-\sum b_i$ is odd as well (since both sums have to be integers).

But $\displaystyle \sum a_i-\sum b_i$ is the sum of $999$ numbers, all of which are $1$ or $6$. Since it's odd, however, we know that there must be an even number of $6$'s. Let $2x$ be the number of $6$'s.

Then $\displaystyle \sum a_i-\sum b_i = 6(2x)+1(999-2x) = 10x+999 \equiv 9 \pmod{10}$ as desired. QED.

--------------------

Comment: A pretty easy USAMO problem, but it is a #1, so yeah. And no practice problems for today since I can't think of any. I might add some later.