1998 USAMO P1

Problem:

Suppose that the set $\{1,2,\cdots ,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$.

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(\mathrm{mod}5)$, it is enough to show that it is also $1(\mathrm{mod}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(\mathrm{mod}2),$$ as desired. $◼$

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(\mathrm{mod}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 $◼$