## Posts Tagged ‘packing’

### Rectangles with an Integral Side Length

August 3, 2010

I was recently reminded of this result, one of my all-time favorites due to its utterly unexpected method of solution.

Theorem.

Call a rectangle semi-integral if it has at least one side of integer length. Suppose that a rectangle is decomposed into a finite collection of smaller rectangles, each of which is semi-integral. Then the original rectangle is semi-integral.

Of course this would be trivial if we were talking about “fully integral” rectangles with both sides of integer length, but as it stands it is far from obvious.  It is certainly possible to decompose a rectangle into a collection of semi-integral rectangles in such a way that some rectangles have non-integral length and others have non-integral width, and based purely on geometric concerns, it seems plausible that a counterexample might exist.  Amazingly (to me), the simplest proof I know is this theorem is through integral calculus (and it is very simple indeed)!

Proof of Theorem.

Orient the rectangles so that the sides are parallel to the coordinate axes, so that every rectangle involved has the form $R=[a,b]\times [c,d]$.  For any real numbers $\alpha,\beta$, consider the function $f(x,y)= \cos(2\pi x+\alpha)\cos(2\pi y+\beta)$.  The integral of this function over a rectangle, $\int_a^b\int_c^d f(x,y) \/dy\/dy$ is relatively easy to compute: $\frac{1}{4\pi^2}\left(\sin(2\pi b + \alpha)-\sin(2\pi a+ \alpha)\right)\left(\sin(2\pi d + \beta)-\sin(2\pi c+ \beta)\right).$  By the periodicity of the sine, this integral will vanish for every $\alpha,\beta$ if and only if the rectangle is semi-integral.  If $f$ integrates to 0 on every subrectangle in the decomposition, then $f$ integrates to 0 on the large rectangle. $\square$.

Note that the proof immediately generalizes to higher dimensions!  If an n-dimensional box is decomposed into a finite union of sub-boxes, each of which has at least one integral side length, then the original box has at least one integral side length.

The mathematician Alain Connes has publicly said that one cannot truly understand the integers if one does not understand this problem.