Browse · MathNet
Print56th Ukrainian National Mathematical Olympiad, Third Round
Ukraine counting and probability
Problem
30 children – boys and girls – formed a circle. It occurred that there is no child such that both its neighbors are boys. What is the least possible number of girls there?
Solution
Consider a group of consecutive boys. There are less than 3 boys in this group. Also consider a group of consecutive girls. There are at least 2 girls in the group. These groups follow each other hence their amounts are equal. Assume that it may occur that there are 15 boys and 15 girls. Then there are at least 8 groups of boys, hence there are at least 8 groups of girls and there are at least 16 girls in total. So there are at most 14 boys and at least 16 girls.
It is easy to see that the desired arrangement exists. Consider 7 groups each consisting of 2 boys which are alternating by 6 groups of girls consisting of 2 and one group consisting of 4.
It is easy to see that the desired arrangement exists. Consider 7 groups each consisting of 2 boys which are alternating by 6 groups of girls consisting of 2 and one group consisting of 4.
Final answer
16
Techniques
Coloring schemes, extremal argumentsPigeonhole principle