3
$\begingroup$

Suppose that we have an $n\times m$ chessboard and bishop on the square $(1,1)$. It starts to move diagonally with the following rules:

  1. If bishop is in any corner square except $(1,1)$, it stops moving.

  2. If bishop meets a boundary square which is not a corner, it changes the direction of motion by continuing in the only direction that is not in the opposite direction the path just traveled (i.e. will travel along positions $(3,1) \to (2,2) \to (1,3) \to (2,4) \to \cdots $)

Is it possible to determine where the bishop will stop and its path? I found the case $\min\{n,m\}\not\mid\max \{n,m\}$ hard.

$\endgroup$
2
$\begingroup$

A hint:

Denote the centers of the squares by $(i,j)$ with $i$, $j$ integers $\geq0$. The size of the board is then $n'\times m'$ with $n'=n-1$, $\>m'=m-1$, and the starting point is $(0,0)$.

Replace the board with its universal cover, i.e. the integer lattice ${\mathbb Z}^2$, and mark all points $(k n', l m')$, $\ k,l\in{\mathbb Z}$ with at least one of $k$, $l$ odd, with a black star.

The bishp's complicated travel can now be "lifted" to ${\mathbb Z}^2$ and appears as a straight line. In this way it becomes easier to analyze under which circumstances this journey will hit a "forbidden corner" or will become periodic.

$\endgroup$
3
$\begingroup$

Hint: As is standard in this kind of problem, think of the bishop as moving along the line $y=x$, just that we have many chessboards (possibly reflected at the boundary).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.