6
$\begingroup$

Alberto places N checkers in a circle. Some, perhaps all, are black; the others are white. (The distribution of colors is random.) Betiil places new checkers between the pairs of adjacent checkers in Alberto's ring: she places a white checker between every two that are the same color and a black checker between every pair of opposite colors. She then removes Alberto's original checkers to leave a new ring of N checkers in a circle.

Alberto then performs the same operation on Betiil's ring of checkers following the same rules. The two players alternately perform this maneuver over and over again.

Show that if N is a power of two, then all the checkers will eventually be white, no matter the arrangement of colors Alberto initially puts down. Also, what happens if N is not a power of 2?

$\endgroup$
6
$\begingroup$

Here is an intuitive proof:

For $n=2^1$ the statement is easily verified. Assume the claim has been established for $n=2^k$ for some positive integer $k$. We will show that it also holds for $n=2^{k+1}$. Split the ring into two by assigning the checkers alternatingly to subring y and z [1]. Now observe that a pair of moves on the full ring translates to a single move on each subring [2]. $\square$

More formal/detailed version key steps

[1] More formally, write $x_i(t)$ for the $i$th checker after $t$ moves (after each move we identify the checker placed between checkers $i$ and $i+1$ with checker $i$; here obviously $n+1$ is understood to equal $1$). Then writing $\oplus$ for exclusive or with convention $0=$white, $1=$black the rule of move is $x_i(t+1)=x_i(t)\oplus x_{i+1}(t)$. The subrings are given as $y_i = x_{2i-1}$ and $z_i = x_{2i}$. [2] More formally, write $t'=2t$ and derive the movement rule for $z$ ($y$ works the same way) $z_i([t+1]') = x_{2i}(2t+2) = x_{2i}(2t+1) \oplus x_{2i+1}(2t+1) $ $= (x_{2i}(2t) \oplus x_{2i+1}(2t)) \oplus (x_{2i+1}(2t) \oplus x_{2i+2}(2t)) = x_{2i}(2t) \oplus x_{2i+2}(2t) = z_i(t') \oplus z_{i+1}(t')$

If $n$ is not a power of two

we can nonetheless apply the same procedure as above as long as $n$ is even; so wlog we assume that $n$ is odd. If the position is not all-white or all-black from the beginning it will never be. Indeed if there is at least one black and one white checker, this will still be the case after a move because there must be a pair of unequal colors next to each other and there must also be a same-color pair of neighbors somewhere because $n$ is odd $\square$

| improve this answer | |
$\endgroup$
  • $\begingroup$ a pair of moves on the full ring translates to a single move on each subring: indeed (xi⊕xi+1)⊕(xi+1⊕xi+2)=xi⊕xi+2 . i don't understand this one can you please explain ? $\endgroup$ – Shiv Prateek Sep 13 at 6:05
  • $\begingroup$ @ShivPrateek I've now written it out in fine detail, HTH! $\endgroup$ – Paul Panzer Sep 13 at 6:44
  • $\begingroup$ thanks for the effort. $\endgroup$ – Shiv Prateek Sep 13 at 7:32
2
$\begingroup$

Interpreting white checkers as 0s and black checkers as 1s, the checker that goes between 2 checkers is their sum mod 2. (Also known as the XOR of their values.) We can interpret the state of the ring as a vector, and the function that takes us from one ring to the next is a linear function (mod 2). Take the basis vectors to be those with a 1 in one place on the ring, and 0s everywhere else. If we can find out the fate of these basis vectors, we can find out the fate of the entire ring by summing the fates of the basis vectors corresponding to the initial configuration of the ring. Since the ring can be rotated without changing the rules, we really only need to find the fate of just one of the basis vectors, all the others will be the same.

Let $\omega=e^{2\pi i/N}$. We'll interpret our vectors as polynomials in $\omega$. (The fact that the ring loops around is taken care of by the fact that $\omega^N = 1$.) Going from one state to the next corresponds to multiplying by $(1+\omega)$. Our basis vector is just equal $1\times\omega^0=1$. Updating $n$ times corresponds to multiplying by $(1+\omega)^n$. After $N$ steps, we will have $(1+\omega)^N \times 1$. By the binomial theorem, this equals:

$$ \sum_{k=0}^N \binom{N}{k}\omega^k = 1 + \omega^N + \sum_{k=1}^{N-1} \frac{N!}{k!(N-k)!}\omega^k $$

$$ = 2 + \sum_{k=1}^{N-1} \frac{N!}{k!(N-k)!}\omega^k $$

Now suppose that $N$ is a power of 2, that is $N=2^n$. Then we have:

$$ 2 + \sum_{k=1}^{2^n-1} \frac{2^n}{2^n-k}\frac{(2^n-1)!}{k!(2^n-k-1)!}\omega^k = 2 + \sum_{k=1}^{2^n-1} \frac{2^n}{2^n-k}\binom{2^n-1}{k-1}\omega^k $$

We can then see that in the sum, the coefficients of the $\omega^k$ will all be even. So, mod 2, they will all be equal to 0. Similarly, the coefficient of $\omega^0$ is 2, which is also equal to 0 mod 2. So the result will be all 0s (i.e. all white checkers).

If $N$ is not a power of 2, then there will be some odd binomial coefficients in the sum, so the vectors will not go to 0 after $N$ steps at least, and maybe not ever.

| improve this answer | |
$\endgroup$
  • $\begingroup$ that's an interesting answer, consider a ring with 6 checkers having black and white placed alternatively then the final step is reached after 2 steps can you explain ths..? $\endgroup$ – Shiv Prateek Sep 13 at 2:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.