In chess, a rook at position hr, ci can move in a straight line either horizonta

Question

In chess, a rook at position hr, ci can move in a straight line either horizontally or vertically (to
hr ± x, ci or hr, c ± xi, for any integer x). (See Figure 5.11.) A rook’s tour is a sequence of legal moves, starting
from a square of your choice, that visits every square of the board once and only once. Prove by induction that
there exists a rook’s tour for any n-by-n chessboard for any n 1.

Figure Below:

proof fromm ertically (to noves, starting induction that already seen: a msists of four and level e Figure 5.11: A rook can move to any of the positions marked with a circle. pinski triangle

Explanation / Answer

The proof is as follows:

The base case n = 2

If we place rook at 1,1 we will have moves in first row and first column. Similarly
for all the positions (1,2) , (2,1), (2,2)

Hypothesis

The statement is true for n = k and we will prove for k+1.

Considering a chess board of size k+1.

We have assumed the statement is true for n = k. For any (i,j) in chess board we have
row i and column j as rook moves. Now going to n = k+1, we have increased the row by 1
and column by 1. So all the moves in the chess board of size k can be extended by 1 rowwise
and columnwise as per valid rook moves. If we consider any position in the new row and new column,
the possible moves will be row as k+1 and column as k+1 as per rook moves and we will have rook moves for all the newly added positions.As for the size k , it is true and as per the above
statements it is true for k+1 size also

Hence proved.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.