Problem 3. Consider the sets $M=\{0,1,2, \ldots, 2019\}$ and

$$
A=\left\{x \in M \left\lvert\, \frac{x^{3}-x}{24} \in \mathbb{N}\right.\right\}
$$

a) How many elements does the set $A$ have?

b) Determine the smallest natural number $n, n \geq 2$, which has the property that any subset with $n$ elements of the set $A$ contains two distinct elements whose difference is divisible by 40.
## Solution and Grading Criteria

a) The number $x^{3}-x=x\left(x^{2}-1\right)=(x-1) x(x+1)$ is a product of three consecutive natural numbers, so $3 \mid x^{3}-x$.

If $x \in A$ is even, since $x-1$ and $x+1$ are odd, $x$ must be a multiple of 8.

If $x \in A$ is odd, the numbers $x-1$ and $x+1$ are even, and one of them is divisible by 4, so $x^{3}-x$ is divisible by 8.

Therefore, $x \in A$ if and only if $x \in M$ is odd or divisible by 8. .......1p In $M$ there are 1010 odd numbers and 253 multiples of 8, so $A$ has a total of 1263 elements.

$2 \mathrm{p}$

b) We will show that the smallest value of $n$ is 26.

Since any number in $A$ gives one of the remainders $0,1,3,5$ and 7 when divided by 8, when divided by 40 it can give any of the following remainders: $0,1,3,5,7,8,9,11,13$, $15,16,17,19,21,23,24,25,27,29,31,32,33,35,37$ or 39 (odd or multiple of 8), i.e., any of 25 possible remainders. $2 p$

For $n \leq 25$ we find in $A$ numbers that give different remainders when divided by 40. ...1p If $n=26$, by the pigeonhole principle, in any subset of $n$ elements of $A$ there exist two that give the same remainder when divided by 40, so their difference is divisible by 40.