Maths Olympiad Prep

Library / /13 of 37

Combinatorics Difficulty 6.5 National olympiad Find the answer

Given two integers m,n m,n satisfying 4<m<n. 4 < m < n. Let A1A2A2n\plus1 A_{1}A_{2}\cdots A_{2n \plus{} 1} be a regular 2n\plus1 2n\plus{}1 polygon. Denote by P P the set of its vertices. Find the number of convex m m polygon whose vertices belongs to P P and exactly has two acute angles.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Given two integers m m and n n satisfying 4<m<n 4 < m < n , let A1A2A2n+1 A_1A_2\cdots A_{2n+1} be a regular 2n+1 2n+1 polygon. Denote by P P the set of its vertices. We aim to find the number of convex m m -gons whose vertices belong to P P and have exactly two acute angles.

Notice that if a regular m m -gon has exactly two acute angles, they must be at consecutive vertices. Otherwise, there would be two disjoint pairs of sides that take up more than half of the circle each. 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 m -gons by a factor of 2n+1 2n + 1 , 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 k points, and the other arc contains 2n1k 2n - 1 - k points. For each k k , the vertices of the m m -gon on the smaller arc may be arranged in (2n1km4) \binom{2n - 1 - k}{m - 4} ways, and the two vertices on the larger arc may be arranged in (kn)2 (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 k is thus (kn)2×(2n1km4) (k - n)^2 \times \binom{2n - 1 - k}{m - 4} . Summation over all k k and change of variable gives that the total number of polygons (divided by a factor of 2n+1 2n + 1 ) is:
k0k2(nk1m4). \sum_{k \geq 0} k^2 \binom{n - k - 1}{m - 4}.

This can be proven to be exactly (nm1)+(n+1m1) \binom{n}{m - 1} + \binom{n + 1}{m - 1} by double induction on n>m n > m and m>4 m > 4 . The base cases n=m+1 n = m + 1 and m=5 m = 5 are readily calculated. The induction step is:
k0k2(nk1m4)=k0k2((n1)k1m4)+k0k2((n1)k1(m1)4). \sum_{k \geq 0} k^2 \binom{n - k - 1}{m - 4} = \sum_{k \geq 0} k^2 \binom{(n - 1) - k - 1}{m - 4} + \sum_{k \geq 0} k^2 \binom{(n - 1) - k - 1}{(m - 1) - 4}.
=(n1m1)+(nm1)+(n1m2)+(nm2)=(nm1)+(n+1m1). = \binom{n - 1}{m - 1} + \binom{n}{m - 1} + \binom{n - 1}{m - 2} + \binom{n}{m - 2} = \binom{n}{m - 1} + \binom{n + 1}{m - 1}.

So the total number of m m -gons is:
(2n+1)×[(nm1)+(n+1m1)]. (2n + 1) \times \left[ \binom{n}{m - 1} + \binom{n + 1}{m - 1} \right].

The answer is: \boxed{(2n + 1) \left[ \binom{n}{m - 1} + \binom{n + 1}{m - 1} \right]}.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.