Competition problem — Combinatorics

Library / /11 of 16

Combinatorics Difficulty 6.2 National olympiad Prove it Austria

Let $n \ge 3$ be an integer. For a convex $n$ -gon $A_1A_2\dots A_n$ we consider a line $g$ through $A_1$ that does not contain any other point of the $n$ -gon. Let $h$ be the orthogonal to $g$ through $A_1$ . We orthogonally project the $n$ -gon onto $h$ . For $j = 1, \dots, n$ let $B_j$ denote the image of $A_j$ . The line $g$ is called valid if the points $B_j$ are disjoint.
We consider all convex $n$ -gons and all valid lines $g$ . How many different orderings of the points $B_1, \dots, B_n$ do exist?
G. Baron, Vienna

Solution

Each arrangement of $B_1, \dots, B_n$ begins with $B_1$ and ends with $B_k$ for some $k$ with $2 \le k \le n$ . From $B_1$ through $B_k$ the projections are arranged from "top to bottom" and from $B_k$ through $B_n$ and back to $B_1$ from "bottom to top". The $k-2$ projections $B_2, \dots, B_{k-1}$ assume some $k-2$ of the $n-2$ intermediate positions between $B_1$ and $B_k$ , and each of these choices of $k-2$ positions uniquely determines the entire sequence of the $B_i$ . Since there are $\binom{n-2}{k-2}$ such choices possible, we see that the total number of sequences of projections is equal to
$\sum_{k=2}^{n} \binom{n-2}{k-2} = \sum_{i=0}^{n-2} \binom{n-2}{i} = 2^{n-2}.$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.