## Sunday, August 16, 2009

### KBB2 Problem 3

Suppose the Cartesian plane is tiled with infinitely many square tiles such that:

1. The square tiles must have the same size and form a chessboard-like formation.

2. Each tile corner must lie on a point with integer x-coordinate and y-coordinate

3. The tile sides need not be parallel to the X or Y axis.

Given that the points $(0,0)$ and $(3,1)$ are both tile corners (not necessarily of the same tile), determine all the possible tile sizes.

#### Solution

Let $s$ be the tile size. Suppose one walks from $(0,0)$ to $(3,1)$ in a shortest possible route. In that route, say he walks $a$ tiles down, then makes a left or right turn, and walks $b$ tiles across. His displacement from the origin is $\sqrt{(as)^2 + (bs)^2} = s\sqrt{(a^2+b^2)}$. But it's also $\sqrt{3^2+1^2} = \sqrt{10}$

Thus $s^2(a^2+b^2) = 10$. Now $s$ is an integer because the corners must lie on lattice points. $a$ and $b$ are also integers. Thus, $s^2$ divides 10, which means $s$ could only be $1,\sqrt{2}, \sqrt{5}, \sqrt{10}$

Now we need to show that each possibility has a feasible configuration.

For $s=1$, we can tile by making each lattice point a corner.

For $s = \sqrt{2}$, we can tile by making a lattice point a corner if and only if it's x and y coordinate are both even or both odd.

For $s = \sqrt{5}$, we can place the first tile at $(0,0), (1,2), (2,-1), (3,1)$ and place the others accordingly.

For $s = \sqrt{10}$, we can place the first tile at $(0,0), (3,1), (-1,3), (2,4)$ and place the others accordingly.