Suppose that the set {1, 2,...1998} has been partitioned into disjoint pairs {a, b} (1sis999) so that for all i a-b equals 1 or 6. Then the sum a-b,+a, - b,+. +la.-bends in which digit?
Answers
Explanation:
C be the number of Consecutive pairs in the partition, and S be the number of pairs that differ by Six. We have C+S=999 and the sum of the differences is thus
C+6S=999+5S
Now each pair that differs by 6 consists of either two odd numbers or two even numbers. It's easy to see that the first such pair must consist of two odd numbers and the last such pair must consist of two even numbers -- e.g., you can't have {2,8} without having {1,7}. What's a little harder to see is that the pairs that differ by 6 must alternate between both odd and both even (when ordered, say according to the smaller number in each pair), but this can be shown by induction. It follows that S must be an even number. Every even value of S is possible between 0 and 996: Start with the "dense" set of pairs that differ by 6 that pairs the numbers 1 through 6 with 7 through 12, 13 through 18 with 19 through 24, etc., and then two at time change {1,7} and {2,8} to {1,2} and {7,8}, then {3,9} and {4,10} to {3,4} and {9,10}, etc. It follows that every number ending in a 9, from 999 to 5979, is a possible sum.
Remark: If all one wants to show is that the sum, whatever it is, ends in a 9 (which is what the original AoPS problem asks for), it's enough to note that 999+5S≡4 mod 5 and that the sum and difference of any two numbers have the same parity, so the parity of the sum of the differences is
1+2+⋯+1998=1998⋅19992=999⋅1999≡1mod2
and therefore (combining 4 mod 5 and 1 mod 2) the sum of the differences is ≡9 mod 10. (The AoPS solution gives a different argument for the 4 mod 5 part of the proof; I might have thought of the parity part myself, but I saw it there first.)