Maths Olympiad Prep

Library / /23 of 41

Geometry Difficulty 5.7 AIME, harder Prove it New Zealand

Problem:
Let VV be the set of vertices of a regular 21-gon. Given a non-empty subset UU of VV, let m(U)m(U) be the number of distinct lengths that occur between two distinct vertices in UU. What is the maximum value of m(U)U\frac{m(U)}{|U|} as UU varies over all non-empty subsets of VV?

Solution

Solution:
To simplify notation, we will let mm be m(U)m(U) and let nn be U|U|. First note that there are 10 different diagonal-lengths in a regular 21-gon. Now consider the following set of 5 vertices.

Figure 1

Note that each of the 10 different diagonal-lengths appear (exactly once each). So for this set of 5 vertices we have mn=105=2\frac{m}{n} = \frac{10}{5} = 2. We will now show that this is the maximum possible value for mn\frac{m}{n}.

If UU is an arbitrary non-empty set of vertices, then there are two cases:

- Case 1: n<5n < 5. The total number of pairs of vertices in UU is given by 12n(n1)\frac{1}{2} n(n - 1). Since n1<4n - 1 < 4 this gives us the bound:
mn(n1)2<n×42=2n.m \leq \frac{n(n - 1)}{2} < \frac{n \times 4}{2} = 2n.
Thus mn<2\frac{m}{n} < 2 in this case.

- Case 2: n5n \geq 5. The total number of distances in UU is at most 10 because there are only 10 different diagonal lengths in the 21-gon. Therefore
mn10n105=2\frac{m}{n} \leq \frac{10}{n} \leq \frac{10}{5} = 2
as required.

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.