Combinatorics – General Formula for Combinatorics Question in Bay Area Mathematics Olympiad 2016

Question

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.

Answer 1

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.