Maths Olympiad Prep

Library / /324 of 397

Combinatorics Difficulty 6.7 National Olympiad Prove it Taiwan

A and B play a game on a Cartesian coordinate plane. At the start, A first chooses a position (x0,y0)(x_0, y_0) to place the first piece. Then, starting with B, A and B take turns placing pieces:

i) If the piece A placed in the previous turn is located at coordinates (x,y)(x, y), then B can only place the next piece at one of the coordinates (x+2,y+1)(x + 2, y + 1), (x+2,y1)(x + 2, y - 1), (x2,y+1)(x - 2, y + 1), (x2,y1)(x - 2, y - 1).

ii) If the piece B placed in the previous turn is located at coordinates (x,y)(x, y), then A can only place the next piece at one of the coordinates (x+1,y+2)(x + 1, y + 2), (x+1,y2)(x + 1, y - 2), (x1,y+2)(x - 1, y + 2), (x1,y2)(x - 1, y - 2).

In addition, if ac(modn)a \equiv c \pmod{n}, bd(modn)b \equiv d \pmod{n}, and there is already a piece at coordinates (a,b)(a, b), then neither player may place a piece at coordinates (c,d)(c, d). The first person who cannot place a piece anywhere loses.

(1) When n=2018n = 2018, who has a winning strategy?
(2) When n=2019n = 2019, who has a winning strategy?

Solution

When n=2018n = 2018, B has a winning strategy; when n=2019n = 2019, A has a winning strategy.

First, consider an n×nn \times n board where the top and bottom of the board are connected, and the left and right are connected. Since for all 1a,bn1 \le a, b \le n, only one piece can be placed among {(nx+a,ny+b)x,yZ}\{(nx + a, ny + b) \mid x, y \in \mathbb{Z}\}, we can replace the coordinate plane with such a board, where the cell (a,b)(a, b) of the board represents the set of points {(nx+a,ny+b)x,yZ}\{(nx + a, ny + b) \mid x, y \in \mathbb{Z}\} in the coordinate plane.

(We adopt the convention that the rows of the board are numbered from 11 to nn from bottom to top, and the columns are numbered from 11 to nn from left to right)

(1) First we prove that when nn is even, BB has a winning strategy.

Pair up all the cells of the n×nn \times n board: cell (a,2t)(a, 2t) is paired with cell (a+2,2t+1)(a + 2, 2t + 1) (here the addition and subtraction of coordinates are all taken (mod n)(\bmod\ n)). If, whenever AA places a piece, BB places a piece at the cell paired with the cell where that piece was placed, then AA's piece each time lies in a new pair, and BB's piece completes that pair, so BB always has a place to move, and hence BB has a winning strategy.

(2) Next we prove that when nn is odd, AA has a winning strategy. Let n=2k+1n = 2k + 1, and define the following sets:

i) When 2k2 \mid k, let S={4r+1,4r+20r<k2}S = \{4r + 1, 4r + 2 \mid 0 \le r < \frac{k}{2}\}, T={4r+3,4r+40r<k2}T = \{4r + 3, 4r + 4 \mid 0 \le r < \frac{k}{2}\}

ii) When 22 does not divide kk, let S={4r+2,4r+30r<k12}{2k}S = \{4r + 2, 4r + 3 \mid 0 \le r < \frac{k-1}{2}\} \cup \{2k\}, T={4r+4,4r+50r<k12}{1}T = \{4r + 4, 4r + 5 \mid 0 \le r < \frac{k-1}{2}\} \cup \{1\}

It is not hard to see that STS \cup T contains exactly all the integers from 11 to 2k2k, and that TT is the set formed by adding 22 to every number in SS.

Now, pair up the cells of the n×nn \times n board: for 1an1 \le a \le n, if aa is odd, pair the cell (a,b):bS(a, b): b \in S with the cell (a+1,b+2)(a + 1, b + 2); if aa is even, pair the cell (a,b):bT(a, b): b \notin T with the cell (a+1,b2)(a + 1, b - 2). From the relationship between SS and TT described above, we see that all cells except (1,n)(1, n) are exactly paired up one by one. Therefore AA has the following strategy: first place a piece at cell (1,n)(1, n), and whenever BB places a piece, AA places a piece at the cell paired with the cell where that piece was placed. It is not hard to see that this is a winning strategy for AA. This completes the proof.

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 translated into English from zh; metadata (topic, difficulty) added by this project.