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. Proposed by Toomas Krips, Estonia
Problem
Source: IMO Shortlist 2011, Combinatorics 5
Tags: combinatorics, IMO Shortlist, algorithm, Hi
12.07.2012 16:27
Here's what I call the "triangles of death" solution, named after the initial shape of the forbidden regions that expand to fill the whole board. Let the top left of the board be $(0,0)$ and let the bottom right of the board be $(m,m)$. The answer is $\frac{3m}{2} - 1$. To obtain this, place two ants on $(\frac 12, \frac 12)$, $(m - \frac 12, \frac 12)$ moving down, and similarly place two ants on $(\frac 12, m - \frac 12)$, $(m - \frac 12, m - \frac 12)$ moving up. After two pairs of ants meet at $(\frac 12, \frac m2)$ and $(m - \frac 12, \frac m2)$, the two that turn toward the center of the board will meet at $(\frac m2, \frac m2)$. These two ants will take time $\frac{3m}{2} - 1$ to fall off. Call an ant moving right or down positive, and call other ants negative. Note that a positive ant has sum of coordinates increasing and a negative ant has sum of coordinates decreasing. Consider an alternate set of rules in which instead of the two ants turning $90^\circ$ clockwise when they meet, the positive ant stays positive and the negative ant stays negative. So a positive ant has his sum of coordinates increase by one for every unit of time. All positive ants start with sum of coordinates at least one, so after time $t$ they all have sum of coordinates at least $t+1$. Similarly, all negative ants start with sum of coordinates at most $2m-1$, so at time $t$ they all have sum of coordinates at most $2m-1-t$. But the ants do not behave any differently between this new set of rules and the original, so this is also true for the original problem's rules. We can similarly define an ant to be $x$-leaning if he is moving right or up, and $y$-leaning otherwise. By considering an alternate set of rules in which $x$-leaning ants stay $x$-leaning and vice versa, we have that $x$-leaning ants always have their $x$-coordinate minus their $y$-coordinate increasing by one each time unit, and similarly for $y$-leaning ants. After time $t$, all $x$-leaning ants on $(a,b)$ are such that $a - b \geq t - m - 1$. Similarly, all $y$-leaning ants on $(a,b)$ are such that $b - a \geq t - m - 1$. This is true for the original problem's rules as well. Now consider the situation after time $\frac{3m}{2}-1$. We claim all the ants have fallen off. Suppose an ant $(a,b)$ is still on. If $\frac m2 \leq a+b \leq \frac{3m}{2}$, then the ant can neither be positive nor negative, which means he can't be moving at all, contradiction. If this inequality is not true, then either $a,b$ are both at most $\frac{m}{2}$ or $a,b$ are both at least $\frac{m}{2}$. Either way, $|a-b| \leq \frac{m}{2}$. But this implies that at this point in time the ant can be neither $x$-leaning or $y$-leaning, so he can't be moving at all either. As a result, there is nowhere on the board that can still have an ant, so $\frac{3m}{2} - 1$ is the last possible time that an ant can remain on the board.
13.07.2012 00:53
Hm, I named the region "forbidden region". How unoriginal The following proof is rather similar to the official solution. To make things easier, let a unit of length be 2 subunits of length and a unit of time be 2 subunits of time (stuffs become integers now). Also define time $x$ as the moment that $x$ subunits have elapsed. Make new lines dividing each row/column of squares into two identical rows/columns. The ants will then only travel along the gridlines, and will meet only at grid intersections. Redefine meeting as two ants meeting head-on (two ants meeting perpendicularly don't count, and also more than two ants meeting). I claim that it takes $3m - 2$ subunits of time for all ants to fall off. Construction is precisely as MellowMelon's, but in my mock IMO I rotate it by 90 degrees (2 leftward ants and 2 rightward ants). Although we actually only need two ants to reach the bound; an ant on the lower-left corner heading right and an ant on the lower-right corner heading left. So, while MellowMelon didn't construct the triangle of death, I construct the forbidden region in my proof. Put a coordinate system on the board; set the lower-left vertex of the board is $(0,0)$, lower-right vertex of the board is $(2m,0)$, and upper-left vertex of the board is $(0,2m)$. Let $A_i$ be the set of lattice points inside the board (not on the edge) that have Manhattan distance of at most $i+1$ with $(0,0)$; aka the set of $(x,y)$ where $x,y \in \mathbb{Z}^+$ and $x+y \le i+1$. I claim there can be no meetings in $A_i$ at time $i$. Suppose there is a meeting; I'll prove that it leads to contradiction. If $i = 1$, then the meeting must take place on $(1,1)$ as it's the only point in $A_1$. But then one of the ants in the meeting must come from $(0,1)$ or $(1,0)$, impossible. Suppose for all $i \le k$, the claim is true. I'll prove that for $i = k+1$, the claim stands. Suppose there is a meeting in some point $(x,y) \in A_{k+1}$ at time $k+1$. One of the ants involved in the meeting must be in $(x_0, y_0)$ at time $k$ where $x_0 + y_0 = x + y - 1$ by the very definition of meeting; WLOG it came from $(x-1, y)$. But then $(x-1, y)$ is in $A_k$, so the ant cannot had a meeting at time $k$. Hence at time $k-1$ it must be from $(x-2, y)$. Induct this way, to get that the ant never had a meeting before and it came from $(x-k-1, y)$. But since $x + y \le k + 2$, then $x - k - 1 + y \le 1$, impossible to be the starting point of the ant (all possible places have $x + y \ge 2$). Now rotate the board to get the forbidden regions of each corner; an ant cannot have a meeting at time $t$ and place having Manhattan distance of less than or equal to $t + 1$ with any corner. Now for every ant, let $(x,y)$ be its last meeting at time $t$; WLOG it moves downward now. Then by considering $(2m,2m)$ and $(2m,0)$, we have: $(2m - x) + (2m - y) \ge t + 2$ $x + (2m - y) \ge t + 2$ Adding, we have: $6m - 2y \ge 2t + 4$ $y \le 3m - t - 2$ So the ant will fall within $3m - t - 2$ subunits of time. Since it has moved for $t$ subunits of time before, then it will fall of by time $3m - 2$, proving the claim. Yeah, rather complicated. But still rather intuitive except for thinking the idea of a forbidden region.
13.07.2012 10:02
Is my solution wrong because it seems a lot shorter? The condition that when 2 ants meet they rotate clockwise is unnecessarely you could just say that they arbitrarely go in different perpendicular directions(the times remaining unchanged. Let us say the table is ABCD and ant X dyes in side BC in point M WLOG $CM\le MB$ before ant X died on side BC she was going on a perpendicular direction to ,it if she changed direction (before going this way) there were 2 ants which intersected with there previous directions parallel to AD we can say that the time of ant X is the time of the ant going on upper direction + the segment from the intersection to the sides we obtain this way a left down road from X to an ant starting positon with this road equal to the time of X's death but this road is at most $ MC+CD \le m-\frac{1}{2}+\frac{m}{2}-\frac{1}{2}$ Edit: i forgot to mention that every ant dies but this is obvious by a left down alghoritm
Attachments:
13.07.2012 15:32
Oh ya forgot one part: All ants must fall. Let $x$ be the total of the distances in subunits of length of each ant before they fall. I claim $x$ is always decreasing, and as $x$ takes integer values at integer times, $x$ will eventually reach $0$. Indeed after one subunit of time, $x$ decreases by the number of ants. When a meeting takes place, the total distance stays the same since the sum of distances of both ants stays $2m$. EDIT: And I certainly don't understand paul1703's solution.
26.07.2012 11:56
I think we can prove this way: for every point with coordinates $(m/2,n/2)$ we can calculate last possible moment when it is possible that two ants moving in opposite directions meet in this point. Just apply induction. And then answer will be easy.
21.07.2013 10:40
MellowMelon wrote: Here's what I call the "triangles of death" solution, named after the initial shape of the forbidden regions that expand to fill the whole board. Let the top left of the board be $(0,0)$ and let the bottom right of the board be $(m,m)$. The answer is $\frac{3m}{2} - 1$. To obtain this, place two ants on $(\frac 12, \frac 12)$, $(m - \frac 12, \frac 12)$ moving down, and similarly place two ants on $(\frac 12, m - \frac 12)$, $(m - \frac 12, m - \frac 12)$ moving up. After two pairs of ants meet at $(\frac 12, \frac m2)$ and $(m - \frac 12, \frac m2)$, the two that turn toward the center of the board will meet at $(\frac m2, \frac m2)$. These two ants will take time $\frac{3m}{2} - 1$ to fall off. Call an ant moving right or down positive, and call other ants negative. Note that a positive ant has sum of coordinates increasing and a negative ant has sum of coordinates decreasing. Consider an alternate set of rules in which instead of the two ants turning $90^\circ$ clockwise when they meet, the positive ant stays positive and the negative ant stays negative. So a positive ant has his sum of coordinates increase by one for every unit of time. All positive ants start with sum of coordinates at least one, so after time $t$ they all have sum of coordinates at least $t+1$. Similarly, all negative ants start with sum of coordinates at most $2m-1$, so at time $t$ they all have sum of coordinates at most $2m-1-t$. But the ants do not behave any differently between this new set of rules and the original, so this is also true for the original problem's rules. We can similarly define an ant to be $x$-leaning if he is moving right or up, and $y$-leaning otherwise. By considering an alternate set of rules in which $x$-leaning ants stay $x$-leaning and vice versa, we have that $x$-leaning ants always have their $x$-coordinate minus their $y$-coordinate increasing by one each time unit, and similarly for $y$-leaning ants. After time $t$, all $x$-leaning ants on $(a,b)$ are such that $a - b \geq t - m - 1$. Similarly, all $y$-leaning ants on $(a,b)$ are such that $b - a \geq t - m - 1$. This is true for the original problem's rules as well. Now consider the situation after time $\frac{3m}{2}-1$. We claim all the ants have fallen off. Suppose an ant $(a,b)$ is still on. If $\frac m2 \leq a+b \leq \frac{3m}{2}$, then the ant can neither be positive nor negative, which means he can't be moving at all, contradiction. If this inequality is not true, then either $a,b$ are both at most $\frac{m}{2}$ or $a,b$ are both at least $\frac{m}{2}$. Either way, $|a-b| \leq \frac{m}{2}$. But this implies that at this point in time the ant can be neither $x$-leaning or $y$-leaning, so he can't be moving at all either. As a result, there is nowhere on the board that can still have an ant, so $\frac{3m}{2} - 1$ is the last possible time that an ant can remain on the board. So i have a question. i may couldn't understand the condition well, so does the ant move only to one direction except the case when it meets another ant? also when you've written x-leaning ants which go up or right, how is it possible, when positive ants stay positive, which means that an ant which goes down and has the collision there forces it to go anticlockwise(to right on the coordinate system), to be positive again. And that's why i didn't understand how do you separate right-up moving and left-down moving ants? also i wonder how do you get $a - b \geq t - m - 1$ for x-leaning?
21.07.2013 21:49
Yes, the ants only move in one direction, and this direction only changes when they run into an ant moving in the opposite direction. For the positive/x-leaning issue: I am simulating the problem under a few different systems of rules, which all have the same end result. The original problem's rules are equivalent to two ants meeting horizontally/vertically and then the two somehow turning in 90 degrees so that they go in opposite directions. There are multiple ways to make this happen. For the positive/negative ants, I specify that any ant which is moving right or down turns in a way that makes them continue moving right or down, meaning their coordinates always increase in the coordinate system I specified. Likewise, up-left moving ants always move up-left. For the x/y-leaning ants, I am working under a completely different set of rules in which ants moving right or up turn in a way so that they continue moving right or up. Similarly for left/down. This is independent of the positive/negative rules. As it turns out, both sets of rules give the same behavior for all the ants in set which is equivalent to the original rules, so I can draw conclusions from both about where ants can be after a certain amount of time.
22.07.2013 19:27
thanks, and as you got $a - b \geq t - m - 1$ for $x$ leaning, why is it correct? let $x, y$ be the starting points then the minimal value of $x-y$ is $1-m$ when the coordinates are $(\frac{1}{2}; m-\frac{1}{2})$ and after time $t$ we have that the difference of the points $a-b \geq t+(1-m)$
25.07.2013 12:18
can you answer me please?
08.11.2019 08:50
Here is a solution that doesn't involve changing the rules (hopefully it's right!). All the ants fall off the checkerboard after $\frac{3}{2}m-1$ seconds. To see that this is achievable, take two ants in the upper left and upper right corners moving towards each other. For points $X$ and $Y$, define $t(XY)$ to be the taxicab distance between $X$ and $Y$. Let $A, B, C, D$ be the centers of the corner squares of the board, and for any point $P$ inside rectangle $ABCD$, set $$f(P) = \min\{t(AP), t(BP), t(CP), t(DP)\}$$to be the minimum taxicab distance to one of the corners. Now we prove the main claim: Claim: Let $P$ be any point on the board. Then no collisions occur at $P$ after $f(P)$ seconds. Proof. Define an event at point $P$ to be either: placing an ant at $P$ at time $t = 0$, or a collision at $P$ at time $t > 0$. We show, by strong induction on $f(P)$, that no events occur at $P$ after time $t=f(P)$. The conclusion is obvious for all placing events; these are our base cases. [asy][asy] size(200); defaultpen(fontsize(10pt)); int m = 7; for (int i = 0; i <= m; ++i){ draw((i-0.5, -0.5)--(i-0.5, m-0.5), grey); draw((-0.5, i-0.5)--(m-0.5, i-0.5), grey); } pair A, B, C, D, P, Q, R; A = (0, 0); B = (0, m-1); C = (m-1, m-1); D = (m-1, 0); P = (2.5, 1.5); Q = (0, 1.5); R = (6, 1.5); path a1, a2, a3, a4; a1 = A--(0,1.5)--P--(2.5,-0.5); a2 = (0,3)--(0,1.5)--(-0.5,1.5); a3 = (6,1)--(6,1.5)--(6.5,1.5); a4 = (6,2)--(6,1.5)--P--(2.5,6.5); draw(a1, red+linewidth(0.9), EndArrow(TeXHead)); draw(a2, heavygreen+linewidth(0.9), EndArrow(TeXHead)); draw(a3, heavycyan+linewidth(0.9), EndArrow(TeXHead)); draw(a4, blue+linewidth(0.9), EndArrow(TeXHead)); draw((3,-0.5)--(3,6.5)^^(-0.5,3)--(6.5,3), dashed); dot("$A$", A, dir(225)); dot("$B$", B, dir(135)); dot("$C$", C, dir(45)); dot("$D$", D, dir(315)); dot("$P$", P, dir(45)); dot("$Q$", Q, dir(135)); dot("$R$", R, dir(135)); dot((0,3)); dot((6,1)); dot((6,2)); [/asy][/asy] Now suppose that two ants $X$ and $Y$ collide at $P$; WLOG assume $P$ is in the quadrant closest to $A$. Let $Q$ and $R$ be the locations of the most recent events that happened to $X$ and $Y$, respectively. Then $P$ lies inside segment $\overline{QR}$, and we may assume again without loss of generality that $$t(AQ) < t(AP) < t(AR).$$In particular, $Q$ must lie inside $A$'s quadrant, by the inductive hypothesis, the event at $Q$ happened at a time $t_Q \le t(AQ)$. Hence the collision at $P$ occurs at a time $$t_P = t_Q + t(PQ) \le t(AQ)+t(PQ) = t(AP) = f(P),$$completing the induction. $\blacksquare$ If $g(P)$ is the distance from a point $P$ to the farthest side of the board, then one can easily verify that $f(P)+g(P) \le \frac{3}{2}m-1$ for every $P$. Thus all of the ants have fallen off the board after $\frac{3}{2}m-1$ seconds, which completes the proof.
22.11.2019 01:17
Let the center of the board be $(0,0)$. By WLOG assuming that ants go either in the $+x$, $+y$ directions or $-x$, $-y$ directions, we get that after the time $\frac{3m}{2}-1$ any ant $(x_0,y_0)$ satisfies $|x_0+y_0|>\frac{m}{2}$. Similarly, if we WLOG assume that ants go either $+x$, $-y$ or $-x$, $+y$, we get that any ant after the time $\frac{3m}{2}-1$ satisfies $|x_0-y_0|>\frac{m}{2}$. If WLOG $x_0+y_0>0$, $x_0-y_0>0$, then $x_0=\frac{(x_0+y_0)+(x_0-y_0)}{2}>\frac{m}{2}$, so any ant is off the board. $\frac{3m}{2}-1$ is attained by placing two ants at $(m-\frac12,m-\frac12)$ and $(m-\frac12,\frac12-m)$ facing each other.
30.01.2020 06:57
Nice Problem! The answer is $\boxed{\frac{3}{2} n - 1}$. To see that it is attainable, consider an ant placed facing downwards on the top leftmost square and another ant placed facing upwards on the bottom leftmost square. We could WLOG that there are only two types of ants: Either the ant which only move up and right, or left and down. Call the ant of the first type as an $A$ ant and the second type as a $B$ ant. Clearly this doesn't affect the problem at all as we can't differentiate any two different ants. Now, consider a Cartesian coordinate $(0,0), (0,m), (m,0), (m,m)$ which denotes the vertex of the $m \times m$ square. Notice that after $t$ number of seconds, there are no $A$ ant in the region $\{ (x,y) | x + y \le t \}$. Similarly, there are no $B$ ant in the region $\{ (x,y) | x + y \ge 2m - t \}$. If we modify the statement of $A$ ant to move only up and left, $B$ ant to move only down and right. We could get another inequality: There will be no collision between two distinct ants on $|x - y| \le m - t - 1$. Hence, we get that all collision on point $(x,y)$ must satisfy: \[ t + 1 \le x + y \le 2m - t - 1 \ \text{and} \ |x - y| \le m - t - 1 \]Now, consider any $A$ ant. Suppose that it last collides at point $(x,y)$. Then the maximum number of time for it to fall must be $t + m - \min \{ x,y \} $. Now, notice that \[ t + 1 \le x + y \le 2 \min \{ x ,y \} + m - t - 1 \]Hence, \[ \min \{x ,y \} \ge t + 1 - \frac{m}{2} \]Therefore, the maximum number of time for any $A$ ant to fall is \[ t + m - \min \{ x ,y \} \le t + m - \left( t + 1- \frac{m}{2} \right) = \frac{3}{2} m - 1 \]A similar argument hold for $B$ ant as well.
13.07.2020 10:29
21.07.2020 16:37
\textbf{Solution.} Modify how the ants move. When the ants collide, WLOG let the ant that moves up or right to change its direction to right or up, so as the other ant which goes down or left. They will be called up-right ant and down-left ant respectively as they will only follow these two directions. Set up a coordinates system by letting the chessboard to have vertices $(0,0), (0,m), (m,0), (m,m)$. Consider the coordinates of an up-right ant at time $t$, then since $x+y$ increases by $1$ every second and it initially lands on the center of a square with $x+y\ge 1$, then $x+y\ge t+1$ at time $t$. Likewise $x+y\le 2m-t-1$ for a down-left ant. Only up-right ants will collide with down-left ants, so whenever a collision occur at time $t$ then $t+1 \le x+y\le 2m-t-1$. We turn our focus to bound $x-y$ now. WLOG now that every ant is either up-left or down-right. Then for time $t$, up-left ants has $x-y\le m-t-1$ and down-right ants has $x-y\ge t-m-1$. So at time $t$, a collision can only happen at $t-m-1\le x-y\le m-t-1$. We conclude that at time $t$, any collision that can happen at coordinates $(x,y)$ must satisfy $t+1\le x+y\le 2m-t-1$, and $t-m-1\le x-y\le m-t-1$. (*) Now let's consider an up-right ant again. Consider $t$ be the last instance for this ant to colide with other ants. Then at this time it's coordinates must satisfy (*), and we get $x\ge t+1-\frac{m}{2}, y\ge t+1-\frac{m}{2}$. After the collision the ant can move a distance of at most $\max\{m-x, m-y\}\le \frac{3m}{2}-t-1$, so add up the first $t$ seconds that gives distance $t$, this ant moves a total distance of at most $\frac{3m}{2}-1$. This argument applies for other ants by rotating the board $90^{\circ}$ for the other 3 configurations. $\blacksquare$
05.09.2020 22:16
16.12.2020 12:39
Every variable that we define will implicitly assumed to be an element of $\tfrac{1}{2}\mathbb{Z}$. Place the checkerboard on the coordinate plane such that the center of the lower left square is $(1,1)$ and the center of the upper right square is $(m,m)$. Note that collisions can only occur at $(x,y)\in[1,m]^2$. Suppose that there is an ant moving straight up at $(x,y)$ (and if it is during a collision, consider the time right before the collision). Let $f(x,y)$ be the latest possible time at which this is possible. Note that a time $\tfrac{1}{2}$ before exiting the board, an ant is at some $(x,y)$ moving in some direction, so by a suitable rotation to WLOG that direction to be up, we see that the answer we seek is \[\frac{1}{2}+\max_{(x,y)\in[1,m]^2}f(x,y).\]We have the following main claim. Claim: We have \[f(x,y)\le y-1 + \min\{x-1,m-x\}.\] Proof: We prove this by changing the rules. Indeed, post a collision, potentially swap ants so that an ant is always moving only up and right, or only down and left. It is clear now that an ant moving up at $(x,y)$ had path length at most $x-1+y-1$, so \[f(x,y)\le y-1+x-1.\]Now, change the rules so that an ant is always moving only up and left, or only down and right. It is clear now that an ant moving up at $(x,y)$ had path length at most $m-x+y-1$, so \[f(x,y)\le y-1+m-x.\]This proves the claim. $\blacksquare$ This now implies that we can be sure that all ants have fallen off right after time \[\frac{1}{2}+m-1+\frac{m-1}{2} = \boxed{\frac{3}{2}m-1}.\]We may achieve equality by having an ant at $(1,1)$ start moving right, and an ant at $(m,1)$ start moving left.
07.04.2021 11:17
The latest time the last ant can fall off is \(\frac32m-1\). If we impose a coordinate system with the vertices of the board being \(W=(0,0)\), \(X=(m,0)\), \(Y=(m,m)\), \(Z=(0,m)\), the construction is to place an ant at \((\frac12,\frac12)\) moving right and an ant at \((m-\frac12,\frac12)\) moving left. Alter the rules such that all ants always move either right and up or down and left. It is easy to see that the resulting process is equivalent. Now 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\). (Thus, the ant arrives at \(A\) from the left and leaves upward.) Place a bug on \(A\), and let \(b_1\) be the ant that collides with \(a\) at \(A=:B_0\). Let the bug initially move right, following \(b_1\)'s path backwards. For each \(i\ge1\), let \(b_i\)'s last collision before reaching \(B_{i-1}\) be \(B_i\), and let the bug that collides with \(b_i\) at \(B_i\) be \(b_{i+1}\); when the bug reaches \(B_i\), let it move backwards along \(b_{i+1}\)'s path. It is easy to see, then, that the bug only ever moves right and down. Finally, the bug's movement ends when it reaches some ant's starting position \(B_k\), i.e.\ ant \(b_k\)'s first collision occurs at \(B_{k-1}\). An example with \(k=3\) is shown below. [asy][asy] size(5cm); defaultpen(fontsize(10pt)); draw( (0,0)--(1,0)--(1,1)--(0,1)--cycle); real t=0.03; draw( (.1,.2)--(.1,.6)--(.3,.6)--(.3,1-t),red,Arrow()); draw( (.6,.95)--(.6,.6)--(.3+t,.6),blue,Arrow()); draw( (.45,.4)--(.6,.4)--(.6,.6-t),heavygreen,Arrow()); draw( (.75,.4)--(.6+t,.4),olive,Arrow()); dot("\(W\)",(0,0),SW); dot("\(X\)",(1,0),SE); dot("\(Y\)",(1,1),NE); dot("\(Z\)",(0,1),NW); dot("\(A_0\)",(.1,.2),S); dot("\(A\)",(.3,.6),NW); dot("\(B_1\)",(.6,.6),E); dot("\(B_2\)",(.6,.4),S); dot("\(B_3\)",(.75,.4),E); dot("\(A^*\)",(.3,1),N); [/asy][/asy] In what follows, all lengths are taxicab distances. Let \(t:=AA^*\) be the time when \(a\) falls off the board and let \(s:=AA_0\) be the time when \(a\) reaches \(A\), so \(AA^*=t-s\). Note that bugs \(b_i\) and \(b_{i+1}\) always meet at \(B_i\) at the same time, so if \(AB_i=d\), then both \(b_i\) and \(b_{i+1}\) arrive at \(B_i\) at time \(s-d\); in particular, \(AB_k=s\), so \(A^*B_k=t\). Now observe from \(WA_0\ge1\) and \(XB_k\ge1\) that \(WA^*\ge t+1\) and \(XA^*\ge t+1\). However, for each point \(A^*\) on \(\overline{YZ}\) we have \(WA^*+XA^*=3m\), so \(\min\{WA^*,XA^*\}\le\frac32m\). The desired bound \(t\le\frac32m-1\) follows.
06.04.2022 21:48
19.05.2022 23:30
The answer is $1.5m-1$; construction is trivial. The "clockwise" condition is irrelevant, so instead say that any ant starting with +x or +y can only move in these two directions and vice versa. At the start, suppose that every ant moving towards x=y receives a coin labeled with its distance from x=y (an ant on the line counts as moving away from it). Note that the greatest possible label is $m-1$. Whenever an ant with a coin intersects an ant without a coin, the coin changes hands, and whenever an ant crosses x=y, any coin that it has disappears (while possibly intersecting another ant). It's easy to see that an ant holds a coin iff it's currently approaching x=y. Notice that all coins always move at speed 1 towards x=y, so a coin disappears at the same time as its label. This means that after $m-1$ seconds, no coins are left and hence every ant is moving away from x=y. At that moment, consider an ant $a$, and assume WLOG it's currently moving towards +x. Its sum of coordinates is at least $m$, and since it's moving away from x=y, its x coordinate must be at least $\frac{m}{2}$. Therefore, it can move for at most $\frac{m}{2}$ seconds as desired.
03.07.2022 19:36
The answer is $\boxed{\frac{3}{2}m - 1},$ achievable by placing two ants on the bottom corners of the grid. Choose a diagonal of the checkerboard. Each time two ants moving in opposite directions meet on a square not on the diagonal and change directions, one of them was moving towards the diagonal and one of them was moving away, and the same can be said after the direction change. Since ants may be considered indistinguishable, we can change the rules so the ant moving away from the diagonal keeps moving away in a perpendicular direction, and the ant that moves towards the diagonal keeps moving towards it in a perpendicular direction. Now characterize the ants into two types. Type $A$ ants head towards the diagonal. Type $B$ ants head away from the diagonal. The only time ants change types are when a type $A$ ant reaches the diagonal and then always turns into a type $B$ ant. It takes at most $\frac{m}{2}$ time for any type $B$ ant to fall off from the moment it becomes a type $B$ ant. It takes at most $m-1$ time for any type $A$ ant to reach the diagonal, and then at most $\frac{m}{2}$ more time to fall off once it becomes a type $B$ ant, the end. $\blacksquare$
03.08.2022 23:41
squareman wrote: It takes at most $m-1$ time for any type $A$ ant to reach the diagonal, and then at most $\frac{m}{2}$ more time to fall off once it becomes a type $B$ ant Why is the latter part true? (i.e. taking $\frac{m}{2}$ time as opposed to $m - 1$ time after a type $A$ becomes type $B$). EDIT: I see now. It's because every ant is moving away from the diagonal at this point.
03.06.2023 03:55
Let an ant's vertical or horizontal distance to the $x=y$ line be $d$. Let an ant's value be $d$ if it is going towards the line and $-d$ if it is going away from it. When two ants moving in opposite directions meet, one is currently going towards $x=y$ and one is going away. One of them will continue going towards the line and one will continue going away. That is, unless they meet on $x=y$ in which case it doesn't matter. Thus, we can assign the direction the ant goes in, in a way that it either only goes right or up, or only goes left or down. When two ants meet and change directions, we can have them switch values so that the value of the ant will always be decreasing. The maximum starting value of any ant is at most $m-1$ so after $m-1$ seconds every ant is moving away from $x=y$, and so will take at most $\tfrac{m}{2}$ seconds to get to the edge. The answer is $\tfrac{3m}{2}-1$ achieved when two ants are at two adjacent corners moving towards each other.
24.09.2023 18:50
squareman wrote: It takes at most $\frac{m}{2}$ time for any type $B$ ant to fall off from the moment it becomes a type $B$ ant. It takes at most $m-1$ time for any type $A$ ant to reach the diagonal, and then at most $\frac{m}{2}$ more time to fall off once it becomes a type $B$ ant, the end. $\blacksquare$ I still think this type of resolution runs into issues if two type A ants collide on the diagonal itself at a point with distance more than $\frac{m}{2}$ from one of the edges. You'd need to show that this type of collision is impossible. Anyways, bad solution incoming. Color all ants initially going to the bottom or to the right red and those going up or to the left blue. Then redefine the turning operation such that red ants always go towards the bottom or right, and similarily. Claim: Add additional gridlines between midpoints of centers to get a $2m - 1 \times 2m - 1$ grid. Then ants all meet and turn on points of this grid. Proof. All ant starting positions have coordinates that the sum the same $\pmod{2}$. The result follows. $\blacksquare$ We now count the number of half moves possible. Claim: $3m - 2$ half moves are achieveable. Proof. Put ants facing each other in pairs at each of the corners. It then takes $m - 1 + m - 1 + m = 3m - 2$ moves before the ants fall off. $\blacksquare$ Claim: After $k$ half moves, points within $k$ of the bottom left or top right corner under the taxicab metric can't have a turn. Proof. We prove this inductively for the bottom right corner. The base case of $k$ follows immediately. Now suppose it holds for $1, 2, \dots, n - 1$. Consider the points $n$ away from the corner. Any turn there requires an ant going up or right within $n - 1$ of the corner. We induct on the fact that after $n$ turns there are no such ants with $n - 1$. FTSOC suppose that such an ant exists. Then consider its path up to going right or up. If it didn't turn, then it could have made at most $n - 1$ moves contradiction. If it did turn at a distance $k$ from the corner, that must have occured after at most $k$ moves, so the result still follows. $\blacksquare$ Claim: $3m - 2$ is the maximum possible number of moves. Proof. WLOG we show this result for a red ant on a grid. Enumerate the diagonals from the top left to bottom right as $d_{-2k+2}, \dots, d_0, d_{2k-2}$ in order of distance from the bottom left corner. Consider the first $2k-2$ half moves of the red ant. Then if the ant started on $d_{2a}$, such that if the red ant has more than $k-1+a$ downward moves, then it hits the bottom right triangle. First suppose that holds. If $a \ge 0$, then the number of rightward moves is at most $k-1$, so the total number of moves is at most $2k-1 + k-1 = 3k-2$. If $a < 0$, then there are similarly at most $2k-1+2a + (k-1-a) = 3k-2+a < 3k-2$ moves. As such, we are done unless the red ant has exactly $k-1+a$ downward moves in the first turn and $k-1-a$ rightward moves. This guarentees that the ant is in the bottom right $k \times k$ corner, at which point it can only make at most $2k - 2 + k = 3k - 2$ moves. $\blacksquare$ There are thus at most a length of $\frac{3}{2}k - 1$ full moves travelled.