Challenge Math Challenge - December 2020

[Not anonymous]

Spoiler: Question 12

Answer: 5
Explanation: The modulo w.r.t. 7 of any natural number belongs to one of the 4 sets from $A=\{\{0\}, \{1, 6\}, \{2, 5\}, \{3, 4\}\}$, i.e. sets of the form $\{r, (7-r) \mod 7\}$ where $r$ belongs to the set of all possible remainders w.r.t. 7, i.e. {0, 1, 2, ..., 6}. Consider 2 distinct natural numbers $a, b$. It is easy to see that if $(a \mod 7)$ and $(b\mod 7)$ belong to 2 different sets in $A$, then neither their sum nor difference is divisible by 7. On the other hand, if they belong to the same set from within $A$, then 2 possibilities arise:

1. $(a \mod 7) = (b \mod 7)$, i.e. the remainders w.r.t. 7 of both $a$ and $b$ correspond the same element in the set. In this case, $(a - b) \equiv 0 \mod 7$, i.e. the difference is divisible by 7.
2. $(r_{a} \equiv (a \mod 7)) \neq (r_{b} \equiv (b \mod 7))$. Then, by definition of the sets, $r_{a} = (7 - r_{b}) \mod 7$. Therefore, $(r_{a} + r_{b}) = 7 \equiv 0 \mod 7 \Rightarrow (a+b) \equiv 0 \mod{7}$, i.e. the sum is divisible by 7.

Thus, for neither sum nor difference of $a, b$ to be divisible by 7, their modulo w.r.t. 7 must belong to 2 different sets from $A$. By pigeonhole principle, there can be at most 4 distinct natural numbers in a set such that the modulo w.r.t. 7 of no two of those belong to the same set from $A$. Thus, if we have a set of 5 (or more) natural numbers, at least two of those numbers will have either their sum or their difference divisible by 7.