In an $m\times n$ table there is a policeman in cell $(1,1)$, and there is a thief in cell $(i,j)$. A move is going from a cell to a neighbor (each cell has at most four neighbors). Thief makes the first move, then the policeman moves and ... For which $(i,j)$ the policeman can catch the thief?
Problem
Source: Iranian National Olympiad (3rd Round) 2002
Tags: geometry, combinatorics proposed, combinatorics
grobber
08.10.2006 08:55
I believe the policeman can catch the thief precisely when $i,j$ have the same parity. I only have time to post a sketch, but basically, it should be obvious that the policeman can "push the thief in a corner", making the taxiab distance between the two equal to either $1$ or $2$. When $i,j$ have the same parity, the two will end up with the thief in a corner, say $(m,n)$, and the policeman in $(m-1,n-1)$, with the thief to move; clearly, the thief is lost in this situation . Otherwise, if $i-j$ is odd, then after each of the policeman's moves the taxicab distacne between the two is odd, so the policeman can never catch the thief.
ith_power
26.02.2009 06:00
your argument seems to be right in the sense that the policeman can catch th thief iff thief is at (m,n) and policeman is at (m-1.n-1) or similar situations at corners. However consider abcissa of cells only. each move changes it by 1. so $ (m - i) and (m - 1 - 1)$ should have same parity, similarly (n-j) and (n-2) should have same parity. similarly for other corners, Left upper: i should be even; n-2 and n-j have same parity=> j is even. Right Lower: j should be even ; n-2 and n-i have same parity=> i is even.
Lightning_17
08.04.2009 00:12
You forgot to say that the policeman always wins if either m or n is equal to 1. When m,n>1 we can colour the board in black and white like a chess board and notice that if they star in different colours the policeman never catches the thief. Using the argument of the taxiab distance we can see that the policeman can always decrease the distance between them, but the thief can increase it unless he is pushed in the corner, wich will happen because the policeman can always decrease its distance, now notice that since the distance is even in the beggining the distance between them will eventually be 2 and it's the thief's move. When he reaches a corner he has to decrease the distance and then since the distance is 1 and it's the policeman's move, we all know what happens next So the iff condition, just like grobber said is the distance is even so it means that i-1+j-1 is even meaning that i+j is even meaning they have the same parity. They don't need to both be even.