## Task 4 - 130924

Imagine a circle divided into 1000 equal arcs, and each of the 1000 points is labeled with the natural numbers 1 to 1000.

![](https://cdn.mathpix.com/cropped/2024_06_06_b85a894aa8dbf722a7b3g-0962.jpg?height=182&width=1219&top_left_y=1054&top_left_x=424)

Now, starting with the number 1, and every 15th number thereafter, i.e., 1, 16, 31, 46, ..., are to be crossed out. In this process, even the already crossed-out numbers are to be counted when the sequence wraps around. This crossing out is to continue until only numbers that have already been crossed out would be crossed out again.

Determine the number of all numbers that are not crossed out by this procedure!
For a number $1 \leq n \leq 1000$ to be struck out, there must be non-negative integers $u$ and $q$ such that $n + 1000 \cdot u = 1 + 15 \cdot q$. Here, $u$ represents the number of complete laps around the circle, and $1 + 15 \cdot q$ represents every 15th number starting from 1, if counting continues indefinitely.

If we consider the remainder of both sides of this equation when divided by 5, it must be 1, since $15 q$ is divisible by 5. Since $1000 u$ is also divisible by 5, $n$ must leave a remainder of 1 when divided by 5. Therefore, there exists an integer $k$ with $0 \leq k < 200$ such that $n = 5 k + 1$. Substituting this into the equation, we find that the number $5 k + 1$ is struck out if and only if there are non-negative integers $q$ and $u$ such that $5 k + 1 + 1000 u = 1 + 15 q$, or equivalently, after subtracting 1 and dividing by 5, $k + 200 u = 3 q$.

These non-negative integers $q$ and $u$ exist for every non-negative $k$: If $k$ is divisible by 3, choose $u = 0$ and $q = \frac{k}{3}$. If $k$ leaves a remainder of 1 when divided by 3, then $k + 200$ is divisible by 3, and one can choose $u = 1$ and $q = \frac{k + 200}{3}$. Finally, if $k$ leaves a remainder of 2 when divided by 3, then $k + 400$ is divisible by 3, and one can choose $u = 2$ and $q = \frac{k + 2 \cdot 200}{3}$.

Together, this means that exactly the numbers $1 \leq n \leq 1000$ that can be expressed as $n = 5 k + 1$ with a non-negative integer $k$ such that $0 \leq k < 200$ are struck out. There are exactly 200 such numbers, so out of the 1000 numbers, exactly 800 are not struck out.