Maths Olympiad Prep

Library / /35 of 61

Combinatorics Difficulty 6.5 National Olympiad Prove it Canada

Problem:

Two circles of different radii are cut out of cardboard. Each circle is subdivided into 200 equal sectors. On each circle 100 sectors are painted white and the other 100 are painted black. The smaller circle is then placed on top of the larger circle, so that their centers coincide. Show that one can rotate the small circle so that the sectors on the two circles line up and at least 100 sectors on the small circle lie over sectors of the same color on the big circle.

Solution

Solution:

Let x0,,x199x_{0}, \ldots, x_{199} be variables. Assign the value of +1+1 or 1-1 to xix_{i} depending on whether the (i+1)(i+1)st segment of the larger circle (counting counterclockwise) is black or white, respectively. Similarly, assign the value of +1+1 or 1-1 to the variable yiy_{i} depending on whether the (i+1)(i+1)th segment of the smaller circle is black or white. We can now restate the problem in the following equivalent way: show that
Sj=i=1200xiyi+j0 S_{j} = \sum_{i=1}^{200} x_{i} y_{i+j} \geq 0
for some j=0,,199j = 0, \ldots, 199. Here the subscript i+ji+j is understood modulo 200200.

Now observe that y0++y199=0y_{0} + \cdots + y_{199} = 0 and thus
S0++S199=i=0199xi(y0++y199)=0. S_{0} + \cdots + S_{199} = \sum_{i=0}^{199} x_{i} (y_{0} + \cdots + y_{199}) = 0.
Thus Sj0S_{j} \geq 0 for some j=0,,199j = 0, \ldots, 199, as claimed.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.