It's very easy to get but how to prove it?

Edited by author 08.08.2012 02:32

Warning: spoilers. Don't read if you have not solved problem.
------------------------------------------------------------











Well, I can't prove that there always exists path with such length, but I can prove that every path has at least such length.

Obviously, we need to prove that there is always at least (n + m + 1) diagonal moves.
Let cell be black if both it coordinates are not divisible by two and white otherwise.
There are (n+1)(m+1)/4 black squares.

Let f be amount of white cells we have visited plus amount of diagonal moves we have made.
We start our movement from some black point. When we start f is zero.

Assume we are now in black point.
Lemma
To reach another black points we need to increase f by at least 3.
Proof:
10101
00000
10X01
00000
10101
(X is our cell, 0's are while squares, 1 are black).
It's obvious, that if don't do diagonal moves at all, we need to visit at least 3 white squares.
If we do at least 2, then we visit at least one white square, 2 + 1 = 3.
If we do exactly 1, then if it is first move, then we can't leave white squares with second non-diagonal
move. If first move is non-diagonal, then second diagonal can't help. So in that case it's true too.
So we have proved lemma.

Now, f is amount of diagonal moves plus nm - (n+1)(m+1)/4. From the other side
f >= 3(n+1)(m+1)/4 because of lemma.
So (amount of diagonal moves) >= 4(n+1)(m+1)/4 - nm = n + m + 1.

Sorry for my bad English and possible bad explanation.















Spoilers End
--------------------