Prove that if six natural numbers are chosen at random, then the sum or difference of two of them is divisible by 9.

Question

Any input on how to approach this problem will be appreciated!

Answer 1

This is a very nice example of a proof by the pigeon hole principle: If you sort more than n objects into n pigeon holes, at least one pigeon hole will contain at least two objects.

Application to your problem: Let the six numbers be $a,b,c,d,e$ and $f$. If two of them are divisible by 9, the result follows immediately. So let's assume that $a$ may or may not be, but none of $b,c,d,e,f$ are divisible by 9 (this is needed at the very end). Note that $$ a + x \equiv a - y \mod 9 \,\,\,\,\Rightarrow x + y \equiv 0 \mod 9$$

$$a + x \equiv a + y \mod 9 \,\,\,\,\Rightarrow x - y \equiv 0 \mod 9$$

Now consider the set of up to ten numbers $\lbrace a \pm x \,|\,x \in \lbrace b,c,d,e,f\rbrace\rbrace\,$ modulo 9 to conclude.