Please Login to access more options.
Problem 13 (Simple Shift Repetition Game)
Consider the set of simple shift permutations $H=\{\phi_n\mid n\in \mathbb{Z}\}$ on a 26 letter alphabet. We've shown that there are 26 different functions in this set. Consider the following game.
- The first player picks an element $\sigma_1\in H$. They then remove from $H$ the span of $\sigma_1$ (so everything generated by $\{\sigma_1\}$).
- The second player now chooses an element $\sigma_2\in H$ that hasn't yet been removed. They then remove from $H$ any element in the span of $\{\sigma_1,\sigma_2\}$. At this stage, any permutation that can be written as a composition combination of the permutations $\sigma_1$ and $\sigma_2$ has been removed.
- Players alternate taking turns, choosing an element $\sigma_k\in H$ that hasn't been removed in a previous stage, and then removing from $H$ any element in the span of $\{\sigma_1,\sigma_2,\ldots,\sigma_k\}$.
- Whoever take the last element of $H$ wins. The game can also be played as a misere game.
Answer the following questions.
- Player 1 takes $\phi_6$. Which elements should be removed from $H$
- Is there a way for player 1 to win on the first move? Explain.
- What's the largest number of turns that can occur in this game (so if neither player tries to win, how long can the game go on)?
- If we play this as a misere game, does player 1 have a winning strategy?
The following pages link to this page.