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.

  1. Player 1 takes $\phi_6$. Which elements should be removed from $H$
  2. Is there a way for player 1 to win on the first move? Explain.
  3. 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)?
  4. If we play this as a misere game, does player 1 have a winning strategy?

Solution

Let $H=\{ \phi_{n}\in \mathbb{Z}_{26}\}$.

  1. Player 1 removing $\phi_{6}$ from the set means that everything spanned by said permutation is also removed. We can see that it would remove $\phi_{6}^{n}$, where $n=0,1,2,3,4,...,12$. We don't need any value of $n$ higher than 12 however because that would cycle back to being $\phi_{6}^{0}=\phi_{0}$. The elements removed, therefore would be $\{\phi_{0}, \phi_{2}, \phi_{4}, ..., \phi_{24}\}$, or all the even permutations (with the identity included).
  2. Because player 1 has no patience and really just wants to win, it might be beneficial to know that there are a number of options that would end the game on the first move. Player 1 needs to pick any odd element $\phi_{k}$, such that $k\neq 13$. We know $k\neq 13$ because selecting $\phi_{13}$ would only remove 2 elements from set $H$. So, listed out, player 1's options are $$\phi_{1}, \phi_{3}, \phi_{5}, \phi_{7}, \phi_{9}, \phi_{11}, \phi_{15}, \phi_{17}, \phi_{19}, \phi_{21}, \phi_{23}, \phi_{25}.$$ Because each of these elements has a span that generates all of $H$. By selecting any of these elements the game is over before player 2 can even blink.
  3. If, instead, the players are trying to develop the Christlike attribute of patience and see how long the game will last, it turns out they won't develop too much of it. The game can only last a maximum of 3 turns before it will end. If player 1 selects $\phi_{0}$ then only that element is removed. Player 2 then selects $\phi_{13}$ and the span of those 2 elements composed with each other will still only remove those same 2 elements. After that, it doesn't matter what player 1 picks, the game will be over. If an odd element is selected, they are all removed anyway. If an even element is removed, the span of any even element composed with $\phi_{13}$ will lead to the removal of the whole set. Looks like they need to find a new way to try their patience.
  4. With the change of rules, player 1 now needs to select $\phi_{13}$ in order to win misere style. This will remove only the two elements $\{\phi_{0}, \phi_{13}\}$. Then, regardless of what player 2 picks the span of that choice along with $\phi_{13}$ will remove all the other elements.
Tags

Change these as needed.

  • Week2 - Which week are you writing this problem for?
  • Josh - Sign your name by just changing "YourName" to your wiki name.
  • Complete
  • When you are ready to submit this written work for grading, add the phrase [[!Submit]] to your page. This will tell me that you have completed the page (it's past rough draft form, and you believe it is in final draft form). Don't type [[!Submit]] on a rough draft.
  • If I put [[!NeedsWork]] on your page, then your job is to review what I've written, address any comments made, and then delete all the comments I made. When you have finished reviewing your work, leave [[!NeedsWork]] on your page and type [[!Submit]]. (Both tags will show up). This tells me you have addressed the comments.
  • I'll mark your work with [[!Complete]] after you have made appropriate revisions.