2
$\begingroup$

I don't know much about abstract algebra and would appreciate some help in framing a problem in a group-theoretic way (if it's possible).

The problem

There are $n$ cups in a row, some of them upside down. Is there a way to turn them all right-side up by turning three consecutive cups repeteadly?

I knew the solution to the problem in which the allowed operation is turning two consecutive cups. One can see that, assigning 0 to upside down cups and 1 to the rest, the parity of the configuration does not change.

So I was looking for an invariant for the three-consecutive-cups variation and found one.

The solution

We can assign the weights $w_1 = (1, 1)$, $w_2 = (0, 1)$ and $w_3=(1, 0)$ to the cups cyclically (so that we will always turn one cup with each weight) and add them modulo 2. This is an invariant, as one can see in a case-by-case check:

$$000 \Leftrightarrow 111 \equiv (0,0) = w_1+w_2+w_3$$ $$001 \Leftrightarrow 110 \equiv w_3 = w_1+w_2$$ $$010 \Leftrightarrow 101 \equiv w_2 = w_1+w_3$$ $$100 \Leftrightarrow 011 \equiv w_1 = w_2+w_3$$

Now, if we have $n$ cups, there are $n-2$ possible operations (turning cups $123$, or $234$, ... or $(n-2)(n-1)n$). We then have $2^{n-2}$ combinations of those operations. But there are $2^n$ different possible states for $n$ cups, which means there are $2^2$ families of states, which correspond to the 4 possible values for the invariant: $(0,0), (0,1), (1,0), (1,1)$. Since there are not different combinations of operations that yield the same result (because $(1,1,1,0,...,0)$, $(0,1,1,1,0,...,0)$, $\dots$, $(0,...,0,1,1,1)$ are all linearly independent) all states with a given invariant are reachable from any other state of that family.

A group-theory solution?

OK, now for my question. I've been studying a bit of abstract algebra and this looks like it could be expressed in that language, but I don't know how. The group would be $\Bbb Z2 \times...\times\Bbb Z2 $ and the operation addition modulo 2. The "families" of solutions look to me like cosets, somehow, but I don't that's think right because a coset is the subset obtained by applying a certain operation (let's say $(1,1,1,0,...,0)$) to all members of the group.

That's not what I do here. Instead, in this problem we are interested in finding what members are reachable by applying a combination of the allowed operations. Maybe it is more like a vector space and not a group?

I'd like some insight into this to better grasp the problem in a more formalized way. Thank you!

$\endgroup$
  • $\begingroup$ Just FYI, the wikipedia page that you linked to (for the two cups problem) allows flipping any two cups, not just adjacent cups. $\endgroup$ – angryavian Apr 13 '18 at 16:34
  • $\begingroup$ Oh, you're right! It doesn't make any difference for the two cups problem, though. $\endgroup$ – Guille Vicente Apr 13 '18 at 16:35
0
$\begingroup$

Letting $\def\F{\mathbb F}\F_2$ be the finite field with two elements, the set of states in this problem is $\F_2^n$, as you mentioned. This is a group, but is also an $n$-dimension vector space over $\F_2$, and the latter interpretation is more fruitful.

There are $n-2$ different triplets of cups that can be turned over, so each possible method of turning over cups is represented by a vector in $\F_2^{n-2}$. To figure out how a strategy $x\in \F_2^{n-2}$ affects an arrangement $a\in \F_2^n$, you just have to multiply $x$ by this $n\times(n-2)$ matrix: $$ A = \begin{bmatrix} 1 & 1 & 1 & 0 & 0 &0 &\dots&0&0&0\\ 0 & 1 & 1 & 1 & 0 &0 &\dots&0&0&0\\ 0 & 0 & 1 & 1 & 1 &0 &\dots&0&0&0\\ 0 & 0 & 0 & 1 & 1 &1 &\dots&0&0&0\\ &\vdots\\ 0& 0&0&0&0&0&\dots&1&1&1\end{bmatrix} $$ The effect of the strategy is to change $a$ into $xA + a$. Therefore, to determine whether an arrangement $a$ can be transformed into $a'$, you need to solve the matrix equation $$ xA=a'-a:=b $$ Right off the bat, we know that the rank of $A$ is at most $n-2$, so that the set of vectors $b$ for which the above equation can be solved is a subspace with dimension at most $n-2$. Going even further, we can use standard linear algebra techniques to explicitly describe the subspace of $b$ for which this can be solved. After doing so, you will come up with the same clever invariant.

This cup puzzle has the same mathematics as the game lights out, where there is a grid of buttons which are all on or off, and touching a button toggles itself along with its neighbors. For more info, you might want to check out https://www.jaapsch.net/puzzles/lomath.htm.

$\endgroup$
  • $\begingroup$ Thank you, very interesting! I don't know how I could find that subspace of $b$, though. Could you point me to some documentation or something? I knew that game but hadn't thought about it in this way! I'll take a look. $\endgroup$ – Guille Vicente Apr 14 '18 at 12:13

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.