Maths Olympiad Prep

Library / /378 of 397

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it Taiwan

Consider a 2013×20132013 \times 2013 chessboard, whose grid lines run in the north-south/east-west directions. In each unit square is filled an arrow pointing either east or south. Each minute, for every arrow AA, if AA points to an adjacent square, and the arrow BB in that square has a direction different from AA, then in the next minute AA is changed to the arrow of the other direction (if AA originally pointed south then it changes to pointing east, and if AA originally pointed east then it changes to pointing south); otherwise the arrow AA does not move. All such transformations are performed simultaneously every minute.

Prove that after finite time, none of the arrows can change direction anymore. Also find the longest possible time during which at least one arrow can still change direction.

Solution

本題的答案是最多在前 40244024 分鐘內可以有箭頭方向變換產生。

我們首先證明:自第 40254025 分鐘起, 所有箭頭的方向都固定下來, 不再產生變換。

The answer to this problem is that arrow direction changes can occur for at most the first 40244024 minutes.

We first prove: starting from minute 40254025, the directions of all arrows are fixed and no more changes occur.

Set up a coordinate system on the chessboard: each square has coordinates (i,j)(i, j), where 0i,j20120 \le i, j \le 2012, and the square (0,0)(0, 0) is at the southeast corner of the chessboard. We claim: if x+y<mx + y < m, then the arrow in square (x,y)(x, y) will no longer change direction from minute mm onward.

We use mathematical induction on mm. The case m=1m = 1 holds automatically, because the arrow in square (0,0)(0, 0) does not point to any other square.

Now assume the statement holds for a positive integer mm, that is, as long as x+y<mx + y < m, the arrow in square (x,y)(x, y) no longer changes direction from minute mm onward. If the statement does not hold for m+1m + 1, then there exists a square (x,y)(x, y) with x+y<m+1x + y < m + 1, such that the arrow AA in this square changes direction at minute MM, with Mm+1M \ge m + 1. That is, at minute M1M - 1, arrow AA points to an arrow BB with a different direction from itself. The square containing arrow BB has coordinates (x,y)(x', y'), where x+y=x+y1<mx' + y' = x + y - 1 < m. By the induction hypothesis, arrow BB no longer changes direction from minute mm onward. Also, since AA and BB point in different directions, we know that arrow BB points to square (x1,y1)(x - 1, y - 1). Therefore arrow AA cannot have pointed to arrow BB before minute M1mM - 1 \ge m,

otherwise AA would have had to change direction before minute M1M-1. Therefore arrow AA also had to change direction at minute M1M-1.

Suppose arrow AA pointed to another arrow CC before minute M1M-1. Again, the square containing CC has coordinates (x,y)(x'', y''), where x+y=x+y1<mx'' + y'' = x + y - 1 < m. Then by the induction hypothesis again, arrow CC also does not change direction from minute mm onward, and it also points to square (x1,y1)(x-1, y-1).

But the above phenomenon cannot occur, because before minute mm, both arrows BB and CC point simultaneously to an arrow DD in square (x1,y1)(x-1, y-1), and B,CB, C have different directions. Therefore at minute mm, one of them differs in direction from arrow DD and hence must change direction.

This completes the induction step. Since every square's coordinates (x,y)(x, y) satisfy x+y4024<4025x+y \le 4024 < 4025, no arrow will change direction from minute 40254025 onward.

Figure 1

Using the coordinate system described above, the bottommost row of squares, from east to west, has coordinates from (0,0)(0,0) to (2012,0)(2012,0). In the figure above, only the arrows in squares with coordinates (x,0)(x,0) point east (0x2012)(0 \le x \le 2012), while the arrows in all other squares point south.

First observe that: the arrow in square (0,y)(0,y) (0y2012)(0 \le y \le 2012) always points south.

Let us first look at what happens during the first 20122012 minutes: let 0m20120 \le m \le 2012. After mm minutes, the arrow in square (x,y)(x,y) points east, where 1x20121 \le x \le 2012, y=my=m. But for every square (x,y)(x, y) with 1xm20121 \le x \le m \le 2012, y>my > m, the arrow in that square points south. So at minute mm, every arrow in square (x,m)(x, m) (1x20121 \le x \le 2012) will be changed to point south. Therefore, after 20122012 minutes, in the northernmost row, only the arrow in square (0,2012)(0, 2012) points south, while the arrows in all other squares (x,2012)(x, 2012) (where 1x20121 \le x \le 2012) point east.

Next, after 2012+m2012 + m minutes (0m2012)(0 \le m \le 2012), the arrow in square (x,2012)(x, 2012) points east if m+1x2012m + 1 \le x \le 2012, but the arrow in square (m,2012)(m, 2012) points south. Therefore at minute 2012+m2012 + m (where 1m20121 \le m \le 2012), the arrow in square (m,2012)(m, 2012) will change from pointing east to pointing south. So, summing up the above, during the first 40244024 minutes there are arrows changing direction.

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.