NZMO Round One

Combinatorics Difficulty 7.0 National Olympiad, round 2 Prove it New Zealand

Problem:

Josie and Ross are playing a $20 \times 20$ chessboard game. Initially the chessboard is empty. The two players alternately take turns, with Josie going first. On Josie's turn, she selects any two different empty cells, and places one white stone in each of them. On Ross' turn, he chooses any one white stone currently on the board, and replaces it with a black stone. If at any time there are 8 consecutive cells in a line (horizontally or vertically) all of which contain a white stone, Josie wins. Is it possible that Ross can stop Josie winning — regardless of how Josie plays?

Solution

Solution:

Ross can't stop Josie winning — Josie has a strategy in which she can ensure that there will be 8 white stones in a row. We will give an explicit example of such a strategy.

To simplify notation, we define a $k$ -strip to be a $1 \times 8$ rectangle, in which the first $k$ cells are filled with white stones and the other $8 - k$ cells are empty.

- Step One. Josie creates 32 disjoint 1-strips using the following technique.

Start by finding 44 disjoint $1 \times 9$ rectangles on the board.

- Josie places a white stone in one end of each of these 44 rectangles on her first 22 turns.
- Ross "ruins" 22 of them. Each of the other 22 rectangles are 1-strips (by ignoring the empty end cell).
- On Josie's next 10 turns she then chooses 20 of the ruined $1 \times 9$ rectangles, and "unruins" them by placing a white stone in the other end. These are now 1-strips (by ignoring the cell containing the black stone).
- However Ross "ruins" a further 10 of them. So in total we have
$22 + 20 - 10 = 32 \text{ disjoint 1-strips.}$

- Step Two. Repeat the following operation for $k = 1, 2, 3, 4, 5$ .

Starting with $2^{6 - k}$ disjoint $k$ -strips. Josie can use her next $2^{5 - k}$ turns to add one white stone to each of these strips. On Ross' next $2^{5 - k}$ turns he can spoil at most $2^{5 - k}$ of them. So we are left with at least $2^{5 - k}$ disjoint $(k + 1)$ -strips.

- Step Three. Now we have at least one 6-strip. Josie wins immediately by placing both her white stones into the empty cells in the 6-strip.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.