# How can I express this problem (a generalization of the three cups problem) in a group-theoretic way?

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!

• Just FYI, the wikipedia page that you linked to (for the two cups problem) allows flipping any two cups, not just adjacent cups. Commented Apr 13, 2018 at 16:34
• Oh, you're right! It doesn't make any difference for the two cups problem, though. Commented Apr 13, 2018 at 16:35

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.
• 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. Commented Apr 14, 2018 at 12:13