1
$\begingroup$

I got this question in an exam I was giving-

Alice and Bob are playing a game. There are $n$ coins laid out on a circular table, at positions marked from $1$ to $n$. In each round, Alice picks a list of positions. Bob then looks at this list, and can choose to cyclically shift the coins on the table by any number of positions. Finally, the coins at the positions chosen by Alice are flipped. Alice wins the game if at some point, all coins have "Heads" on top. For what values of $n$ can Alice guarantee a win, regardless of the initial configuration of the coins?

My approach was to think that if there is such an $n$, then in some sense, it has some property that is invariant under "cyclical shifts". So, the divisors of $n$ may play an important role. Especially, prime numbers may get involved as well. But, that's all the intuition I have. Nothing significant clicked from it. Any help would be appreciated.

$\endgroup$
4
  • $\begingroup$ Do you know that the person who asked can vote and/or mark one answer as "accepted"? Please see math.stackexchange.com/tour $\endgroup$
    – Robert Z
    Jun 23, 2021 at 7:50
  • $\begingroup$ At the beginning of the Game are all heads down? $\endgroup$
    – miracle173
    Jun 23, 2021 at 12:29
  • $\begingroup$ @miracle173 I don't think so. $\endgroup$ Jun 23, 2021 at 13:42
  • $\begingroup$ Can you add an example gor such a Game so that i can Check of i Unterstand you correctly? I think for n=4 Alice will Alexas win $\endgroup$
    – miracle173
    Jun 23, 2021 at 13:55

1 Answer 1

4
$\begingroup$

Let's represent the coins with a vector in $Z_2^n$, with $0$ representing heads, $1$ representing tails.

Let $G$ be the group acting on $Z_2^n$ generated by a cyclic permutation of the basis vectors.

Let $V$ be the set of all configuration from which Alice is guaranteed a win.

The game is equivalent to the following: Alice presents Bob with a collection of sequences $s_i$ of vectors, subject to some restrictions, from which Bob selects one. Alice can win from configuration $v$ if every sequence available to Bob satisfies $\sum s_i = v$.

Note that if $S$ and $T$ is a valid set of sequences of vectors for Alice to present to Bob (a "valid play"), then the set $U$ of concatenations of a sequence from $S$ with a sequence from $T$ is also a valid play.

Theorem: $V$ is a vector space.

Proof:

Note that $0\in V$.

Suppose $u$ and $v$ are in $V$. Then $u+v\in V$ also. This is because Alice has valid plays $S$ and $T$ for which every sequence $s_i\in S$ has $\sum s_i=\{u\}$ and every sequence $t_i\in T$ has $\sum t_i=\{v\}$. Then, let $U$ be the set of concatenations of sequences in $S$ and $T$, and note that for every $u_k\in U$, $\sum u_k=\sum s_i+\sum t_j=u+v$.

This is enough to prove $V$ is a vector space, since the field has characteristic 2.

Note that $V$ must be a union of orbits of $G$. Given an orbit $A\subseteq V$, one of the following must be true:

  • either $A=\{0\}$
  • Alice has a valid play $S$ such that for every sequence $s_i\in S$, no subsequence $s_1+\dots+s_k$ of $s$ has $a+s_1+\dots+s_k\in A$ for any $a\in A$.

Otherwise, Bob can force a stalemate by repeatedly visiting $A$.

The latter statement is equivalent to the following: if Alice can win, then for every subsequence $s_j$ of every $s_i\in S$, $\sum s_j\neq\{0\}$.

Hence, each move of the game removes a collection of orbits from $V$.

The subspace of possible configurations after $k$ moves is still a vector space. [Proof: exercise] and is still a union of orbits of $G$. Hence, there is a sequence of subspaces $V = V_0, V_1, V_2,..., V_m = \{0\}$ representing the possible configurations of the game after each of Alice's optimal moves (the fact that $m$ might vary from game to game doesn't change this. Either allow $V_i=V_j$, or assume Bob is playing optimally to maximise the length of the game).

It's better to renumber these subspaces: $W_k = V_{m-k}$, so $W_0=\{0\}$, and $W_m=V$.

Then, I think you can make good progress by asking:

  • What could $W_1$ possibly be?
  • Now you know that, what could $W_2$ possibly be?

I have a proof that $W_1=\langle (1,1,1...,1)\rangle$. I'm almost certain that $W_2$ only exists if $n$ is even, and equals $\langle(1,1,...,1), (1,0,1,0,....,1,0)\rangle$. I haven't tried to work out $W_3$ yet.

I have a sneaking suspicion that $V=Z_2^n$ if and only if $n$ is a power of 2, but that's just a vague feeling at this stage.

$\endgroup$
2
  • 1
    $\begingroup$ See also n buttons on a table in Puzzling SE. $\endgroup$ Jun 23, 2021 at 9:26
  • $\begingroup$ That's neat. It's the same as this one would be if Alice were playing blind. $\endgroup$ Jun 24, 2021 at 1:26

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.