2
$\begingroup$

This is an extended version of this question, more carefully presented for professional mathematicians.


Consider a two-player game on the complete undirected graph $K_5$, in which edges are initially uncolored. Player A chooses an uncolored edge and colors it blue, then player B chooses an uncolored edge and colors it red. Players alternate until one player (the loser) is forced to have colored three edges forming a triangle with the same color. (Such a game can end in a draw, as $K_5$ can be expressed as the union of two 5-cycles, as Gerhard Paseman points out.) Assume that on each move a player avoids completing such a triangle, if possible.

Questions

  • How many distinguishable games are there? Two games are distinguishable if there is no permutation of the vertex labels (and hence edge labels) that yields the same sequence of moves.
  • What is the discrete distribution of total moves in distinguishable games, assuming each valid game is equally likely?
  • One can use Ramsey theory to count the number of end configurations that end in a draw. What is the number of distinguishable games than end in a loss for player A, loss for player B, or draw?
  • Generalize the above to $K_n$ for arbitrary $n \in \mathbb{Z}^+$.
$\endgroup$
4
  • $\begingroup$ Uh, $K_5$ can end in a draw as it is the union of two 5 cycles. Look up Ramsey numbers to see $R(3,3)=6$. Gerhard "It's A Problem Of Friendship" Paseman, 2017.03.31. $\endgroup$ Mar 31, 2017 at 17:18
  • $\begingroup$ You are correct. Thank you. I'll change the problem accordingly. $\endgroup$ Mar 31, 2017 at 17:21
  • $\begingroup$ The $K_5$ game plays can almost be enumerated by hand, especially if you stop when a triangle is formed. I get 1 game for 1 move, 2 for 2 moves, 7 for 3 edges picked. This leaves less than 5040 continuations for each of the 7 cases, and it is likely a tenth of that. Have you tried hand enumeration? Gerhard "I Don't Mean Finger Counting" Paseman, 2017.03.31. $\endgroup$ Mar 31, 2017 at 19:20
  • $\begingroup$ "Assume on each move a player avoids completing such a triangle, if possible." $\endgroup$ Mar 31, 2017 at 19:22

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.