Maths Olympiad Prep

Library / /37 of 41

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

Problem:

Josie and Ross are playing a 20×2020 \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 kk-strip to be a 1×81 \times 8 rectangle, in which the first kk cells are filled with white stones and the other 8k8 - k cells are empty.

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

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

Figure 1

- 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×91 \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+2010=32 disjoint 1-strips.22 + 20 - 10 = 32 \text{ disjoint 1-strips.}

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

Starting with 26k2^{6 - k} disjoint kk-strips. Josie can use her next 25k2^{5 - k} turns to add one white stone to each of these strips. On Ross' next 25k2^{5 - k} turns he can spoil at most 25k2^{5 - k} of them. So we are left with at least 25k2^{5 - k} disjoint (k+1)(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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.