Maths Olympiad Prep

Library / /3 of 6

Combinatorics Difficulty 5.3 AIME, harder Prove it Mongolia

Given are 2n2n people and it is known that their heights are all different. They have to stand in two rows, each with nn people. How many different positions are there, if the front row person is always shorter than the back row person?

Solution

In the first seats of the rows, we can choose 2 people 2n(2n−1)2\frac{2n(2n-1)}{2} different ways. Then in the second seats of the rows, we can choose 2 people (2n−2)(2n−3)2\frac{(2n-2)(2n-3)}{2} different ways. Continuing this, we have
2n(2n−1)2⋅(2n−2)(2n−3)2⋯2⋅12=(2n)!2n. \frac{2n(2n-1)}{2} \cdot \frac{(2n-2)(2n-3)}{2} \cdots \frac{2 \cdot 1}{2} = \frac{(2n)!}{2^n}.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.