Browse · MathNet
Print49th Mathematical Olympiad in Ukraine
Ukraine counting and probability
Problem
The knight stands in the left lower corner of a chessboard and it is known that the first column and the last row are colored in red. The knight moves on the chessboard according to the chess rules but it can't get on the cell which is already colored in red. After every move of the knight we color in red the column and the row that contain the cell on which the knight has just got. Is it possible to color the whole chessboard in red if we act as described above?
Fig.15
Solution
As it is shown on the fig.15, we can color in red the first four columns and the first four rows of the chessboard. Now consider our chessboard without these four columns and rows. As we can see on the same figure, the fifth move of the knight brings it to the left lower corner of the new reduced chessboard. If we continue reducing our chessboard in the same way, then after 501 iterations we will receive a chessboard, which can be colored in red as shown on the fig.16.
Fig.16
Fig.16
Final answer
Yes
Techniques
Coloring schemes, extremal argumentsInduction / smoothing