A chess rook can only travel horizontally or vertically, but not diagonally. We color the
bottom of a chess rook red. So, when it makes a move it paints all the squares it travels over red.
Prove that, a rook will need at least 2n − 1 moves to every square of an n × n chess board red.
how to prove it??
National Junior Problem 7
-
Nayer_Sharar
- Posts:16
- Joined:Mon Dec 21, 2020 9:26 pm
Re: National Junior Problem 7
We will prove this by induction.Define $P(n)$ as $\rightarrow $ It takes at least $2n-1$ moves for a rook to cover $n\times n$ chessboard
It is easy to see that $P(1)$ holds
Suppose $P(m)$ holds for some $m>1,m\in N$
Consider a $(m+1)\times (m+1)$ chessboard.The rook can cover maximum
$m$ squares in $1$ move.WLOG,the rook has covered a row instead of a column.Now the rook is at the last square of the first row.To cover maximum squares on the next move,the rook must cover the whole column in which the last square of the first row is situated.Now suppose the rook has done that.
$\therefore$ the rook has traveled $2m-1$ squares in $2$ moves.Now, the remaining is a $m\times m$ chessboard.
By induction hypothesis,it will take at least $2m-1$ moves for the rook to cover the remaining board.So, the rook needs at least
$2m-1+2=2m+1=2m+2-1=2(m+1)-1$ moves to cover the $(m+1)\times (m+1)$ chessboard.
$\Longrightarrow P(m+1)$ holds,This completes our induction.
It is easy to see that $P(1)$ holds
Suppose $P(m)$ holds for some $m>1,m\in N$
Consider a $(m+1)\times (m+1)$ chessboard.The rook can cover maximum
$m$ squares in $1$ move.WLOG,the rook has covered a row instead of a column.Now the rook is at the last square of the first row.To cover maximum squares on the next move,the rook must cover the whole column in which the last square of the first row is situated.Now suppose the rook has done that.
$\therefore$ the rook has traveled $2m-1$ squares in $2$ moves.Now, the remaining is a $m\times m$ chessboard.
By induction hypothesis,it will take at least $2m-1$ moves for the rook to cover the remaining board.So, the rook needs at least
$2m-1+2=2m+1=2m+2-1=2(m+1)-1$ moves to cover the $(m+1)\times (m+1)$ chessboard.
$\Longrightarrow P(m+1)$ holds,This completes our induction.