2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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)$? $\endgroup$
    – Todd Trimble
    Commented Jun 15, 2019 at 11:09
  • $\begingroup$ @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)) $\endgroup$
    – katana_0
    Commented Jun 15, 2019 at 11:12

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .