Let $G \neq {1}$ be a finite group. Two players I $\&$ II, that know the group $G$ are playing the following game: Player I chooses a prime $p_1$ and then the players consider the group $G(p_1)):= G^{p_1}$. Player II chooses a prime $q_1$ and they consider the group $G(p_1,q_1):=(G^{P_1})^{q_1}$. Player I, then chooses a prime $p_2$ and they consider $G(p_1,q_1,p_2)=((G^{P_1})^{q_1})^{p_2}$ and so on. The first player to reach the trivial group wins. That is, if for some $p_i$, $G(P_1,...,q_{i-1},p_i)={1}$ but $G(p_1,...,q_{i-1}) \neq {1}$, player I had won. Similarly for player II.

a) Prove that player II does not have a strategy that guarantees him a win no matter what the group $G$ is.

b) Suppose now that $G$ is abelian and let us also add the constraint that at every stage the players have to choose a prime that divides the order of the group at that stage. Provide a necessary and sufficient condition on $G$ for player I to have a winning strategy.

  • $\begingroup$ I presume by $G^p$ you mean $\{ g^p : g \in G \}$. This isn't a subgroup in general unless $G$ is abelian. Strictly speaking that doesn't affect the definition of the game, though. $\endgroup$ – Qiaochu Yuan Nov 18 '18 at 3:44
  • $\begingroup$ yes, That is correct. $\endgroup$ – mathpadawan Nov 18 '18 at 11:39

(a): There might be a strategy-stealing argument here, but I'm not convinced that I understand the question completely. It seems like the game does not terminate, since either player can always just "stall" by choosing a prime $p$ which is $1\bmod{|G|}$, and by Lagrange's Theorem, $G^p=G$. Even if we impose the restriction that the primes must be distinct, Dirichlet's Theorem permits infinite stalling.

[ Note that if infinite stalling is possible, then it is also optimal. If there is any immediately winning move, a player will take it. If any move would put their opponent in that situation, they will not. Perhaps it is intuitive that toward the "end" of the game tree, one player will not want to take a move, so will stall, but then they basically just traded seats with their opponent, who will also not want to take a move... ]

(b): Count the number of primes which divide $G$. If the number is odd, player I wins; if the number is even, player II wins. This doesn't seem to have anything to do with strategy: the outcomes are guaranteed no matter what moves the players make!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.