Counting Chips On a Circle

You are to place evenly 2n red and 2n green chips, for some integer n ≥ 1, on a circle. Prove that there always is a half circle with an equal amount of red and green chips.

(The applet below is to help you experiment with the problem. There are 4N small circles in a circular formation. Clicking on any of those changes its color from green to red and vice versa.)


If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

Counting Chips On a Circle


What if applet does not run?

Solution

|Activities| |Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

Solution

You are to place evenly 2n red and 2n green chips, for some integer n ≥ 1, on a circle. Prove that there always is a half circle with an equal amount of red and green chips.

For each number m, 1 ≤ m ≤ 4n, let r(m) and g(m) be the numbers of red and green chips on the half circle that starts with m. (Throughout we use arithmetic modulo 4n.)

Two numbers r(m) and r(m+1) either coincide or differ by 1. It all depends on whether the chips in locations m and m + 2n are of the same or of different colors. For, in passing from r(m) to r(m+1) one of the chips is removed while another is added to the count. The same is of course true for g(m) and g(m+1).

Observe that if, for some m, r(m) < g(m) then r(m + 2n) > g(m + 2n), and vice versa. Indeed the second inequality reflects on the quantities of the chips in the half circle complementary to the one starting with m. Also, since r(m) + g(m) = 2n, the number of chips in a half circle, assuming r(m) < g(m) we get that r(m) < n and n < g(m). Furthermore, if, say, r(m) < n then r(m + 2n) > n.

Compare the quantities r(m + i) and g(m + i), i = 0, 1, ..., 2n. If r(m) = g(m), we are done. Otherwise, if, e.g, r(m) is the smaller of the two, then, as we just saw

r(m) < n and r(m + 2n) > n.

By letting i change from 0 to 2n we shall arrive from r(m) to r(m + 2n) by changing the quantity by at most 1 on every step. Thus it must be that for some i, r(m + i) = n. For this i, also g(m + i) = n and, therefore, r(m + i) = g(m + i).

References

  1. J. Tanton, A Dozen Questions About A Dozen, Math Horizons, April 2007, pp. 12-16

|Activities| |Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

71471352