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.
