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
20.03.2021 14:00
Nice problem!
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.