Maths Olympiad Prep

Library / /52 of 52

Geometry Difficulty 7.7 National olympiad, round 2 Prove it Belarus

At each node of the checkered n×nn \times n board sat a beetle. At midnight, each beetle crawled into the center of a cell. It turned out that the distance between any two beetles sitting in the adjacent (along the side) nodes did not increase.
Prove that at least one beetle crawled into the center of a cell at the vertex of which it sat initially.
(A. Voidelevich)

Solution

First solution. We will prove the statement of the problem in the general case of rectangular boards n×mn \times m. Suppose in contrary that there exist such positive integers nn and mm and a movement of beetles, that none of the beetles crawled into the center of the cell at the vertex of which it initially sat. Take such a pair (n,m)(n, m) with minimal n+mn+m. Clearly, for 1×11 \times 1 board the statement of the problem is true, so without loss of generality assume that n2n \ge 2.

Enumerate the columns from left to right by numbers 1,,m1, \dots, m and the vertical gridlines by numbers 0,,m0, \dots, m. Similarly, enumerate the rows from top to bottom by numbers 1,,n1, \dots, n and the horizontal gridlines by numbers 0,,n0, \dots, n. So, (i,j)(i, j)-cell have (i1,j1),(i1,j),(i,j)(i-1, j-1), (i-1, j), (i, j) and (i,j1)(i, j-1) vertices.

Suppose that for some ii, 1im11 \le i \le m-1, the beetle crawled from (2,i1)(2, i-1)-node to the center of (1,i)(1, i)-cell. Then the beetle from (1,i1)(1, i-1)-node couldn't move to the centers of (1,i1)(1, i-1) and (2,i)(2, i) cells, so it crawled to the center of (1,i+1)(1, i+1)-cell. Hence the beetle from (1,i)(1, i)-node crawled to the center of (1,i+2)(1, i+2)-node. Similarly, the beetle from the (1,j)(1, j)-node, i<j<m1i < j < m-1, crawled to the center of (1,j+2)(1, j+2)-cell. Finally, for the beetle from (1,m1)(1, m-1)-node we obtain a contradiction, since it had to move to the center of the cell, adjacent to (1,m)(1, m)-cell: either (1,m1)(1, m-1)-cell or (2,m)(2, m)-cell, both having (1,m1)(1, m-1)-node as a vertex. If we now suppose that the beetle from (2,i1)(2, i-1)-node, 2im2 \le i \le m, moved to the center of (1,i1)(1, i-1)-cell, we obtain a contradiction in a similar way.

Consider the next transformation of the n×mn \times m board. Remove the first row and all beetles from the top (0-th) gridline. For each of the remaining beetles, which crawled to the first row, let it now crawl one row below. And for the rest of the beetles don't change anything. It is easy to see that after transformation we obtain a counterexample on to the statement of the problem on the (n1,m)(n-1, m) board. But this contradicts the minimality of n+mn+m. Therefore, our assumption of the existence of a counterexample is false.

Second solution. By a distance between a beetle and a cell call the minimal number of unit moves along the gridlines, which this beetle require to get to the vertex of the cell. The distance between the beetle K\mathfrak{K} and the cell CKC^{\mathfrak{K}}, at which it crawled, call its path.

We are to prove that there exists a beetle with zero path. Suppose a contrary and choose the beetle K1\mathfrak{K}_1 with minimal path. The gridlines, passing through the starting vertex of K1\mathfrak{K}_1 divide the board into four rectangles. Without loss of generality let CK1C^{\mathfrak{K}_1} lie in the top right rectangle. Since the path of K1\mathfrak{K}_1 is positive, we may assume that CK1C^{\mathfrak{K}_1} is not located on the left border of the rectangle.

Consider the beetle K2\mathfrak{K}_2, which sat to the right of K1\mathfrak{K}_1. It crawled to CK1C^{\mathfrak{K}_1} or to the adjacent to it. But the distance between K2\mathfrak{K}_2 and CK1C^{\mathfrak{K}_1} is less than the path of K1\mathfrak{K}_1, and the same hold for the left and bottom adjacent cells of CK1C^{\mathfrak{K}_1}. Hence CK2C^{\mathfrak{K}_2} is located to the right or top of CK1C^{\mathfrak{K}_1} and the next condition hold: (1) the path of K2\mathfrak{K}_2 equals to the path of K1\mathfrak{K}_1, i.e. it is minimal; and (2) CK2C^{\mathfrak{K}_2} lies in the top right rectangle, with respect to K2\mathfrak{K}_2.

Replacing the beetle K1\mathfrak{K}_1 with K2\mathfrak{K}_2 we find the beetle K3\mathfrak{K}_3 satisfying the conditions (1) and (2). Continue this considerations, we obtain the sequence of beetles, each satisfying (1) and (2), such that the distance from the beetles to the top right cell of the board is decreasing at each step. It is evident that at some moment we get a contradiction.

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.