Skip to main content
OlympiadHQ

Browse · MathNet

Print

Belorusija 2012

Belarus 2012 counting and probability

Problem

boys (), 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 to of the same parity as .

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 be the number of the tall boys in the arrangement. Then the number of the middle boys is equal to and has the same parity with . Since the number of the tall boys in the arrangement can admit any value from (see solution of Problem C.8), the number of the middle boys can admit any value from and must be the same parity as . The corresponding examples for any see in solution of Problem B.8.
Final answer
Any integer from 0 to N−2 with the same parity as N.

Techniques

Invariants / monovariantsCounting two ways