Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
When can a d-dimensional rectangular box R be tiled by translates of two given d-dimensional rectangular bricks B1 and B2? We prove that R can be tiled by translates of B1 and B2 if and only if R can be partitioned by a hyperplane into two sub-boxes R1 and R2 such that Ri can be tiled by translates of the brick Bi 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.) | When Can You Tile a Box With Translates of Two Given Rectangular Bricks Richard J. Bower and T. S. Michael Mathematics Department United States Naval Academy Annapolis MD 21402 tsm@usna.edu Submitted Feb 21 2004 Accepted May 10 2004 Published May 14 2004 MR Subject Classifications 05B45 52C22 Abstract When can a d-dimensional rectangular box R be tiled by translates of two given d-dimensional rectangular bricks B1 and B2 We prove that R can be tiled by translates of B1 and B2 if and only if R can be partitioned by a hyperplane into two sub-boxes R1 and R2 such that Ri can be tiled by translates of the brick Bi 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 Bl and B2. Let R be of size Z X z2 X X zd and let Bl and B2 be of respective sizes V1 X v2 X X vd and W1 X w2 X X wd. Then there is a tiling of the box R with translates of the bricks B1 and B2 if and only if a zi vi is an integer for i 1 2 . d or b zi wi is an integer for i 1 2 . d or c there is an index k such that zi vi and zi wi are integers for all i k and zk avk 3wk for some nonnegative integers a and 3. Our theorem extends some well known results due to de Bruijn and Klarner on tilings of rectangles by rectangles with integer edge lengths. 1 Introduction and Main Theorem A d-dimensional rectangular box or brick of size V1 X v2 X X vd is any translate of the set x1 x2 . xd G Rd 0 xi vi for i 1 2 . d . Corresponding author. Partially supported by the Naval Academy Research Council THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 N7 1 Thus a box or brick in dimension d 2 is simply a rectangle with sides parallel to the coordinate axes. We study the problem of tiling a d-dimensional rectangular box with translates of two given d-dimensional rectangular bricks. We use the term tile in the following .
