5

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). For example, in the diagram below (where $n=4$), an observer at point $X$ would read "$BAMO$," while an observer at point $Y$ would read "$MOAB$." Diagram to be added soon

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.

Attemp: I thought about creating the maximum number of regions outside n-gon by extending all the diagonals and sides of n-gon, but it's a bit difficult to get a closed form (I haven't tested it). You have to use V + (F + 1) = E + 2, and that only gets bad from there.

Andrés E. Caicedo
  • 79,201
Lambert macuse
  • 4,266

1 Answers1

3

Edit: The number of edges in my initial answer was too low. Corrected.

The Euler formula approach works and gives $2{n \choose 2} + 2{n \choose 4} $ areas for a convex $n$-gon $P$ in general position.

  • Vertices: Any four vertices of $P$ define two vertices outside $P$. Together with the $n$ vertices of $P$ and the point at infinity this gives $V=2{n \choose 4} + n +1$.
  • Edges: Any pair of vertices of $P$ define two edges outside of $P$. Any four vertices of $P$ add four more edges. Together with the $n$ edges of $P$ this gives $E=2{n \choose 2} + 4{n \choose 4} + n$.
  • From $V-E+F=2$ it follows that $F=1+ 2{n \choose 2} + 2{n \choose 4} $ including the interior of $P$. So $2{n \choose 2} + 2{n \choose 4} $ areas outside $P$.
WimC
  • 32,192
  • 2
  • 48
  • 88
  • How does any $4$ vertices of $P$ add four more edges? I thought all edges are accounted for by considering pairs of vertices in $P$? – Lambert macuse Jan 07 '20 at 11:21
  • Four vertices define two sets of lines that intersect outside of the polygon. (If the vertices are $a,b,c,d$ in cyclic order then the pairs are ${ab,cd}$ and ${bc,da}$.) So four vertices add two extra vertices as intersection points of these pairs. At each of these two intersections, two edges start there and extend outward, away from the polygon, possibly of infinite length. So two times two edges per four polygon vertices. – WimC Jan 07 '20 at 17:48