Browse · MathNet
PrintBelorusija 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.
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