Kolya and Dima play a game on an board, making moves in turn. During his turn, Kolya must put one cross in any empty cell (i.e., in a cell in which a cross has not yet been drawn and which has not yet been covered with a domino). Dima must cover two adjacent cells with a domino (which are not yet covered with other dominoes), in which there are an even number of crosses in total (0 or 2). The one who can't make a move loses. Which of does the player have a winning strategy, if
[list=a]
[*]Dima makes the first move?
[*]Kolya makes the first move?
[/list]
*
Solution
To analyze the problem of Kolya and Dima’s game on an board, we need to consider the implications of who makes the first move and how the rules affect the strategic outcomes:
### Game Dynamics
1. Game Setup:
- An board initially empty.
- Kolya's turn: place a cross in any empty cell.
- Dima’s turn: place a domino over two adjacent, empty cells with an even number of crosses (0 or 2).
2. Objective:
- The player who cannot make a valid move loses.
### Part (a): Dima starts
- Dima's First Move: Dima can only place a domino on two empty cells, starting with 0 crosses. He has 32 possibilities to place a domino since initially, no crosses are on the board.
- Strategy for Kolya: When Kolya makes the subsequent move, he adds a cross to any of the remaining empty cells.
- Continued Play: This pattern of alternating between Kolya placing a cross and Dima placing a domino continues, with Dima needing to find pairs of two empty cells after Kolya’s move. If strategized properly, Dima will eventually face a board such that after Kolya’s last move, no suitable double-cell configuration exists according to game rules.
- Conclusion: Since the board size results in exhaustion of pairs for domino placement and Kolya can always find a cell for a cross (while maintaining at least one legal move for himself until close to the board filling), Kolya will win if Dima starts.
### Part (b): Kolya starts
- Kolya's First Move: Kolya places a cross in any initial empty cell.
- Dima's Best Strategy: Dima places his domino over any pair of adjacent cells without crosses to maximize control over early moves and reduce Kolya's flexibility.
- Continued Play: The strategic alternations mean that Dima can leave Kolya to make a move that eventually prevents Kolya from placing a cross legally, due to scenario limitations where domino moves finish before cross moves.
- Conclusion: With strategic domino placements, Dima pressures Kolya into a position where no more legal crosses can be placed efficiently before board configurations lock Kolya out. Dima will win if Kolya starts.
Thus, we conclude:
-
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.