Skip to main content
OlympiadHQ

Browse · MathNet

Print

AustriaMO2013

Austria 2013 counting and probability

Problem

Let be an integer. For a convex -gon we consider a line through that does not contain any other point of the -gon. Let be the orthogonal to through . We orthogonally project the -gon onto . For let denote the image of . The line is called valid if the points are disjoint. We consider all convex -gons and all valid lines . How many different orderings of the points do exist? G. Baron, Vienna
Solution
Each arrangement of begins with and ends with for some with . From through the projections are arranged from "top to bottom" and from through and back to from "bottom to top". The projections assume some of the intermediate positions between and , and each of these choices of positions uniquely determines the entire sequence of the . Since there are such choices possible, we see that the total number of sequences of projections is equal to
Final answer
2^{n-2}

Techniques

Recursion, bijectionAlgebraic properties of binomial coefficientsConstructions and loci