Abstract Algebra IBL Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Simple Shift Repetition Game ======
==== Problem ====
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?


----
==== Remarks ====  
  * Make remarks with a list.

----
==== $\LaTeX$ version ====
<file tex problem.simple_shift_repetition_game.tex>
%%%%%
% DEPENDENCIES
% RequiredPackages: \usepackage{tikz}
% RequiredMacros: \DeclareMathOperator{\aut}{Aut} 
%%%%%
\begin{problem}
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.
\begin{enumerate}
\item 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\}$). 
\item 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. 
\item 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\}$.  
\item Whoever take the last element of $H$ wins. The game can also be played as a misere game. 
\end{enumerate}
Answer the following questions.
\begin{enumerate}
\item Player 1 takes $\phi_6$.  Which elements should be removed from $H$
\item Is there a way for player 1 to win on the first move? Explain. 
\item 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)?
\item If we play this as a misere game, does player 1 have a winning strategy?
\end{enumerate}
\end{problem}
</file>

----
==== External links ====
  * [[wp>Dihedral group]]

{{tag>problem}}
Abstract Algebra IBL Wiki

User Tools

Site Tools

Page Tools
