Please Login to access more options.
Problem 20(The Game Of Permutation Scoring On A Square)
Let's play the game of scoring on the automorphism group of the square. We know there are 8 automorphism. Play this game a few times to get a feel for what different choices will give.
- Show there is no way for player 1 to win on the first move.
- If player 1 takes any of the flips for their first move, what should player 2 choose to win the game?
- Does player 1 have a winning strategy? What is it?
Solution
1. Recall that the number of automorphisms of $\mathcal{G}$ are eight in total, four flips and four rotations, as given in the table below.
| Rotations | Flips |
|---|---|
| $\sigma_0 = ()$ | $\sigma_{H} = (1, 2)(3, 4)$ |
| $\sigma_{90^\circ} = (1, 2, 3, 4)$ | $\sigma_{D} = (2, 4)$ |
| $\sigma_{180^\circ} = (1, 3)(2, 4)$ | $\sigma_{D'} = ( 1, 3 )$ |
| $\sigma_{270^\circ} = (1, 4, 3, 2)$ | $\sigma_{V} = (1, 4)(2, 3)$ |
Consider the following scenarios: 1) player one takes $\sigma_0$ and $span\{\sigma_0\}$ which is still just $\sigma_0$, 2) player one takes either $\sigma_{90^\circ}$ or $\sigma_{270^\circ}$ and either of their spans, which are equal, and which span the set of rotation permutations, 3) player one takes $\sigma_{180^\circ}$ and its span which is $span\{ \sigma_{180^\circ} \} = \{ \sigma_{90^\circ}, \sigma_{180^\circ} \}$, or 4) player one takes one of the flip permutations, $\sigma_i$ for $i \in \{ H, D, D', V \}$, and its span which is $span\{ \sigma_i \} = \{ \sigma_i, \sigma_0 \}$.
Thus, in any of the above scenarios, we see that player one cannot win no matter what move he makes.
2. In order to win, player two should take either the $90^{\circ}$ or $270^{\circ}$ rotation permutations since they will span the entire rotation permutations and flip permutations. For example, if player one took $\sigma_H$, the when player 2 takes $\sigma_{90}$ they also obtain
$$ \begin{align} \sigma_{90^{\circ}}^1\circ \sigma_{H}&= (1, 2, 3, 4) \circ (1, 2)(3, 4) = ( 1, 3 ) = \sigma_{D'}, \\ \sigma_{90^{\circ}}^2\circ \sigma_{H}&= (1, 2, 3, 4) \circ (1, 2, 3, 4) \circ (1, 2)(3, 4) = (1, 4)(2, 3) = \sigma_{V}, \text{ and}\\ \sigma_{90^{\circ}}^3\circ \sigma_{H}&= (1, 2, 3, 4) \circ (1, 2, 3, 4) \circ (1, 2, 3, 4) \circ (1, 2)(3, 4) = (2, 4) = \sigma_D. \end{align} $$ Thus player 2 removes all the remaining flips (as well as clearly the other rotatations). A similar argument can be made for each flip.
3. In order for player one to win, each of his strategies should start by taking $\sigma_{180^\circ}$, since this move will take away only $\sigma_{180^\circ}$ and $\sigma_0$; therefore, if player two follows with either a flip or a rotation, then player two will span only the flip permutations or the rotation permutations respectively. Which then upon player one's next turn can take either the flip or rotation permutation that player two did not take, and span the entire space as was shown above. To show that this is the case we only need to consider the composition combinations of permutations for $\sigma_{180^{\circ}}$ and any of the flips, given that there is no need to list the combinations for the rotations since we know that choosing any one of them will only span the rotation permutations. It then follows that
$$ \begin{align} \sigma_{180^\circ} \circ \sigma_H &= (1, 3)(2, 4) \circ (1, 2)(3, 4) = (1, 4)(2, 3) = \sigma_V, \\ \sigma_{180^\circ} \circ \sigma_D' &= (1, 3)(2, 4) \circ (1, 3) = (2, 4) = \sigma_D, \\ \sigma_{180^\circ} \circ \sigma_D &= (1, 3)(2, 4) \circ (2, 4) = (1, 3) = \sigma_D', \text{ and}\\ \sigma_{180^\circ} \circ \sigma_V &= (1, 3)(2, 4) \circ (1, 4)(2, 3) = (1, 2)(3, 4) = \sigma_H. \end{align} $$
Tags
- 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.