Maths Olympiad Prep

Library / /73 of 73

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Brazil

Arnold and Bernold play the following game in a m×nm \times n board: Arnold chooses one of its cells and places a knight on it. Then Bernold and Arnold move the knight alternately, with the condition that the knight visits a cell at most once. The player who is unable to move the knight loses. Determine, in terms of mm and nn, which player has the winning strategy.

Remark: the knight always moves two cells in a row or a column and then one cell in the perpendicular direction.

Solution

Suppose, without loss of generality, mnm \le n. If m=2m = 2, Arnold has winning strategy if and only if nn is not a multiple of 44; for m3m \ge 3, Arnold has winning strategy if and only if mm and nn are both odd.

Suppose m=2m = 2. If 44 does not divide nn, Arnold can win placing the knight on the first column if n=4k+1n = 4k + 1 and on the second column if n=4k+rn = 4k + r, r=2r = 2 or r=3r = 3. The knight should always be moved two columns ahead on each move, allowing exactly 2k2k moves.
Now consider n=4kn = 4k. Divide the table into 2×42 \times 4 subtables, and pair the cells in such a way that it's always possible to move the knight between cells from each pair:

1234
3412

Since the whole table is divided into pairs, Bernold can always move, no matter where Arnold places the knight: it suffices to move the knight to the other cell in the pair. When Arnold plays, he will move the knight to a cell from another pair, and Bernold can repeat this strategy. So if n=4kn = 4k Bernold has winning strategy.
This finishes the case m=2m = 2. The case m3m \ge 3 follows in a similar fashion, dividing the table into smaller subtables:
1234
3615
2546
123456
341789
278965
123
4A1
234
12345
346A7
21756

Those tables prove that Bernold has winning strategy for tables 3×n3 \times n, nn even and Arnold has winning strategy for tables 3×n3 \times n, nn odd: divide the table into one 3×33 \times 3 or 3×53 \times 5 subtable and several 3×43 \times 4 subtables; it suffices to place the knight on the cell marked with an AA and then use the aforementioned Bernold's strategy.
The case m=4m = 4 can be verified using several 4×24 \times 2 subtables if nn is even and one 4×34 \times 3 subtable and several 4×24 \times 2 subtables if nn is odd. This also proves that if either Arnold or Bernold has winning strategy for a m×nm \times n table then he also has winning strategy for a (m+4)×n(m+4) \times n table, m3m \ge 3. So it suffices to solve the problem for m{3,4,5,6}m \in \{3, 4, 5, 6\}.
The case m=5m = 5 can be solved using the following subtables:
123456
341789
21011965
1213141578
101112131415
12345
34567
211089
11A1276
12101198

Notice that Bernold has winning strategy for a 5×45 \times 4 table and Arnold has winning strategy for a 5×35 \times 3 table. Thus, in the case 5×n5 \times n, nn even, we merge 5×45 \times 4 subtables if nn is a multiple of 44 and one 5×65 \times 6 subtable and 5×45 \times 4 subtables if n=4k+2n = 4k + 2; if nn is odd, we merge several 5×45 \times 4 subtables to a 5×35 \times 3 or 5×55 \times 5 subtable, if n=4k+3n = 4k + 3 or n=4k+1n = 4k + 1, respectively.
The case 6×n6 \times n follows directly from the case 3×n3 \times n if nn is even (merge two 3×n3 \times n tables) and merging 6×46 \times 4 subtables to a 6×36 \times 3 or 6×56 \times 5 subtable, if n=4k+3n = 4k + 3 or n=4k+1n = 4k + 1, respectively. All the cases are covered.

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.