8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – WW1 Jun 27 '19 at 18:53
  • $\begingroup$ 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... $\endgroup$ – Sen47 Jun 28 '19 at 0:15
  • $\begingroup$ 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. $\endgroup$ – Peter Taylor Jun 28 '19 at 7:45
2
$\begingroup$

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.

enter image description here

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you so much, sir. Highly obliged for your time. $\endgroup$ – Sen47 Jun 30 '19 at 14:18
  • $\begingroup$ @Sen47: You're welcome. Thanks for the credit. $\endgroup$ – Markus Scheuer Jun 30 '19 at 14:20

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.