A standard 8 x 8 wooden chessboard has a straight line scratch in its surface, and is taken in for repair. The artisan who it is brought to decides to cover each affected square with a thin wooden veneer of the appropriate color.

Assuming that a different veneer is needed for each square of the board, what is the maximum number of such veneers that the artisan will require to do the job?

First, realize that the scratch is continuous. If the scratch is in one square, it will be in an adjacent square only if there is some point where the scratch crosses the border between them, and it will be in a non-adjacent square only if there is a sequence of adjacent squares for which the previous statement is true. The length of the scratch is one more than the number of boders crossed. [A curved scratch could possibly double back into an already counted square, lowering the expected total, but the problem states the scratch is a straight line.]

Second, realize that when it crosses the border between two adjacent squares, the scratch is also crossing the border between two adjacent ranks or two adjacent columns. [Again, a straight line cannot double back to cross twice.]

There are 8 columns, and so there are 7 borders between pairs of columns. Similarly, there are 7 borders btween pairs of ranks. The maximum number of borders that the scratch can cross is 14, so the length of the scratch is 14 + 1= 15.

Posted by TomM on 2002-05-27 22:32:14