Taiwan IMO Selection Camp, 2021

Let us number the concentric circles in order as $1, 2, \dots, 2021$, and number the rays in order as $0, 1, \dots, N-1$, and let $A_i \in \{0, 1, \dots, N-1\} := \mathcal{N}$ be the set of ray indices for which there is a red point on the $i$-th concentric circle. The coincidence condition in the problem statement is equivalent to: for all $(x_1, \dots, x_{2021}) \in \mathcal{N}^{2021}$, there exists $(y_1, \dots, y_{2021}) \in A_1 \times \dots \times A_{2021}$ such that
$$x_1 - y_1 \equiv \dots \equiv x_{2021} - y_{2021} \quad \mod N. \quad (1)$$

The number of red points that the problem asks us to compute is then equal to $\sum_{i=1}^{2021} |A_i|$. For convenience of explanation, we say below that $(x_1, \dots, x_{2021})$ and $(y_1, \dots, y_{2021})$ satisfying (1) are congruent.

First we prove the lower bound. Note that any $(y_1, \dots, y_{2021}) \in A_1 \times \dots \times A_{2021}$ can be congruent to at most $N$ elements $(x_1, \dots, x_{2021}) \in \mathcal{N}^{2021}$, and since $|\mathcal{N}^{2021}| = N^{2021}$, we must have $|A_1 \times \dots \times A_{2021}| = \prod_{i=1}^{2021} |A_i|$ at least $N^{2021}/N = N^{2020}$, and therefore
$$\sum_{i=1}^{2021} |A_i| \ge 2021 \left( \prod_{i=1}^{2021} |A_i| \right)^{1/2021} \ge 2021 N^{2020/2021} = 2021 n^{2020}.$$

Next we prove that this lower bound is attainable; to this end, we construct $A_1, \dots, A_{2021}$ satisfying the required condition, each of size $n^{2020}$. Define $S_i = \{0, n^{i-1}, 2n^{i-1}, \dots, (n-1)n^{i-1}\}$, and let $A_i = \{0, 1, \dots, N-1\} \setminus S_i$. The following lemma proves that this collection of $A_i$ indeed satisfies the requirement of the problem (just substitute $s = 2021$).

Lemma: For all $s \le 2021$, let $B_{s,i} = \{0\} \cup S_1 \cup \dots \cup S_s$, and
$$A_{s,i} = \begin{cases} B_{s,i} & 1 \le i \le 2021 - s, \\ B_{s,i} - S_{i+s-2021} & 2022 - s \le i \le 2021. \end{cases}$$
Then for all $(x_1, \dots, x_{2021}) \in \{0, \dots, n^s - 1\}^{2021}$, there exists $(a_1, \dots, a_{2021}) \in A_{s,1} \times A_{s,2} \times \dots \times A_{s,2021}$ satisfying $a_1 - x_1 \equiv a_2 - x_2 \equiv \dots \equiv a_{2021} - x_{2021} \mod n^s$.

Proof: When $s = 0$, this is obvious. Assume the statement holds for $s-1$. Now consider any $(x_1, \cdots, x_{2021}) \in \{0, \cdots, n^s - 1\}^{2021}$. Since translation does not affect the congruence relation, without loss of generality assume $x_{2022-s} = 0$.

By the division principle, take $x_i = q_i n + r_i$, where $r_i \in S_1$. Note that $(q_1, \cdots, q_{2021}) \in \{0, \cdots, n^{s-1}-1\}^{2021}$, so by the induction hypothesis, there exists $(a'_1, \cdots, a'_{2021}) \in A_{s-1,1} \times \cdots \times A_{s-1,2021}$ such that $a'_1 - q_1 \equiv \cdots \equiv a'_{2021} - q_{2021} \bmod n^{s-1}$. By construction, for all $i \neq 2022-s$, we have $A_{s,i} = S_1 + n A_{s-1,i}$, so $na'_i + r_i \in A_{s,i}$; and for $i = 2022-s$, since $x_{2022-s} = 0$ implies $r_{2022-s} = 0$, and the construction guarantees $A_{s,2022-s} = n A_{s-1,2022-s}$, we have $na'_{2022-s} + r_{2022-s} \in A_{s,2022-s}$.

Finally note that
$$(na'_{i} + r_{i} - x_{i}) - (na'_{2022-s} + r_{2022-s} - x_{2022-s}) \equiv n(a'_{i} - a'_{2022-s}) + r_{i} - r_{2022-s} - (x_{i} - x_{2022-s}) \equiv n(q_{i} - q_{2022-s}) + r_{i} - r_{2022-s} - (q_{i} n + r_{i} - q_{2022-s} n - r_{2022-s}) \equiv 0 \mod n^{s},$$
we know there exists $(a_1, \cdots, a_{2021}) \in A_{s,1} \times \cdots \times A_{s,2021}$ satisfying $a_1 - x_1 \equiv a_2 - x_2 \equiv \cdots \equiv a_{2021} - x_{2021} \mod n^s$. This completes the proof.