Browse · MathNet
PrintChina Western Mathematical Olympiad
China counting and probability
Problem
There are white and black balls placed randomly on the circumference of a circle. Starting from a certain white ball, number all white balls in a clockwise direction by . Likewise, number all black balls by in an anti-clockwise direction starting from a certain black ball. Prove that there exist consecutive balls whose numbering forms the set .
Solution
Proof Choose a black ball and a white ball with the same number, and the number of balls between the two balls is minimum. We can suppose the number of the two balls is . Firstly, we shall prove that the balls between the two balls have the same color.
In fact, if they are of different color, then the white ball and the black ball, each is numbered by , are between the two balls (See Fig. 1). This is a contradiction to the point that number of balls between the two balls (labelled by ‘1’ s) is a minimum.
Secondly, if the balls between the two balls (labelled by ‘1’s) are white, we have two cases.
Case 1 The number of the white balls are . See Fig. 2, then from the white balls (labelled by ‘1’s) in anti-clockwise direction we can get a chain of balls whose numbering forms the set .
Fig. 1
Fig. 2
Case 2 The number of the white balls are (See Fig. 3), then from the white ball (labelled by ‘1’s) in clockwise direction we can have a chain of balls that satisfies the condition.
The same argument can prove that the claim holds, if the balls between the two balls (labelled by ‘1’s) are black, or there are no ball between them.
Fig. 3
In fact, if they are of different color, then the white ball and the black ball, each is numbered by , are between the two balls (See Fig. 1). This is a contradiction to the point that number of balls between the two balls (labelled by ‘1’ s) is a minimum.
Secondly, if the balls between the two balls (labelled by ‘1’s) are white, we have two cases.
Case 1 The number of the white balls are . See Fig. 2, then from the white balls (labelled by ‘1’s) in anti-clockwise direction we can get a chain of balls whose numbering forms the set .
Fig. 1
Fig. 2
Case 2 The number of the white balls are (See Fig. 3), then from the white ball (labelled by ‘1’s) in clockwise direction we can have a chain of balls that satisfies the condition.
The same argument can prove that the claim holds, if the balls between the two balls (labelled by ‘1’s) are black, or there are no ball between them.
Fig. 3
Techniques
Coloring schemes, extremal arguments