When Can You Tile a Box With Translates of Two Given Rectangular Bricks?

Abstract

When can a $d$-dimensional rectangular box $R$ be tiled by translates of two given $d$-dimensional rectangular bricks $B_1$ and $B_2$? We prove that $R$ can be tiled by translates of $B_1$ and $B_2$ if and only if $R$ can be partitioned by a hyperplane into two sub-boxes $R_1$ and $R_2$ such that $R_i$ can be tiled by translates of the brick $B_i$ alone $(i=1,2).$ Thus an obvious sufficient condition for a tiling is also a necessary condition. (However, there may be tilings that do not give rise to a bipartition of $R.$)

There is an equivalent formulation in terms of the (not necessarily integer) edge lengths of $R,$ $B_1,$ and $B_2.$ Let $R$ be of size $z_1\times z_2\times \cdots\times z_d,$ and let $B_1$ and $B_2$ be of respective sizes $v_1\times v_2\times \cdots\times v_d$ and $w_1\times w_2\times \cdots\times w_d.$ Then there is a tiling of the box $R$ with translates of the bricks $B_1$ and $B_2$ if and only if

(a) $z_i/v_i$ is an integer for $i=1,2,\ldots, d;$ or

(b) $z_i/w_i$ is an integer for $i=1,2,\ldots,d;$ or

(c) there is an index $k$ such that $z_i/v_i$ and $z_i/w_i$ are integers for all $i\neq k,$ and $z_k=\alpha v_k+\beta w_k$ for some nonnegative integers $\alpha$ and $\beta.$

Our theorem extends some well known results (due to de Bruijn and Klarner) on tilings of rectangles by rectangles with integer edge lengths.