1
$\begingroup$

This problem is from Bay Area Math Olympiad 2016: 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 does not 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.

The vertices determine $\binom{n}{2}$ lines and there is a one to one correspondence between the number of words and the number of regions outside the convex hull formed by the vertices. The final answer is tantalizingly simple: $2\binom{n}{2} + 2\binom{n}{4}$. While the official solution is available, is there a combinatorial argument to get the answer in a direct way?

$\endgroup$
  • $\begingroup$ For those that want to look at the official solution, it can be found at this link (problem 5, the last problem). $\endgroup$ – Misha Lavrov Sep 10 '18 at 20:38
2
$\begingroup$

$2\binom n4$ counts the number of bounded regions outside the convex hull (which I'll call $H$). $2\binom n2$ counts the number of unbounded regions.

To count bounded regions: for each bounded region $\mathcal R$, let $f(\mathcal R)$ be the point of $\mathcal R$ furthest from $H$. Because the distance to $H$ is a convex function, $f(\mathcal R)$ must be a vertex of $\mathcal R$; because $\mathcal R$ contains points at distance $>0$ from $H$, this vertex is not one of the ones that lie on $H$. So $f(\mathcal R)$ is the intersection of two lines $AB \cap CD$, where $A,B,C,D$ are distinct vertices of $H$.

There are $\binom n4$ ways to choose $A,B,C,D$; each gives three intersection points $AB \cap CD$, $AC \cap BD$, and $AD \cap BC$, but one of these is inside $H$. So there are $2\binom n4$ values of $f(\mathcal R)$. Each one is achieved exactly once: given an intersection $AB \cap CD$, three of the regions have a point further from $H$ by moving along $AB$ or along $CD$.

To count unbounded regions: If we zoom out really far, all $\binom n2$ lines approximately intersect at a single point, and zooming out does not change the unbounded regions. It is easy to see that $N$ lines meeting at a point create $2N$ unbounded regions.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Counting unbounded regions using the zoom out is indeed a beautiful idea. Brilliant! $\endgroup$ – Muralidharan Sep 10 '18 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.