3360.22 – City Hall Tile Floor

City Hall has a splendid rectangular black-and-white tiled floor. The tiles are squares. There are 93 of them in one direction and 231 in the other. A mouse runs in a straight line diagonally from one corner of the floor to the opposite corner. How many tiles does it cross?

Solution

Take a piece of graph paper with 1" squares, or a checkerboard. Stretch a thread across a "floor" of various small dimensions – 2 $\times$ 2, 2 $\times$ 3, 2 $\times$ 4, 5 $\times$ 2, etc, and tally the number of squares that are crossed. It makes a nice class activity for pairs of students, one stretching the thread, both counting, and the other writing.

What emerges is a fascinating and non-obvious pattern. For a floor that is $n \times m$ tiles, the number of tiles the mouse crosses is equal to $m + n$ minus the greatest common factor of $m$ and $n$ .

For the floor that's 93 $\times$ 231, the answer is $93 + 231 - 3 = 321$ .

N.B. The problem assumes that the tiles are lined up with the walls, so that the floor looks like some sort of a checkerboard. This is not the proper way to lay the tiles (ask the Bostonians): they should be laid on the diagonal to look right.