Maths Olympiad Prep

Library / /181 of 299

Combinatorics Difficulty 6.7 National Olympiad Prove it Iran

Vertices of a regular nn-gon have been colored blue and red such that for each rotation of the nn-gon, the number of vertices that have different colors before and after the rotation is less than 32 percent of the number of vertices. Prove that either the number of blue vertices or the number of red vertices is less than 20 percent of the number of vertices, nn.

Solution

Obviously, there are exactly n1n-1 different nontrivial rotations of a regular nn-gon (rotations of 2πin\frac{2\pi i}{n} angles, for 1in11 \le i \le n-1). Denote the number of blue and red vertices of the polygon by bb and rr, respectively (a+b=n)(a+b=n), and the number of vertices that have different colors before and after the rotation of 2πjn\frac{2\pi j}{n} angle by tjt_j. According to the problem statement, tj<32100nt_j < \frac{32}{100}n for j=1,2,,n1j = 1, 2, \dots, n-1. On the other hand, during the n1n-1 rotations each blue vertex coincides with each red vertex exactly once and conversely, each red vertex coincides with each blue vertex exactly once. Therefore, from one hand the total number of pair of points with opposite colors after all of the nontrivial rotations is j=1n1tj\sum_{j=1}^{n-1} t_j, and 2rb=2r(nr)2rb = 2r(n-r) from another. Hence,
2r(nr)=j=1n1tj<(n1)×32100n<32100n2, 2r(n-r) = \sum_{j=1}^{n-1} t_j < (n-1) \times \frac{32}{100}n < \frac{32}{100}n^2,
or equivalently,
r2nr+16100n2>0(rn2)2>9100n2rn2>310n, r^2 - nr + \frac{16}{100}n^2 > 0 \Leftrightarrow \left(r - \frac{n}{2}\right)^2 > \frac{9}{100}n^2 \Leftrightarrow \left|r - \frac{n}{2}\right| > \frac{3}{10}n,
which completes the proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.