Taiwan IMO Selection Camp

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

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

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

We first prove: starting from minute $4025$, 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)$, where $0 \le i, j \le 2012$, and the square $(0, 0)$ is at the southeast corner of the chessboard. We claim: if $x + y < m$, then the arrow in square $(x, y)$ will no longer change direction from minute $m$ onward.

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

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

otherwise $A$ would have had to change direction before minute $M-1$. Therefore arrow $A$ also had to change direction at minute $M-1$.

Suppose arrow $A$ pointed to another arrow $C$ before minute $M-1$. Again, the square containing $C$ has coordinates $(x'', y'')$, where $x'' + y'' = x + y - 1 < m$. Then by the induction hypothesis again, arrow $C$ also does not change direction from minute $m$ onward, and it also points to square $(x-1, y-1)$.

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

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

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

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

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

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