# A group theoretical game: Is it possible to reach a state when only blue marbles are left?

I've found this problem in a math contest. Apparently it's solved by group theory but I have no idea how.

We're playing a game with a set of red and blue marbles arranged in a line.

Here are the rules of the game:

1. A blue marble can jump over two red marbles and kills one of the two.

2. A marble (blue or red) can jump over three adjacent red marbles and kills the three.

3. A marble (blue or red) can jump over two adjacent blue marbles and kills both.

Suppose that at the initial state we have $2007$ blue marbles, $2008$ red marbles and again $2007$ blue marbles arranged in a line.

Is it possible to reach a state when only blue marbles are left?

-

Consider the following maps $\mathbb C\to\mathbb C$ (where $\omega=e^{2\pi i/3}$): $$r(z)=\omega z$$ $$b(z)=\overline z$$

Then we have the following identities: \tag1\begin{align}b(r(r(z))&=r(b(z))\\ r(r(b(z)) &= b(r(z))\\ r(r(r(z))&=z\\ b(b(z))&=z\end{align} Finally $$\tag2\underbrace{b(b(\cdots(b}_{2007}(\underbrace{r(r(\cdots(r}_{2008}(\underbrace{b(b(\cdots(b}_{2007}(z))\cdots))=b(r(b(z)))=r(r(z))$$ is neither $z$ nor $b(z)$ because $r(r(1))=\omega^2\ne1$. Since any application of the rules of the marble game to the sequence of functions applied in $(2)$ does not change the function (because of the identities $(1)$ that match the marble game rules) and any composition of $b$s is eitzer $b(z)$ or the identity, we conclude that it is impossible to end up with only blue marbles.

Instead of using complex numbers we could also work with $\mathbb Z/3\mathbb Z$ and let $b(x)=-x\pmod 3$ and $r(x)=x+1\pmod 3$.

-

We can associate to the game, $G$ the free group generated by $r$ and $b$ with the relations:

$1) br^2=rb,r^2b = br$

$2)br^3=r^3b=b, r^4 = r$

$3)rb^2 = b^2r=r, b^3 = b$

Where we associate any given game state with a word in $G$,by sending a line of marbles to a line of $r$s and $b$s. Reducing a word in $G$ with one of the relations is equivalent to making one of the moves described in your question. So, all we need to do to solve the problem is to show that $b^{2007}r^{2008}b^{2007}$ is not equivalent to a word that is just some power of $b$.

-
That presentation reduces to $\langle b,r \mid r^3=b^2=1, brb=r^2 \rangle$, which is the dihedral group of order $6$. It is the same group as in Hagen von Eitzen's answer. The group has more relations than the game: for example $r^3=1$ in the group, but we cannot remove three red marbles when there are no blue ones around. But all the moves in the game are modelled in the group, so it works as an impossibility proof. – Derek Holt May 9 '14 at 14:59
@DerekHolt Sure, I was just explaining how to set up the group and solve the problem, in case the asker then wanted to have a go themselves after they knew roughly what to do. Another reason I think I'll leave it as is is because, for this problem, the group structure doesn't encompass the entire game state since the moves in the game aren't reversible. Thus whilst it is true that if two states give different group elements you can't move from one to another, that doesn't mean that two states give the same element, you can move from one to another. – Tom Oldfield May 9 '14 at 15:05

The rules of the game suggest a group $G$ with the presentation $$G = \langle b,r \,\, | \,\, br^2 = rb, \, br^3 = b, \, r r^3 = r, \, b b^2 = b, \, r b^2 = r \rangle$$ This presentation can be simplified to $$G = \langle b,r \,\, | \,\, r^3 = b^2 = Id, \, b^{-1} r b = r^2 \rangle$$ This group $G$ is the semidirect product $\mathbb{Z}/3 \rtimes \mathbb{Z}/2$ where the generator $b$ of the quotient $\mathbb{Z}/2 = \langle b \rangle$ acts on the kernel $\mathbb{Z}/3 = \langle r \rangle$ by taking $r$ to $r^{-1}=r^2$. So, $G$ is the order 6 dihedral group, represented geometrically as symmetries of an equilateral triangle, where $b$ is a reflection of order 2 and $r$ is a rotation of order 3.

So the question is whether the word $b^{2007} r^{2008} b^{2007}$ represents a reflection. Taking the sum of the $b$-exponents and reducing mod 2 you get the homomorphism $G \to \mathbb{Z}/2$ given by the semidirect product structure, and an element of $G$ is a reflection if and only if that sum is odd.

But $2007 + 2007$ is even.

-