Maths Olympiad Prep

Library / /2 of 2

Geometry Difficulty 7.6 National Olympiad, round 2 Prove it United States

Problem:
The corners of a fixed convex (but not necessarily regular) nn-gon are labeled with distinct letters. If an observer stands at a point in the plane of the polygon, but outside the polygon, they see the letters in some order from left to right, and they spell a "word" (that is, a string of letters; it doesn't need to be a word in any language). For example, in the diagram below (where n=4n=4), an observer at point XX would read "BAMO," while an observer at point YY would read "MOAB."
Figure 1
Determine, as a formula in terms of nn, the maximum number of distinct nn-letter words which may be read in this manner from a single nn-gon. Do not count words in which some letter is missing because it is directly behind another letter from the viewer's position.

Solution

Solution:
Let us call our original nn points V1,V2,,VnV_{1}, V_{2}, \ldots, V_{n}.
If A,BA, B are two points, then viewers on one side of line AB\overleftrightarrow{A B} see AA to the left of BB, and viewers on the other side see BB to the left of AA. Therefore, if we draw the (n2)\binom{n}{2} lines determined by pairs {Vi,Vj}\{V_{i}, V_{j}\} (1i<jn1 \leq i < j \leq n), then different "views" of V1,V2,,VnV_{1}, V_{2}, \ldots, V_{n} (from outside their convex hull) are in one-to-one correspondence with the regions formed outside the convex hull by these (n2)\binom{n}{2} lines. These regions are what we will now count. Our strategy is to count all regions, then subtract those regions that are inside the convex hull of V1,V2,,VnV_{1}, V_{2}, \ldots, V_{n}.

We begin by stating and proving a general lemma:

Lemma. Let KK be a convex region of the plane. Let rr lines pass through the interior of KK, making a total of mm intersections in the interior of KK. Suppose further that no three of the lines meet at one of these intersections. Then KK is divided by the lines into 1+r+m1 + r + m regions.

Proof of Lemma. Number the lines 1,2,,r\ell_{1}, \ell_{2}, \ldots, \ell_{r}. We imagine that we draw the lines one at a time, in this order. Suppose mim_{i} is the number of points in the interior of KK where i\ell_{i} intersects 1,2,,i1\ell_{1}, \ell_{2}, \ldots, \ell_{i-1}. Then at the stage when we draw i\ell_{i}, it passes through mi+1m_{i} + 1 existing regions, dividing each of them into two regions and thereby increasing the number of regions by mi+1m_{i} + 1. Since there is initially one region (KK itself), the final number of regions after all rr lines are drawn is
1+(m1+1)+(m2+1)+(m3+1)++(mr+1). 1 + (m_{1} + 1) + (m_{2} + 1) + (m_{3} + 1) + \cdots + (m_{r} + 1).
But observe that m1+m2++mr=mm_{1} + m_{2} + \cdots + m_{r} = m, since each intersection point in the interior of KK is counted exactly once on each side of the equation. Thus the final number of regions is 1+r+m1 + r + m.

By the lemma, if (n2)\binom{n}{2} lines are in general position (no two parallel, no three concurrent), then they divide the plane into 1+(n2)+(n2)1 + \binom{n}{2} + \binom{n}{2} regions.

However, our (n2)\binom{n}{2} lines aren't in general position; n1n-1 lines meet at each of our original points ViV_{i}. Each ViV_{i} is surrounded by 2(n1)2(n-1) regions, but if we nudged each line by a tiny amount so as to separate all their pairwise intersections, then these 2(n1)2(n-1) regions would become 1+n+(n12)1 + n + \binom{n-1}{2} regions (by the lemma). Accounting for this, the number of regions formed by our (n2)\binom{n}{2} lines is
1+(n2)+(n2)+n[2(n1)(1+n+(n12))]. 1 + \binom{n}{2} + \binom{n}{2} + n\left[2(n-1) - (1 + n + \binom{n-1}{2})\right].

Finally, we subtract the regions inside the convex hull of V1,V2,,VnV_{1}, V_{2}, \ldots, V_{n}. The number of lines passing through the convex hull (i.e., diagonals, not sides) is (n2)n\binom{n}{2} - n. Every set of four points {Vi,Vj,Vk,Vm}\{V_{i}, V_{j}, V_{k}, V_{m}\} (1i<j<k<mn1 \leq i < j < k < m \leq n) determines a unique intersection inside the convex hull, so there are (n4)\binom{n}{4} such intersections. Thus by the lemma, the convex hull is cut into 1+(n2)n+(n4)1 + \binom{n}{2} - n + \binom{n}{4} regions. Subtracting this from our total count of regions in the plane, we conclude that the number of regions outside the convex hull (which is our final answer) is
1+(n2)+(n2)+n[2(n1)(1+n+(n12))][1+(n2)n+(n4)] 1 + \binom{n}{2} + \binom{n}{2} + n\left[2(n-1) - (1 + n + \binom{n-1}{2})\right] - \left[1 + \binom{n}{2} - n + \binom{n}{4}\right]
This may be simplified to
112n(n1)(n25n+18). \frac{1}{12} n(n-1)\left(n^{2} - 5n + 18\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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.