Maths Olympiad Prep

Library / /45 of 54

Combinatorics Difficulty 6.9 National olympiad Prove it China

There are nn white and nn 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 1,2,,n1, 2, \dots, n. Likewise, number all black balls by 1,2,,n1, 2, \dots, n in an anti-clockwise direction starting from a certain black ball. Prove that there exist consecutive nn balls whose numbering forms the set {1,2,,n}\{1, 2, \dots, n\}.

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 11.
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 nn, 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 2,,k2, \dots, k. See Fig. 2, then from the white balls (labelled by ‘1’s) in anti-clockwise direction we can get a chain of nn balls whose numbering forms the set {1,2,,n}\{1, 2, \dots, n\}.

Figure 1
Fig. 1

Figure 2
Fig. 2

Case 2 The number of the white balls are k,k+1,,nk, k+1, \dots, n (See Fig. 3), then from the white ball (labelled by ‘1’s) in clockwise direction we can have a chain of nn 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.

Figure 3
Fig. 3

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.