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.

$\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
    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
    Jun 15, 2019 at 11:12

1 Answer 1

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.

$\endgroup$

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.