Maths Olympiad Prep

Library / /2 of 11

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Bulgaria

Problem:
Let m5m \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,,n1l = 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
(lm2)+(nm2)(nl1m2)(l+1)(nl1m3) \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,,n1l = 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=0n1[(lm2)+(nm2)(nl1m2)(l+1)(nl1m3)]= l=0n1(lm2)+n(nm2)s=0n1(sm2)(ns)s=0n1(sm3)= n(nm2)ns=0n1(sm3)+(s+1)s=0n1(sm3)s=0n1(sm3)= (m2)s=0n1(s+1m2)(nm2)=(m2)(n+1m1)(nm2)= mn2n1m1(nm2). \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)(mn2n1)m1(nm2)\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,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.