Maths Olympiad Prep

Library / Team selection test for 47. IMO /2 of 9

Team selection test for 47. IMO

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Bulgaria

Problem:
Let m≥5m \geq 5 and nn be positive integers and MM be a regular (2n+1)(2n+1)-gon. Find the number of convex mm-gons with vertices among the vertices of MM and having at least one acute angle.

Solution

Solution:
It is easy to observe that there are at most two acute angles in every convex mm-gon. Moreover, if there are two acute angles then they are located at one and the same side.

Fix l=0,1,…,n−1l = 0, 1, \ldots, n-1 and let AA and BB be two vertices of MM such that there are ll vertices on the arc AB^\widehat{AB}. Consider the following expression
(lm−2)+(nm−2)−(n−l−1m−2)−(l+1)(n−l−1m−3) \binom{l}{m-2} + \binom{n}{m-2} - \binom{n-l-1}{m-2} - (l+1)\binom{n-l-1}{m-3}
We count in it all mm-gons having two acute angles to the side ABAB and all mm-gons having one acute angle to the right of ABAB.

It is easy to see that summation on l=0,1,…,n−1l = 0, 1, \ldots, n-1 and then multiplication by 2n+12n+1 counts every mm-gon exactly once.

Now using the identity ∑s=0k(st)=(k+1t+1)\sum_{s=0}^{k} \binom{s}{t} = \binom{k+1}{t+1} we obtain
∑l=0n−1[(lm−2)+(nm−2)−(n−l−1m−2)−(l+1)(n−l−1m−3)]= ∑l=0n−1(lm−2)+n(nm−2)−∑s=0n−1(sm−2)−(n−s)∑s=0n−1(sm−3)= n(nm−2)−n∑s=0n−1(sm−3)+(s+1)∑s=0n−1(sm−3)−∑s=0n−1(sm−3)= (m−2)∑s=0n−1(s+1m−2)−(nm−2)=(m−2)(n+1m−1)−(nm−2)= mn−2n−1m−1(nm−2). \begin{aligned} & \sum_{l=0}^{n-1} \left[ \binom{l}{m-2} + \binom{n}{m-2} - \binom{n-l-1}{m-2} - (l+1)\binom{n-l-1}{m-3} \right] \\ =\ & \sum_{l=0}^{n-1} \binom{l}{m-2} + n\binom{n}{m-2} - \sum_{s=0}^{n-1} \binom{s}{m-2} - (n-s) \sum_{s=0}^{n-1} \binom{s}{m-3} \\ =\ & n\binom{n}{m-2} - n \sum_{s=0}^{n-1} \binom{s}{m-3} + (s+1) \sum_{s=0}^{n-1} \binom{s}{m-3} - \sum_{s=0}^{n-1} \binom{s}{m-3} \\ =\ & (m-2) \sum_{s=0}^{n-1} \binom{s+1}{m-2} - \binom{n}{m-2} = (m-2)\binom{n+1}{m-1} - \binom{n}{m-2} \\ =\ & \frac{mn - 2n - 1}{m-1} \binom{n}{m-2} . \end{aligned}
Therefore the answer is (2n+1)(mn−2n−1)m−1(nm−2)\frac{(2n+1)(mn-2n-1)}{m-1} \binom{n}{m-2}.

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

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