Maths Olympiad Prep

Library / /10 of 24

Combinatorics Difficulty 8.3 Shortlist Prove it Romania

Turbo the snail is in the lower left cell of an n×nn \times n array, n2n \ge 2, and aims to reach the upper right cell by moving one cell rightwards or one cell upwards. Some cells contain monsters, visible to Turbo, and they must be avoided. Assume there is a unique way for Turbo to achieve his goal. In terms of nn, determine the smallest possible number of monsters such an array may contain. (The minimum is over all configurations satisfying the unique path condition.)

Solution

Let (i,j)(i, j) denote the cell on the ii-th row and the jj-th column, where (1,1)(1, 1) is the lower left cell. The required minimum is n1n-1 and is achieved by placing the monsters in the cells (k,nk+1),k=2,,n(k, n-k+1), k=2, \dots, n, to force Turbo move rightwards from (1,1)(1, 1) to (1,n)(1, n) and thence upwards to (n,n)(n, n).

To prove that the n×nn \times n array must contain at least n1n-1 monsters, induct on nn. The base case, n=2n=2, is trivial.

For the inductive step, let n3n \ge 3. If necessary, switch rows and columns to assume that Turbo first moves upwards to (2,1)(2, 1). Note that Turbo enters (n,n)(n, n) either from (n,n1)(n, n-1) or from (n1,n)(n-1, n).

Case 1. Turbo visits (n,n1)(n, n-1). Consider the subarray {(i,j):2in,1jn1}\{(i, j) : 2 \le i \le n, 1 \le j \le n-1\}. As it inherits uniqueness of a safe path for Turbo, it contains at least n2n-2 monsters, by the induction hypothesis. Furthermore, the path from (1,1)(1, 1) to (n,n)(n, n) lying outside the subarray must contain at least one monster, for otherwise it would have offered an alternative to Turbo, contradicting uniqueness. Consequently, the n×nn \times n array contains at least (n2)+1=n1(n-2)+1 = n-1 monsters, as desired. This establishes Case 1.

Case 2. Turbo visits (n1,n)(n-1, n). Note that (2,1)(2, 1) and (n1,n)(n-1, n) are separated by the diagonal joining the lower left cell to the upper right cell, so Turbo's safe path must cross this diagonal at some (unique) cell (k,k)(k, k), where 2kn12 \le k \le n-1.

Consider the subarrays {(i,j):1i,jk}\{(i, j) : 1 \le i, j \le k\} and {(i,j):ki,jn}\{(i, j) : k \le i, j \le n\}. They both inherit uniqueness of a safe path for Turbo, so the former contains at least k1k-1 monsters and the latter at least nkn-k, accounting for at least (k1)+(nk)=n1(k-1)+(n-k) = n-1 monsters in the n×nn \times n array, as desired. This establishes Case 2 and completes the solution.

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.