## Task 4 - 341234

Determine the smallest natural number $n$ with $n \geq 2$ and the following property ( $\left.{ }^{*}\right)$ :

$(*)$ In every set of $n$ natural numbers, there are (at least) two numbers whose sum or whose difference is divisible by 7.
For $n=4$ (and thus also for $n=2,3$), one can still easily find such an $n$-element subset $M$ of $\mathbb{N}$, for example, $M=\{0,1,2,3\}$. If $x, y \in M$ and $x \neq y$, then for them $0 < |x - y| < 4$, and thus $|x - y|$ is not divisible by 7. 

To show that this is no longer possible for $n > 4$, consider the partition $P = \{\{0\},\{1,6\},\{2,5\},\{3,4\}\}$ of $\{0,1, \ldots, 6\}$ and any subset $M$ of $\mathbb{N}$ with at least 5 elements.

If we now associate with each element in $M$ that element in $\{0,1, \ldots, 6\}$ to which it is congruent modulo 7, then by the pigeonhole principle, because $|M| \geq 5$, there must be a 2-element class of $P$ whose two elements are all "hit" by this assignment. The sum of the corresponding elements of $M$ is then, by the construction of $P$, divisible by 7, q.e.d.