Maths Olympiad Prep

Library / Mongolian Mathematical Olympiad 46 /3 of 5

Mongolian Mathematical Olympiad 46

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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.