Problem:
The corners of a fixed convex (but not necessarily regular) -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 ), an observer at point would read "BAMO," while an observer at point would read "MOAB."
Determine, as a formula in terms of , the maximum number of distinct -letter words which may be read in this manner from a single -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 points .
If are two points, then viewers on one side of line see to the left of , and viewers on the other side see to the left of . Therefore, if we draw the lines determined by pairs (), then different "views" of (from outside their convex hull) are in one-to-one correspondence with the regions formed outside the convex hull by these 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 .
We begin by stating and proving a general lemma:
Lemma. Let be a convex region of the plane. Let lines pass through the interior of , making a total of intersections in the interior of . Suppose further that no three of the lines meet at one of these intersections. Then is divided by the lines into regions.
Proof of Lemma. Number the lines . We imagine that we draw the lines one at a time, in this order. Suppose is the number of points in the interior of where intersects . Then at the stage when we draw , it passes through existing regions, dividing each of them into two regions and thereby increasing the number of regions by . Since there is initially one region ( itself), the final number of regions after all lines are drawn is
But observe that , since each intersection point in the interior of is counted exactly once on each side of the equation. Thus the final number of regions is .
By the lemma, if lines are in general position (no two parallel, no three concurrent), then they divide the plane into regions.
However, our lines aren't in general position; lines meet at each of our original points . Each is surrounded by regions, but if we nudged each line by a tiny amount so as to separate all their pairwise intersections, then these regions would become regions (by the lemma). Accounting for this, the number of regions formed by our lines is
Finally, we subtract the regions inside the convex hull of . The number of lines passing through the convex hull (i.e., diagonals, not sides) is . Every set of four points () determines a unique intersection inside the convex hull, so there are such intersections. Thus by the lemma, the convex hull is cut into 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
This may be simplified to