# Combinatorics Question, Bay Area Mathematics Olympiad 2016, Finding a General Formula

The corners of a fixed convex (but not necessarily regular) n-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).

Determine, as a formula in terms of $$n$$, the maximum number of distinct $$n$$-letter words which may be read in this manner from a single $$n$$-gon. Do not count words in which some letter is missing because it is directly behind another letter from the viewer's position.

//My attempt//

• First I notice that there is a bijection between number of words and {sides and diagonals}:
• On extending each edge to both its sides, outside the polygon, the plane is divided into $$2n$$ parts. Standing in each of these sides, gives a different word.
• Further, extending each diagonal to both its sides adds more division of the plane, equal to twice the number of diagonals of $$n$$-gon, which is $$2\left(\binom{n}{2}-n\right)$$
• Adding these two gives $$2\binom{n}{2}$$
• I don't know, but this seems to work for triangles, quadrilaterals and maybe even pentagons.

On the official site's solution page, two solutions are given: One is ugly and well, seems complicated. The other one is given to be: $$2\binom{n}{2}+2\binom{n}{4}$$ which my solution is closer to. Any help to get it would be appreciated. And, please point out if I've done something wrong.

• It looks like you need to assume that no sides are parallel. A quadrilateral with 2 pairs of parallel lines cuts the exterior plane into 12 segments, with one pair you have 13 and no pair gives you 14 (as in the solution) – WW1 Jun 27 '19 at 18:53
• Thanks, I'll try that out. But, is there still a chance that someone might answer my question? I'm sorry if that's a foolish question, but I don't really know anything a out StackExchange... – Sen47 Jun 28 '19 at 0:15
• To talk of a "bijection between number of words and {sides and diagonals}" is sloppy: if that were truly the case, the answer would be $\binom{n}{2}$, but you've already found that this isn't correct. – Peter Taylor Jun 28 '19 at 7:45

As indicated by @WW1 we have to consider a general convex $$n$$-gon meaning that no two lines connecting corners of the $$n$$-gon are parallel. Otherwise the formula \begin{align*} 2\binom{n}{2}+2\binom{n}{4} \end{align*} is not generally valid.

We can derive the term $$2\binom{n}{2}$$ as follows:

• We fix a position $$P$$ outside the convex $$n$$-gon and look at the corners of the $$n$$-gon from left to right.

We can assume according to the problem that $$P$$ is not located at a line of sight of two corners . This implies that whenever we cross a line connecting two corners we change the order of the corners when looking from left to right.

Since there are $$\binom{n}{2}$$ different lines connecting two out of $$n$$ corners we can read \begin{align*} \color{blue}{2\binom{n}{2}} \end{align*} different words this way.

The graphic below gives $$2\binom{4}{2}=12$$ blue marked different words in case of a $$4$$-gon. Note that no two lines connecting two corners are in parallel.

The additional term $$2\binom{n}{4}$$:

• Whenever we choose $$4$$ corners of the $$n$$-gon, we can visit them counter-clockwise and connect each two consecutive corners with a line.

Since by assumption no two lines are parallel, two pairs of lines will intersect defining this way two regions which have not been considered in the first case.

There are $$\binom{n}{4}$$ different ways to select $$4$$ corners and each selection gives rise to two new regions. We obtain \begin{align*} \color{blue}{2\binom{n}{4}} \end{align*} additional words this way.

The graphic below shows a (general) $$4$$-gon and the $$2\binom{4}{2}+2\binom{4}{4}=12+2=14$$ different words. The two additional regions giving $$2\binom{4}{4}=2$$ words are marked in grey.

Note: From the graphic it's obvious that parallel lines reduce the number of regions we can obtain reducing also the number of different words.

• Thank you so much, sir. Highly obliged for your time. – Sen47 Jun 30 '19 at 14:18
• @Sen47: You're welcome. Thanks for the credit. – Markus Scheuer Jun 30 '19 at 14:20