Kvant

Combinatorics Difficulty 6.8 National Olympiad Find the answer

Kolya and Dima play a game on an $8\times 8$ 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

- Dima makes the first move?

- Kolya makes the first move?

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To analyze the problem of Kolya and Dima’s game on an $8 \times 8$ 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 $8 \times 8$ 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:

- $\boxed{\text{Kolya wins if Dima starts, and Dima wins if Kolya starts.}}$

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.