When can you tile a box with translates of two given rectangular bricks?

Richard J. Bower ; T. S. Michael

The electronic journal of combinatorics, Tome 11 (2004) no. 1

Résumé

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.

Détail

DOI : 10.37236/1848

Classification : 05B45, 52C22
Mots-clés : rectangular box, rectangular bricks, tiling