Tour a $M\times N$ chess board with a piece that moves in each turn along the diagonal of a $m\times n$ rectangle

84 Views Asked by At

Here a "tour" is a sequence of moves that visit each square of the board. A square can be visited more than once if necessary.

For example, in a $8\times 8$ chess board, a knight which makes $2\times1$ type moves can tour the whole board from an arbitrary starting point, but a bishop which makes $1\times 1$ (or $k\times k$) type moves can not. What condition must $M,N,m,n$ satisfy so that a full board tour from any starting point is possible?