2011 IMO SL #C5

-
Let $m$ be a positive integer, and consider a $m\times m$ checkerboard consisting of unit squares. At the centre of some of these unit squares there is an ant. At time $0$, each ant starts moving with speed $1$ parallel to some edge of the checkerboard. When two ants moving in the opposite directions meet, they both turn $90^{\circ}$ clockwise and continue moving with speed $1$. When more than $2$ ants meet, or when two ants moving in perpendicular directions meet, the ants continue moving in the same direction as before they met. When an ant reaches one of the edges of the checkerboard, it falls off and will not re-appear. 

Considering all possible starting positions, determine the latest possible moment at which the last ant falls off the checkerboard, or prove that such a moment does not necessarily exist.


The answer is \(\boxed{\frac32m-1}\).

If we place the situation on a coordinate system with the vertices of the board \(W=(0,0)\), \(X=(m,0)\), \(Y=(m,m)\), \(Z=(0,m)\), a working construction is to place an ant at \((\frac12,\frac12)\) moving right and an ant at \((m-\frac12,\frac12)\) moving left. 

Modify the given rules, and now the ants always move either right and up or down and left. Note that the resulting operation is not affected. 

Consider the ant \(a\) that falls off last; let its starting position be \(A_0\), assume without loss of generality it falls off the top edge \(YZ\) at \(A^*\), and let it collide with another ant for the last time at point \(A\). 

Place a bug on \(A\), and let \(b_1\) be the ant that collides with \(a\) at \(A=:B_0\). Let the bug first move right, as it is following \(b_1\)'s path backwards. For every \(i\ge1\), let \(b_i\)'s latest collision before reaching \(B_{i-1}\) be \(B_i\), and let the bug that collides with \(b_i\) at \(B_i\) be bug \(b_{i+1}\). When the bug will reach \(B_i\), we will let it move backwards along the path \(b_{i+1}\) is following. Then, it reaches some ant's starting position \(B_k\); ant \(b_k\)'s first collision occurs at \(B_{k-1}\). 

From this point on, all lengths are total taxicab distances. Let \(t:=AA^*\) be the time when \(a\) is not on the board anymore and let \(s:=AA_0\) be the time when \(a\) reaches \(A\). So, we have \(AA^*=t-s\). Notice that the bugs \(b_i\) and \(b_{i+1}\) always meet at \(B_i\) at the same moment. Hence, if \(AB_i=d\), then both \(b_i\) and \(b_{i+1}\) arrive at \(B_i\) at the time \(s-d\). Furthermore, we have \(AB_k=s\), and therefore \(A^*B_k=t\).

From \(WA_0\ge1\) and \(XB_k\ge1\), note \(WA^*\ge t+1\) and \(XA^*\ge t+1\). But for each point \(A^*\in\) \(\overline{YZ}\) we know \(WA^*+XA^*=3m\), and thus \(\min\{WA^*,XA^*\}\le\frac32m\). 

Finally, the desired \(t\le\frac32m-1\) then follows. $\square$



Comments

Post a Comment

Popular posts from this blog

1995 IMO #2

-
 Let $ a$, $ b$, $ c$ be positive real numbers such that $ abc = 1$. Prove that \[ \frac {1}{a^{3}\left(b + c\right)} + \frac {1}{b^{3}\left(c + a\right)} + \frac {1}{c^{3}\left(a + b\right)}\geq \frac {3}{2}. \]
Read more

2014 IMO SL #C2

-
  Problem : We have $2^m$ sheets of paper, with the number $1$ written on each of them. We perform the following operation. In every step we choose two distinct sheets; if the numbers on the two sheets are $a$ and $b$, then we erase these numbers and write the number $a + b$ on both sheets. Prove that after $m2^{m -1}$ steps, the sum of the numbers on all the sheets is at least $4^m$ .
Read more

2015 IMO SL #A1

-
 Suppose that a sequence $a_1,a_2,\ldots$ of positive real numbers satisfies\[a_{k+1}\geq\frac{ka_k}{a_k^2+(k-1)}\]for every positive integer $k$. Prove that $a_1+a_2+\ldots+a_n\geq n$ for every $n\geq2$.
Read more