Mathematical proof!

Listen everyone, who wants to prove the algorithm to this problem!

See the solution of the problem 3 from IMO34 (International Mathematical Olympiad, year 1993).

The rectangle in that problem is n*n (not m*n), but it isn't important.

And the case 1*n is clear, I think.