# Game on groups (generalization of spinning switches puzzle)

Alice and Bob are playing a game as follows:

Initially

• There're two subgroups $$A,B$$ of Sym(n) known to both Alice and Bob
• There're $$n$$ slots $$S_1, \cdots, S_n$$ and $$n$$ boxes $$B_1, \cdots, B_n$$. Initially $$i$$-th box is on $$i$$-th slot.
• On each box, Bob secretly writes an element of $$A$$ and closes the lid (the element is not known to Alice). An element of $$A$$ can appear in multiple/no box.

At each step:

• Alice picks a subset $$S$$ of $$S \subset \{1, 2, \cdots, n \}$$, and an element $$a \in A$$, and tells Bob $$S$$ and $$a$$.
• For each $$i \in S$$, Bob replaces the element $$x \in A$$ written on the box on $$S_i$$ with $$xa$$.
• If after the previous step the element in all the boxes is the identity element then the game is over and Bob informs Alice that he won the game.
• Bob picks an element (this element is not known to Alice) $$\pi \in B$$ and for all $$i \in \{1, 2, \cdots, n \}$$ simultaneously moves the box in $$S_i$$ to $$S_{\pi(i)}$$.

Given $$(A,B)$$, determine whether Alice has a winning strategy or not. (Alice wins if there's a constant $$c$$ such Alice is guaranteed to win under $$c$$ moves, no matter how Bob plays)

For the particular case $$(A,B) = (\mathbb{Z}_2, \mathbb{Z}_4)$$ we get the following "folklore" problem (wording taken from Peter Winkler's book):

[Spinning switches] Four identical, unlabeled switches are wired in series to a light bulb. The switches are simple buttons whose state cannot be directly observed, but can be changed by pushing; they are mounted on the corners of a rotatable square. At any point, you may push, simultaneously, any subset of the buttons, but then an adversary spins the square. Show that there is a deterministic algorithm that will enable you to turn on the bulb in at most some fixed number of steps.

I'm unable to solve the general problem (except for a very few almost trivial special cases like above), any ideas how to solve this ? The proof of the above puzzle can be adapted to show that $$(\mathbb{Z}_2, \mathbb{Z}_n)$$ is winnable iff $$n$$ is a power of 2.

• So we must be given already a permutation representation of $B$ that takes $\pi$ to a permutation $i \mapsto \pi(i)$? It's a little confusing, but it looks to me that you are making some identification between $\{1, 2,\ldots, n\}$ and the elements of $B$. Also: shouldn't the particular case described below the fold be $(A, B) = (\mathbb{Z}_2, \mathbb{Z}_4)$? Jun 15, 2019 at 11:09
• @ToddTrimble Oops, sorry. You're right on both instances; please see the first bullet point (where I clarified $B$ is a subgroup of Sym(n)) Jun 15, 2019 at 11:12

I looked at a very similar problem in my dissertation, with mostly cosmetic changes and one substantive change (italicized):

• Alice picks a subset $$S$$ of $$S \subset \{1, 2, \dots, n\}$$, and a sequence of elements $$a_i \in A$$, and tells Bob $$S$$ and $$a_i$$.

My work principally builds on three papers: Bar Yehuda, Etzion, and Moran (1993); Ehrenborg and Skinner (1995); and Rabinovich (2022).

Here are the main findings:

• If $$A$$ and $$B$$ are both $$p$$-groups (with the same $$p$$), then Alice has a winning strategy.
• If $$A$$ is generated by involutions (e.g. symmetric groups or the monster group) and $$B = \mathfrak{S}_2$$, the symmetric group on two letters, then Alice has a winning strategy.
• If $$A$$ has a quotient group that is a $$p$$-group and $$B$$ has any subgroup that is a $$q$$ group and $$p \neq q$$, then Alice does not have a switching strategy.

This takes care of quite a lot of pairs $$(A, B)$$, but certainly not all of them.