The numbers are put in some order into the squares of a checkered board, one number per square. Pete performs several moves according to the following rules. On the first move, he puts a token into some square. By any subsequent move, he may either put a new token into an arbitrary square, or to move a token horizontally or vertically from a square containing some number to any square containing a number greater than . Every time a token is put onto a square, this square is marked; it is prohibited to put a token into a marked square.
Find the least number such that for every arrangement of the numbers, Pete can mark all the squares of the board using at most tokens.
Solution
Answer: .
Let us show that tokens are sufficient. Note that one token is enough for each row: you can put it in the square of the row with the minimal number, and then visit all the squares of the row in order of increasing numbers.
On the other hand, let us show that fewer than tokens may not be enough. To do this, number the squares so that the squares of one diagonal are numbered (the remaining squares are numbered arbitrarily). Then one token cannot visit two squares of this diagonal: if a token is placed on one of these squares, then on the next move it must go to a square with a number greater than , and after that it cannot return to the diagonal.
Finally, since a token must visit each square of the diagonal, Pete will have to use at least tokens.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.