Let $n$ be a positive integer and $N=n^{2021}$. There are $2021$ concentric circles centered at $O$, and $N$ equally-spaced rays are emitted from point $O$. Among the $2021N$ intersections of the circles and the rays, some are painted red while the others remain unpainted. It is known that, no matter how one intersection point from each circle is chosen, there is an angle $\theta$ such that after a rotation of $\theta$ with respect to $O$, all chosen points are moved to red points. Prove that the minimum number of red points is $2021n^{2020}$. Proposed by usjl.
Problem
Source: 2021 Taiwan TST Round 1 Mock Day 2 P6
Tags: combinatorics, construction, Taiwan
Tintarn
20.03.2021 14:00
Nice problem!
Replace $2021$ by $k$. Suppose there are $m_1,m_2,m_3,\dots,m_k$ red points on each circle.
We have $N^k$ ways to choose one point on each circle. To each such choice we need to associate one of $N$ possible angles $\theta$ and one of the $m_1m_2\dots m_k$ choices of one red point on each circle. Hence $Nm_1m_2\dots m_k \ge N^k$ and hence $m_1m_2\dots m_k \ge N^{k-1}$ whence the number of red points is
\[m_1+m_2+\dots+m_k \ge kN^{1-\frac{1}{k}}\]by AM-GM. But for $N=n^k$ this is exactly the bound $kn^{k-1}$ that we are required to prove.
Finally, we need to give a construction to show that we can do with this number of red points.
Here we identify the $n^k$ points on each circle with the set $\{0,1,2,\dots,n^k-1\}$. We then choose the $n^{k-1}$ red points on each circle as follows:
For each $0 \le j \le k-1$, choose on circle $j$ the points $a_0+a_1n+\dots+\dots+a_{k-2}n^{k-2}$ with $0 \le a_i \le n-1$ and $a_j=0$.
Clearly we have chosen $n^{k-1}$ points on each circle. By our counting argument from above, it suffices to prove that no two collections of one red point from each circle can be rotated to each other.
From the circle with $j=0$ we can see that such a rotation has to be a multiple of $n$.
Then from the circle $j=1$ the rotation has to be a multiple of $n^2$.
Iterating this, we see that the rotation has to be the identity and we are done.
Acclab
02.03.2024 17:07
Let $k=2021$. Denote the number of red intersections ("points") on the $i$-ith circle $a_i$, then $$ \text{ \# of different ways to choose one point on each circle, equivalent up to rotation } = \frac{(n^k)^k}{n^k} = n^{k(k-1)},$$while $$ \text{ \# of different ways to choose one red point on each circle} = \prod{a_i}. $$Denote these two quantity by $s_1, s_2$. To let the statement hold, $s_2 \geq s_1$, but FTSoC if $\sum{a_i} < kn^{k-1}$, $$ s_2 = \prod{a_i} \leq (\frac{\sum{a_i}}{k})^k < (n^{k-1})^k = n^{k(k-1)} = s_1, $$a contradiction. We're done bounding, now we construct. Induct on $k$, for $k=1$ we just choose a point. Then for each $k$, we copy the construction of $k-1$; $n$ times for the inner circles. Then add the external $k$-th circle and paint all intersections with rays crossing a fixed construction by red. In this construction $s_1 = s_2 = kn^{k-1}$, so to see this includes all ways of choosing one point on each circle up to rotation, it suffices to show there are no two repeated setups(that is, there are no two ways of choosing one red point each circle such that they are equivalent up to rotation). We focus on two red points on the $k$-th circle: if they give rise to two setups equivalent up to rotation, then, in particular, the previous construction of $k-1$ has two equivalent setups up to rotation either, a contradiction. This shows the construction works.