A beautiful solution to a math contest problem

I was recently involved in writing a math contest at my university. One of the problems I contributed was the following:

Let $L$ be the line passing through points $(\sqrt{2},0)$ and $(0,\sqrt{2})$ of the XY -plane. Let $C_0$ be the circle of radius 1 centered at (0, 0). Let $C_1, C_2, C_3,\ldots $ be an infinite sequence of circles such that each $C_i$  is centered on the x-axis, each $C_i$ is tangent to $L$ and $C_{i+1}$ is tangent to $C_i$ for all $i\geq 0$. What is the total area of all these circles? 

The solution I had in mind was to find a recursive formula for the radius of $C_i$ and then sum the areas as a geometric series. One student came up with an absolutely stunning method, worthy of Archimedes. Consider the trapezoid $T_0$ formed from the $x$-axis, the line $L$ and the two vertical tangents to $C_0$. The area of the trapezoid is $2\sqrt{2}$ while the area of $C_0$ is $\pi$. So the ratio $\lambda$ of the area of $C_0$ to the area of $T_0$ is $\frac{\pi}{2\sqrt{2}}$. Now observe that the ratio of the area of $C_i$ to the area of the trapezoid $T_i$ formed from the vertical tangents to $C_i$, the line $L$ and the $x$-axis, is still $\lambda$ by similarity. So $$\sum \mathrm{Area}(C_i)=\lambda \sum \mathrm{Area}(T_i).$$
The sum of the areas of $T_i$ is just the area of an isosceles right triangle with side lengths $1+\sqrt{2}$, i.e. $\frac{(1+\sqrt{2})^2}{2}$. So we get $\frac{\pi}{2\sqrt{2}}\cdot \frac{(1+\sqrt{2})^2}{2}$. Magic!

More on Tiling Problems

This post continues my previous post. Here is, amazingly, an open problem.

Let the order of a tile be the smallest number of tiles that tiles a rectangle (of any size).

Conjecture (Klarner): The only tiles of odd order are rectangles (so have order $1$.)

It's actually a little difficult to find any tilings of a rectangle with an odd number of tiles, but it can be done. Assume now that our tiles are not themselves rectangles. The smallest known odd rectangular tiling has $11$ tiles. It is known that no tiling with $3$ tiles is possible. It's an interesting exercise to pack a 5x9 rectangle with L-shaped tiles with $3$ cells. I encourage you to try it!

In the last post, I defined tile homology $H(\mathcal T)$ for a given tile set $\mathcal T$. When I was talking about this with Morwen Thistlethwaite, he asked

Question (Thistlethwaite): Which abelian groups can be realized as tile homology groups?

This is an interesting question without an obvious answer!

Tile homology groups are actually the abelianization of tile homotopy groups $\pi(\mathcal T)$, first introduced by Conway and Lagarias. The idea here is to think of the boundaries of tiles (oriented counterclockwise) as paths in the square lattice. If we think of $x$ as meaning move one unit up and $y$ as moving one unit to the right, then every tile $t$ produces a conjugacy class $w(t)$ of words in the free group $F_2=\langle x,y\rangle$. One needs to look at conjugacy classes because different  starting points on the tile boundary will produce conjugate words. Moreover, if we fix the origin as the basepoint, different tile placements in the plane will give conjugate boundary words when we connect the boundary by a path back to the basepoint.

Let $b(\mathcal T)$ be the subgroup of $F_2$ normally generated by  $\{w(t_1), \ldots, w(t_k)\}$.

Theorem (Conway-Lagarias): If $\mathcal T=\{t_1,\ldots, t_k\}$ is a tile set which tiles the region $R$, then the boundary word $\partial R$ lies in $b(\mathcal T)$.

The idea of the proof is that $R$ is glued together from copies of tiles, so reading around the boundary of $R$ will be equivalent in $F$ to reading around the boundaries of the tiles which tile $R$. Thus it is a product of conjugates of boundaries of these tiles.

Let $\mathcal P(\mathcal T)=F_2/b(\mathcal T)$ be the path homotopy group $\mathcal P(\mathcal T)$. Then $\partial R\in \mathcal P(\mathcal T)$ gives an obstruction to tiling $R$ by tiles from $\mathcal T$.

The closed paths in the infinite grid correspond to commutators, and so the tile homotopy group $\pi(\mathcal T)$ is defined to be $[F_2,F_2]/b(\mathcal T)$.

Example: If $\mathcal T$ consists of the two orientations (vertical and horizontal) of an $n\times 1$ tile, then $\pi(\mathcal T)\cong F_{(n-1)^2}$, the free group on $(n-1)^2$ generators.

Example (Reid): If $\mathcal T$ consists of the $+$-shaped pentomino and the two orientations of a $1\times3$ tile, then $\pi(\mathcal T)$ is a finite group of order $120$. It is a $\mathbb Z_2$ extension of $A_5$.

In particular, Reid uses this last example to show that any rectangle tiled by the $+$-pentomino and $1\times 3$ tiles must have a side length divisible by $3$.

Tiling problems

I wanted to talk about some interesting work I uncovered while chasing a particular math.stackexchange problem down the rabbit hole. The setting will be an infinite square grid. The squares within the grid will be called "cells."

A tile is a connected (normally also simply connected) union of cells, where two tiles that are translations of each other are considered equivalent. Unless otherwise noted, we will also include rotations and reflections as equivalent.

A region R is a finite union of cells.

We will concern ourselves with the following problem. Given a tile set $\mathcal T=\{t_1, \ldots, t_k\}$, can a region $R$ be tiled with elements of $\mathcal T$. In other words can $R$ be represented as a disjoint union of placements of the tiles from $\mathcal T$?

The canonical example of this phenomenon is the $8\times 8$  chessboard with opposite corners removed. Can it be tiled by two element tiles (dominos)? The standard method is to note that in the resulting region, there are $30$ tiles of one color and $32$ of the other. Yet every domino must cover both a black and a white square. So the number of black squares covered by the dominoes must equal the number of white squares covered by the dominoes, and therefore the dominoes can't cover $R$.

Here is a trickier example:

Theorem (Klarner 1969): An $a\times b$ rectangle can be tiled by $1\times n$ tiles if and only if
$n|a$ or $n|b$.
[Proof]
The "if" direction is obvious, as one can take all tiles to be oriented in the same direction.

For the "only if" direction, suppose that $n\!\not |a$. Then $a=qn+r$ for some nonnegative integer $q$ and remainder $1\leq r<n$. Suppose the rectangle $R$ is placed in the plane with its bottom edge of length $a$. Color the columns of $R$ with $n$ different colors, cycling back to the start. In other words, the color of the $i$th column is the residue class of $i$ modulo $n$. Let $c_i$ be the number of cells colored by the $i$th color. The number of vertical stripes colored by colors $1,\ldots, r$ is $q+1$, while the number colored by $r+1,\ldots, n$ is $q$. So $c_1=\ldots=c_r=(q+1)b$ and $c_{r+1}=\ldots=c_n=qb$.

Now consider what happens when you place a vertically oriented tile in $R$. It will cover $n$ cells of the same color, so modulo $n$ it covers $0$ cells of each color. On the other hand a horizontally placed tile in $R$ will cover one cell of each color. So, if $h$ is the number of horizontally oriented tiles in some tiling of $R$, we must have $c_i\equiv h\bmod n$. Therefore $c_1\equiv c_2\equiv\cdots\equiv c_n\bmod n$. By our count above, this means $(q+1)b\equiv qb \bmod n$. Subtracting $qb$ from both sides yields $b\equiv 0\bmod n$. So we have shown that $n\!\not |a$ implies $n|b$. $\Box$

Here is another example, due to Michael Reid.
Example: Let $R$ be the $10\times 10$ square and let $\mathcal T$ consist of the different orientations of the $L$-shaped tetromino. Then $R$ cannot be tiled by $\mathcal T$.
[Proof]
Color the columns alternating with the numbers $1$ and $5$. Note that any placement of the tile will contain three $1$'s and one $5$ or three $5$'s and one $1$. In both cases, the numbers sum to $0$ modulo $8$. On the other hand the sum of numbers in $R$ is equal to $50\cdot 1+50\cdot 5\equiv 4\bmod 8$. $\Box$

Tile Homology
The previous example can be systematized into a universal invariant, called tile homology, defined for every tile set. Coloring arguments can then be extracted from this.

Let $A$ be the free abelian group on generators $a_{i,j}$ $i,j\in\mathbb Z$ for every cell in the grid. $A$ can be thought of as the set of numberings of the cells in the grid which are only nonzero in finitely many places. If $\mathcal T$ is a tile set, define $B(\mathcal T)$ to be the subgroup of $A$ generated by filling in the cells of all possible tile placements with $1$'s. The tile homology group is defined as
$$H(\mathcal T)=A/B(\mathcal T).$$

Theorem: If $R$ can be tiled by $\mathcal T$, then $[R]=0\in H(\mathcal T)$, where $[R]$ is the assignment $1$ to all cells in $R$, and $0$ to other cells.
 [Proof]
The proof is trivial. $\Box$

Examples:

1.  If $\mathcal T$ consists of $1\times n$ and $n\times 1$ tiles, $H(\mathcal T)=\mathbb Z^{(n-1)^2}$.
2.  If $\mathcal T$ consists of the $L$-shaped tile of height $2$ and width $n$, we have $$H(\mathcal T)=\begin{cases} \mathbb Z/(n+1)\mathbb Z&\text{if } n \text{ even}\\ \mathbb Z\oplus \mathbb Z/(n+1)\mathbb Z &\text{if } n\equiv 3\bmod 4\\ \mathbb Z\oplus \mathbb Z/ \frac{1}{2}(n+1)\mathbb Z&\text{if } n\equiv 1\bmod 4 \end{cases}.$$

Let's prove the first one. Take a horizontally oriented tile and subtract off another one which is displaced one unit to the right. Then $a_{i,j}-a_{i+n+1,j}\in B(\mathcal T)$. Similarly, $a_{i,j}-a_{i,j+n+1}\in B(\mathcal T)$. Thus, the generators $a_{i,j}$ in the $n\times n$ square $1\leq i,j\leq n$ are generators for $H(\mathcal T)$. To determine the relators, consider a tile in the plane. Using the two relations we derived above, we can translate it so that it overlaps the $n\times n$ square. Say it is horizontal, and jutting off the right end. Then, using the translation relations, we can translate the part jutting off the right $n$ units to the left. Thus the relation becomes that the sum of the squares in a row is $0$: $$a_{i,j}+\ldots a_{n,j}=0$$ Similarly the sum of squares in a column is $0$: $$a_{i,1}+\ldots a_{i,n}=0.$$ The result is a free abelian group of rank $(n-1)^2$.

The technique of proof in this case is pretty general. The idea is to find some simple relations as differences of differing tile placements, that allows you to push everything into a finite region. Then push the relators into this region as well to get a  presentation of the group. There are cases where the group is infinitely generated, however.

The proof of the second calculation is a bit tedious and not included here.

Theorem (Reid 2003): If $R\neq 0\in H(\mathcal T)$, there exists an additive homomorphism $\psi\colon A\to\mathbb Q$ such that $R\mapsto \mathbb Q\setminus\mathbb Z$, but every tile placement evaluates to an integer.
[Proof]
If $R\in H(\mathcal T)$ has finite order $n$ define $\phi\colon \langle R\rangle\to \mathbb Q/\mathbb Z$ by sending $R\mapsto 1/n$. (Here $\langle R\rangle$ denotes the subgroup generated by $R$. Otherwise let $R\mapsto 1/2$. Then $\phi$ extends to a map $\phi\colon H(\mathcal T)\to \mathbb Q/\mathbb Z$, since $\mathbb Q/\mathbb Z$ is a divisible group. Then the composition $A\to H(\mathcal T)\to\mathbb Q/\mathbb Z$ lifts to a map $\psi\colon A\to \mathbb Q$, since $A$ is a free abelian group. Now by definition, $\psi(R)=\frac{1}{n}+k$ or $\frac{1}{2}+k$ for some $k\in \mathbb Z $, but any tile placement $t$ maps to $0\in H(\mathcal T)$ and so $\psi(t)\in\mathbb Z$. $\Box$

In the $n\times 1$ case, let $\phi\colon H(\mathcal T)\to \mathbb Q/\mathbb Z$ be defined by sending $a_{1,1}\mapsto \frac{1}{2}$ and all other $a_{i,j}\mapsto 0$, $1\leq i,j\leq n-1$. Lifting this to $\psi\colon A\to \mathbb Q$ gives an assignment in the plane of
$$a_{i,j}\mapsto
\begin{cases} \frac{1}{2} &\text{ if } i,j\in\{0,1\} \bmod 8\\
 0& \text{otherwise} \end{cases}
$$
This coloring gives an alternate proof of Klarner's theorem. Any placement of a tile will hit $0$ or two $1/2$-colored cells, so will evaluate to an integer. On the other hand a rectangle evaluates to an integer iff one of its side lengths is divisible by $n$. If you place the rectangle so that $a_{1,1}$ is its lower left corner, then most of the colored squares come in clumps of $2$ or $4$, with the possible exception of corner squares. If neither $a$ nor $b$ is divisible by $n$ then the other three corners do not contain isolated colored squares, so the total number is odd. This is a contradiction.
See my argument (and picture) here.
$\Box$

References:

1. Klarner (1969) Packing a rectangle with congruent $n$-ominoes.
2. Conway-Lagarias (1990) Tiling with polyominoes and combinatorial group theory
3. Reid (2003) Tile homotopy groups