A lazy rook can only move from a square to a vertical or a horizontal neighbour. It follows a path which visits each square of an $8 \times 8$ chessboard exactly once. Prove that the number of such paths starting at a corner square is greater than the number of such paths starting at a diagonal neighbour of a corner square.
(7 points)
We will illustrate an injection from the paths starting from the b2 square to those starting from the a1 square. Then we will find a path starting from a1 that cannot be obtained through this injection. This will clearly prove the inequality.
It is clear by parity that a path starting from b2 cannot end on a1. But the path goes through a1 at some point,
wlog it enters a1 from b1. Then, it is forced to leave a2. So we have a path that goes b2->some path X -> b1->a1->a2-> some path Y.
But then we can clearly get the path a1->b1->path X backwards->b2->a2->follow through path Y. This clearly visits all the squares exactly once.
Now we describe a path that clearly cannot be obtained from the injection:
Move from a1 to h1 in a straight line, then visit in turn h2 to b2, b3 to h3 etc. then finally h8 to a8 and finishing at a2 (the right side is a zigzag).