38. Vasya placed numbers from 1 to $99^2$ once in each cell of a $99 \times 99$ board. Petya chooses a cell on the board, places a chess king on it, and wants to make as many moves as possible with the king so that the number under it keeps increasing. What is the maximum number of moves Petya can definitely make, no matter how Vasya arranges the numbers?

(S. Berlov)
38. Answer: 3 moves (the king will visit 4 squares).

The rule by which a chess king moves allows it to visit the squares of any $2 \times 2$ square within the board in any order, so Petya will always be able to make three moves with the king: he will choose any such square, place the king on the smallest number in this square, then move it to the next largest number, then to the next largest, and finally to the largest number in this square. We will show how to color the board so that Petya cannot make more than three moves with the king. We will divide the grid into $2 \times 2$ squares (some squares will extend beyond the edge of the board). Let Vasya place the numbers on the board in ascending order: first in the upper-left corner cells of the squares, then, when all these cells are filled, he continues to place numbers in the upper-right cells, when they are all filled, Vasya will start filling the lower-left cells, and finally the lower-right cells. On such a board, the king will not be able to make more than three moves.