Library / /14 of 39

, 2012

Combinatorics Difficulty 5.6 AIME, harder Prove it Belarus

$N$ boys ( $N \ge 3$ ), no two of them having the same height, are arranged along a circle. A boy in the given arrangement is said to be middle if he is taller than one of his neighbors and shorter than the other one.
Find all possible numbers of middle boys in the arrangement.

Solution

Answer: any integer number from $0$ to $N-2$ of the same parity as $N$ .

Consider arbitrary arrangement of the boys along the circle. We say that a boy in the given arrangement is tall if he is taller than both of his neighbors, and a boy is short if he is shorter than both of his neighbors.

The numbers of tall and short boys are equal in any arrangement (see solution of Problem C.8). Let $b$ be the number of the tall boys in the arrangement. Then the number $s$ of the middle boys is equal to $N - 2b$ and has the same parity with $N$ . Since the number $b$ of the tall boys in the arrangement can admit any value from $1 \le b \le [N/2]$ (see solution of Problem C.8), the number $s$ of the middle boys can admit any value from $[0; N - 2]$ and must be the same parity as $N$ . The corresponding examples for any $s$ see in solution of Problem B.8.

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.