When Can You Tile a Box With Translates of Two Given Rectangular Bricks? - Bower, Richard J.; Michael, T. S. (The Electronic Journal of Combinatorics, 2004)
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× z_2× …× z_d, and let B_1 and B_2 be of respective sizes v_1× v_2× …× v_d and w_1× w_2× …× 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,…, d; or (b) z_i/w_i is an integer for i=1,2,…,d; or (c) there is an index k such that z_i/v_i and z_i/w_i are integers for all i eq k, and z_k=α v_k+β w_k for some nonnegative integers α and β. Our theorem extends some well known results (due to de Bruijn and Klarner) on tilings of rectangles by rectangles with integer edge lengths.