A parity problem [solution]

Last week, we posted a problem: http://shaanxoryog.hackers.mu/2015/09/a-parity-problem.html

Recap
First, a brief recap of the problem (for a better description, please check the link above):

You need to catch a thief who has evaded in a 1000 x 2 grid. In every hour the thief moves to an adjacent column, either to the left or right (as in picture above). In every hour, you can assign two policemen to search any 2 cells. If the thief is located in one of the two cells, you catch him, otherwise you don't. Devise a strategy which ensures that you can catch the thief within 2015 hours (or less).

Solution
Only one of our readers: $€|v3n proposed a solution by going in-depth into the problem. Unfortunately there was a small flaw in the solution. Anyway, we really appreciate the engagement and effort done to try solving it :)

The correct solution is as follows (details will follow):

Put the policemen in blocks of 2 and:
i) In the first hour, put them in column 1
ii) Then, after every hour, move them by 1 step starting from column 1 up to column 1000
iii) In the 1001-th hour, stay in column 1000
iv) Then, after every hour, move them by 1 step from column 1000 to column 1.

This solution seems very simple. We're just bringing the policemen from X=1 to 1000, then from X=1000 to 1 (taking 2000 hours)

But does it work? How does it ensure that we can catch the thief?

Dry run
First of all, this solution works for any N x 2 grid, not necessarily a 1000 x 2 grid.

Let's illustrate the solution above on a 5 x 2 grid to better see what's happening.
Assuming that the thief was in column 3 in the first hour:

Thief has no choice than move to the right. 

 Thief has no choice than move to the right.

Thief is caught since only possibility is to move to the left!

As you can see above, we caught the thief!

Let's say that, instead, in the first hour, the thief was in column 2 (instead of 3), at a distance of 1 from the policemen. He can skip the policemen by moving to the left in the second hour while the policemen are moving to the right. We will not get him in the first run. But then when the policemen come back from X=5 to 1, they will catch him! (try it on paper)

Parity of distance between thief and policemen

The most important thing to notice to build up the solution above is that in every hour, the thief must necessarily move to an adjacent column, either to the left or to the right - he can't stay in the same column.
Let's denote the column where the thief currently is in by x1 and the column where the two policemen are by x2.

In the next hour, the thief moves either to x1+1 or x1-1.
At the same time, our two policemen move from x2 to x2+1 (we are considering only the first half of the solution to illustrate it)

Before the movement, the distance between the thief and policemen was x1-x2
After 1 hour it becomes either:
x1+1-(x2+1) = x1+1-x2-1 = x1-x2
or
x1-1-(x2+1) = x1-1-x2-1 = x1-x2-2

Interesting. The parity of the distance does not change!
(x1-x2-2 has the same parity as x1-x2 since removing 2 from any number keeps its parity constant. If x1-x2 was odd, the new distance is also odd. If it was even, it stays even after every hour)

How does this help us?

If we somehow manage to catch the thief, then we must be present on the same column as the thief.
The distance between the thief and the policemen is in this case zero - an even parity.

Interesting!
If the original distance between thief and policemen was of even parity and in each move we're keeping it even and at the same time reducing the number of possible moves of the thief, we will eventually catch him!

This was the main trick. We're keeping the parity the same while reducing the number of possible moves for the thief. The thief's moves get constrained until we eventually are on the same column and catch the thief.

Wait wait wait.. This only works if the original parity was even as underlined above.
What if the thief was originally at an odd distance from the policemen?

That's true. But in our solution, when we reach X=1000, it changes the parity to odd!
We're stepping on X=1000 twice, so the parity of the distance gets changed at this point!

And when we come back from 1000 to 1, we will now catch the thief!

To recap - if the distance was of even parity we will catch the thief in first run (from X=1 to 1000), otherwise when we come back from X=1000 to 1, we will catch him!

Game Over.

In another article we posted recently, we talked about 2-player games in general. We're applying the same principle here - keeping the opponent on a "losing" state while reducing the number of moves. That's the trick.