18 juillet 20193 août 2020 Patrick Meyer Tic-tac-toe is a game where two players successively choose one empty cell of a 3x3 grid to be filled with their respective color. The first player to have three aligned cells (horizontal, vertical, or diagonal) of the same color wins the game. Describe what a vertex in the arena of tic-tac-toe could look like: A couple (i, j) where 1 ≤ i and j ≤ 3. A partially colored 3x3 grid with an indication of which player should play next. A list of the empty cells. Which player(s) have a winning strategy in a game of tic-tac-toe? Both players. The first one to play. The second one to play. None of them. Imagine a game in which the arena contains n vertices. Consider that a player has exactly 3 possible actions from each vertex of the arena. What is the maximum number of possible strategies? n. 3n. n³. 3n. Imagine that we play a game on a graph. We start with a graph containing n vertices and no edges. On each turn, a player must add an edge to the graph. The first player to add an edge that forms a triangle (i.e., there exists v1, v2, v3 such that {v1, v2}, {v2, v3}, {v1, v3} are edges) wins the game. For which values of n does the first player to add an edge have a winning strategy? Never. When the integer division of n by 2 is even. When the integer division of n by 2 is odd. Now consider a variant of the previous game: the first player to add an edge always adds blue edges, and the second player always adds red edges. The game finishes when all edges have been added to the graph. We start with 5 vertices. How many games are there? 2¹⁰. 10!. 10. Time is Up!
