Maths Olympiad Prep

Library / /47 of 63

Combinatorics Difficulty 7.5 National olympiad, round 2 Prove it Japan

Let n>1n > 1 be an integer. Alice and Bob play the following game using an n×2021n \times 2021 grid. First, Alice colors each square either black or white. Bob places a piece in one of the squares in the top row and designates one square in the bottom row as the goal. Then, Alice repeatedly does the following operation n1n-1 times:
> If the piece is on a white square, she moves the piece to the square one below.
> Otherwise, she moves the piece to one left or right and then to one below.

Find the minimum possible value of nn such that Alice can always move the piece to the goal regardless of Bob's choice.

Solution

The answer is n=2022n = 2022.

First, we will prove that n2022n \ge 2022. We denote the square in the ithi^{\text{th}} row and the jthj^{\text{th}} column as (i,j)(i, j). When the piece in (i,j)(i, j) is moved to (i,j)(i', j') in a single operation, it holds that i=i+1i' = i+1 and jj1|j' - j| \le 1. Thus, in order to move the piece from (a,b)(a, b) to (c,d)(c, d) in some operations, it requires that aca \le c and dbca|d - b| \le c - a. If Bob places the piece in (1,1)(1, 1) and designates (n,2021)(n, 2021) as the goal, then 20211n1|2021 - 1| \le n - 1 yields n2021n \ge 2021.

For n=2021n = 2021, if Bob places the piece in (1,1)(1, 1) and designates (2021,2021)(2021, 2021) as the goal, then Alice has to move the piece from (k,k)(k, k) to (k+1,k+1)(k+1, k+1) for any 1k20201 \le k \le 2020. Hence she has to color any (k,k)(k, k) black. In this situation, we can show that she cannot move the piece from (1,1)(1, 1) to (k+1,k)(k+1, k) for any 1k20201 \le k \le 2020, and specifically to (2021,2020)(2021, 2020), which yields n2022n \ge 2022. The proof follows from induction on kk. For k=1k = 1 this claim holds since (1,1)(1, 1) is colored black. For k2k \ge 2, note that she can move the piece to (k+1,k)(k+1, k) only from (k,k1)(k, k-1), (k,k)(k, k), or (k,k+1)(k, k+1). Here, as (k+1)1>k1|(k+1) - 1| > k - 1, she cannot move from (1,1)(1, 1) to (k,k+1)(k, k+1). Also, she cannot move to (k,k1)(k, k-1) by the induction hypothesis. Additionally, as (k,k)(k, k) is colored black, she cannot move from that square to (k+1,k)(k+1, k).

Conversely, we will prove that Alice can move the piece to the goal when n=2022n = 2022. First, she colors the squares (i,j)(i, j) with i4i \ge 4 black. Then, for any odd integers a,ba, b with 3a20193 \le a \le 2019 and 1b20211 \le b \le 2021, she can move the piece from (4,a)(4, a) to (2022,b)(2022, b). Similarly, for any even integers a,ba, b with 2a,b20222 \le a, b \le 2022, she can move the piece from (4,a)(4, a) to (2022,b)(2022, b).

Next, for the squares (i,j)(i, j) with 1i31 \le i \le 3, she colors the following form of squares black for any kk with 0k3360 \le k \le 336:
(1,3k+1),(1,20213k),(1,3k+3),(1,20193k),(2,3k+2),(2,20203k),(3,3k+1),(3,20213k) (1, 3k + 1), (1, 2021 - 3k), (1, 3k + 3), (1, 2019 - 3k), (2, 3k + 2), (2, 2020 - 3k), (3, 3k + 1), (3, 2021 - 3k)

And she colors the remaining squares white. Note that for k=336k = 336, (1,3k+3)(1, 3k+3) and (1,20193k)(1, 2019-3k) are the same squares. In this situation, we prove that Alice can move the piece to the goal. From the symmetry of this coloring, we only need to prove that she can move from (1,a)(1, a) with 1a10111 \le a \le 1011 to any squares in the bottom row. For kk with 0k3360 \le k \le 336, she can move from (1,3k+1)(1, 3k+1), (1,3k+2)(1, 3k+2), or (1,3k+3)(1, 3k+3) to (2,3k+2)(2, 3k+2), then through (3,3k+1)(3, 3k+1) or (3,3k+3)(3, 3k+3), she can move to (4,3k+2)(4, 3k+2) or (4,3k+3)(4, 3k+3). Hence, she can move from (1,a)(1, a) to any squares in the bottom row. 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 and solution reproduced as published; topic and difficulty added by this site.