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?

Let us imagine square boards from 2x2 all the way to 8x8.

Let us examine these boards by placing them into quadrant I of an x and y coordinate system.

If we begin by imagining a 2x2 board containing 4 unit squares, the maximum number of unit squares affected by a straight line stratch will be 3. This results from a line parallel to the corner to corner diagonal [from (0,0) to (2,2)] but which begins at (1/2, 0) and ends at (2,3/2), there are other endpoints that would acheive the same number of unit squares.

There is no way to affect 4 out of the 4 unit squares on a 2x2 board with a single straight line.

If we add one row and one column to our board we move up to a 3x3 board with 9 unit squares. If we extend our "stratch" line to meet the board's new borders, we discover 5 unit squares are now affected. If we continue this process, we find a series of fractions whose numerator is the "stratched" unit squares and whose denominator is the board size. So our, series appears as:
3/4, 5/9, 7/16, 9/25, 11/36, 13/49, and finally 15/64.

This agrees with what I find when I play around with a chess board and place a straight line across its dimensions.

proof through induction? this is all I could think of because I haven't done advanced math in a long time. Someone want to run with this and make it more mathematically rigorous?
What do we say?

Posted by brent on 2002-05-24 16:04:56