Given two integers $ m,n$ satisfying $ 4 < m < n.$ Let $ A_{1}A_{2}\cdots A_{2n + 1}$ be a regular $ 2n+1$ polygon. Denote by $ P$ the set of its vertices. Find the number of convex $ m$ polygon whose vertices belongs to $ P$ and exactly has two acute angles.
Problem
Source: Chinese National Olympiad 2009 P3
Tags: induction, combinatorics proposed, combinatorics
JBL
11.01.2009 02:12
Related questions are http://www.artofproblemsolving.com/Forum/viewtopic.php?t=89764 and a continuous version http://www.artofproblemsolving.com/Forum/viewtopic.php?t=64437 (I searched for "acute convex.")
bodan
12.01.2009 15:15
Notice that if a regular $ m$ polygon has exactly two acute angles, they must be at consecutive vertices: for otherwise there would be two disjoint pairs of sides that take up more than half of the circle each. Now assume that the last vertex, clockwise, of these four vertices that make up two acute angles is f\mbox ixed; this reduces the total number of regular $ m$ polygons $ 2n + 1$ times and we will later multiply by this factor. Suppose the larger arc that the first and the last of these four vertices make contains $ k$ points, and the other arc contains $ 2n - 1 - k$ points. For each $ k$, the vertices of the $ m$ polygon on the smaller arc may be arranged in $ {2n - 1 - k \choose m - 4}$ ways, and the two vertices on the larger arc may be arranged in $ (k - n - 1)^2$ ways (so that the two angles cut off more than half of the circle). The total number of polygons given by $ k$ is thus $ (k - n - 1) ^ 2 \times {2n - 1 - k \choose m - 4}$. Summation over all $ k$ and change of variable gives that the total number of polygons (divided by a factor of $ 2n + 1$) is \[ \sum_{k \geq 0} k^2 {n - k - 2 \choose m - 4}\] This can be proven to be exactly $ {n \choose m - 1} + {n - 1 \choose m - 1}$ by double induction on $ n > m$ and $ m > 4$. The base cases $ n = m + 1$ and $ m = 5$ are readily calculated. The induction step is \[ \sum_{k \geq 0} k^2 {n - k - 2 \choose m - 4} = \sum_{k \geq 0} k^2 {(n - 1) - k - 2 \choose m - 4} + \sum_{k \geq 0} k^2 {(n - 1) - k - 2 \choose (m - 1) - 4} \] \[ \null \quad = {n - 1 \choose m - 1} + {n - 2 \choose m - 1} + {n - 1 \choose m - 2} + {n - 2 \choose m - 2} \] \[ \null \quad = {n \choose m - 1} + {n - 1 \choose m - 1} \] So the total number of $ m$ polygons is \[ (2n + 1) \times \left [{n \choose m - 1} + {n - 1 \choose m - 1}\right]\]
artofproblemsolving
25.01.2009 22:51
I think above answer is not clearly correct. Because when n=6, m=5 the answer is 650 but above answer is 260 can it correct??
bodan
26.01.2009 17:36
Yes, there is a small mistake here: bodan wrote: . . . and the two vertices on the larger arc may be arranged in $ (k - n - 1)^2$ ways (so that the two angles cut off more than half of the circle) . . . Instead of $ (k - n - 1)^2$ it should be $ (k - n)^2$. Then the sum is \[ \sum_{k \geq 0} k^2 {n - k - 1 \choose m - 4} = (2n+1) \left[{n \choose m - 1} + {n + 1 \choose m - 1}\right]\] Then for $ n=6$ and $ m=5$ we get $ 650$. Just for completeness, here is the correct version:
Notice that if a regular $ m$ polygon has exactly two acute angles, they must be at consecutive vertices: for otherwise there would be two disjoint pairs of sides that take up more than half of the circle each. Now assume that the last vertex, clockwise, of these four vertices that make up two acute angles is fixed; this reduces the total number of regular $ m$ polygons $ 2n + 1$ times and we will later multiply by this factor. Suppose the larger arc that the first and the last of these four vertices make contains $ k$ points, and the other arc contains $ 2n - 1 - k$ points. For each $ k$, the vertices of the $ m$ polygon on the smaller arc may be arranged in $ {2n - 1 - k \choose m - 4}$ ways, and the two vertices on the larger arc may be arranged in $ (k - n)^2$ ways (so that the two angles cut off more than half of the circle).
The total number of polygons given by $ k$ is thus $ (k - n) ^ 2 \times {2n - 1 - k \choose m - 4}$. Summation over all $ k$ and change of variable gives that the total number of polygons (divided by a factor of $ 2n + 1$) is
\[ \sum_{k \geq 0} k^2 {n - k - 1 \choose m - 4}
\]
This can be proven to be exactly $ {n \choose m - 1} + {n + 1 \choose m - 1}$ by double induction on $ n > m$ and $ m > 4$. The base cases $ n = m + 1$ and $ m = 5$ are readily calculated. The induction step is
\[ \sum_{k \geq 0} k^2 {n - k - 1 \choose m - 4} = \sum_{k \geq 0} k^2 {(n - 1) - k - 1 \choose m - 4} + \sum_{k \geq 0} k^2 {(n - 1) - k - 1 \choose (m - 1) - 4}
\]
\[ \null \quad = {n - 1 \choose m - 1} + {n \choose m - 1} + {n - 1 \choose m - 2} + {n \choose m - 2} = {n \choose m - 1} + {n + 1 \choose m - 1}
\]
So the total number of $ m$ polygons is
\[ (2n + 1) \times \left [{n \choose m - 1} + {n + 1 \choose m - 1}\right]
\]
artofproblemsolving
26.01.2009 18:51
that's correct thank you your solution is so simple and great!!