1998 USAMO P1

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$.

Easy Solution:

Let there be $x$ six-pairs $(a_i, b_i)$ such that $|a_i - b_i|=6$. Then, there are $999-x$ one-pairs such that $|a_i - b_i| = 1$. The given expression evaluates to$$6x + (999-x) = 5x + 999$$ Since this is already $4 \pmod 5$, it is enough to show that it is also $1 \pmod 2$. Note that $$|a_1-b_1|+|a_2-b_2|+\cdots +|a_{999}-b_{999}| \equiv  a_1-b_1+a_2-b_2+\cdots +a_{999}-b_{999} \equiv a_1+b_1+a_2+b_2+\cdots+a_{999}+b_{999} \equiv 1+2+\cdots+1998 \equiv 1 \pmod 2,$$ as desired. $\blacksquare$

Overkill Solution:

Let there be $x$ six-pairs $(a_i, b_i)$ such that $|a_i - b_i|=6$. Then, there are $999-x$ one-pairs such that $|a_i - b_i| = 1$. The given expression evaluates to$$6x + (999-x) = 5x + 999$$For this to be $9 \pmod{10}$, it suffices to show that $x$ is even.Note that along with any six-pair $(n, n+6)$, in order to make successful pairings, we must have either exactly one of the six-pairs$$(n+1, n+7), (n+3, n+9), (n+5, n+11),$$or one of the following sets of three six-pairs$$\{(n+1, n+7), (n+2, n+8), (n+3, n+9)\}$$$$\{(n+1, n+7), (n+2, n+8), (n+5, n+11)\}$$$$\{(n+1, n+7), (n+4, n+10), (n+5, n+11)\}$$Each option generates an even number of six-pairs, so $x$ is even, as desired $\blacksquare$