De Bruyne’s theorem
De Bruyne’s theorem – the result of combinatorial geometry, according to which rectangular blocks (of any dimension), in which the length of each side is a multiple of the next shorter side length („harmonious bricks"), can be packed only in a rectangular block („box"), the size of the sides of which is a multiple of the sides of the brick …Established and published in 1969 by the Nicholas de Bruijn in one article along with other results on packing congruent rectangular blocks – bricks into large rectangular blocks – boxes so that there is no empty space.ExampleDe Bruyne proved this claim after his seven-year-old son was unable to fit 1 × 2 × 4 displaystyle 1 imes 2 imes 4 blocks into a 6 × 6 × 6 displaystyle 6 imes 6 imes 6 cube. The cube had a volume of 27 displaystyle 27 blocks, but only 26 displaystyle 26 blocks could fit into it. To understand this, we divide the cube into 27 displaystyle 27 smaller cubes, colored alternately in white and black, and note that such a partition has more unit cubes (cells) of one color than another, while any packing of blocks is 1 × 2 × 4 displaystyle 1 imes 2 imes 4 in a cube must have an equal number of cells of each color. De Bruyne’s theorem proves that perfect packing with such side sizes is impossible. The theorem is applicable to other sizes of bricks and boxes.Boxes that are multiples of blocksSuppose that a d displaystyle d -dimensional rectangular box (in mathematical terms, a rectangular parallelepiped) has side lengths A 1 × A 2 × ⋯ × A d displaystyle A_ 1 imes A_ 2 imes dots imes A_ d, and the bricks have side lengths a 1 × a 2 × ⋯ × ad displaystyle a_ 1 imes a_ 2 imes dots imes a_ d. If the lengths of the sides of the brick can be by the integers bi displaystyle b_ i and the multiplication result a 1 b 1, a 2 b 2,… adbd displaystyle a_ 1 b_ 1, a_ 2 b_ 2 , dots a_ d b_ d will be a permutation of numbers A 1, A 2,…, A d displaystyle A_ 1, A_ 2, dots, A_ d, the box is called multiple brick. The box can then be filled with such bricks in a trivial way with the same orientation of the bricks.GeneralizationNot all packaging requires a box to be a multiple of a brick. For example, as de Bruyne pointed out, a 5 × 6 displaystyle 5 imes 6 rectangular box can be filled with copies of 2 × 3 displaystyle 2 imes 3 rectangular bricks, but not all bricks will have the same orientation. However, de Bruyne proved that if bricks can fill a box, then for each ai, displaystyle a_ i, at least one of the quantities A i displaystyle A_ i must be a multiple of one of the sides of the brick. In the above example, the length of the side of the box 6 displaystyle 6 is a multiple of both 2 displaystyle 2 and 3 displaystyle 3.Harmonious bricksThe second result of de Bruijn, which is called de Bruijn’s theorem, concerns the case when each side of a brick is a multiple of the nearest smaller side. De Bruyne calls these bricks harmonious… For example, the bricks most commonly used in construction in the United States are 2 1 4 × 4 × 8 displaystyle 2 frac 1 4 imes 4 imes 8 (in inches) and are not harmonious, in Russia the brick standard is 250 × 120 × 65 mm, so they are also inharmonious, but the „Roman bricks" (from which buildings were built in Ancient Rome) had harmonious dimensions 2 × 4 × 12 displaystyle 2 imes 4 imes 12.De Bruyne’s theorem states that if a harmonious brick is packed in a box, then the box must be a multiple of the brick. For example, three-dimensional harmonious bricks with side lengths 1, 2 and 6 can only be packed in boxes in which one of the three sides is a multiple of six, and one of the other two has an even length. Packages of harmonious bricks in a box can use copies of bricks with a twist. Be that as it may, the theorem asserts that even with the existence of such a package, there must be a package with parallel transfers of bricks.In 1995, an alternative proof of the three-dimensional case of de Bruijn’s theorem was given using the algebra of polynomials.Inharmonious bricksBruyne’s third result is that if the brick is inharmonious, then there is a box that is not multiple to the brick, which can be filled with this brick. Packing a 2 × 3 brick displaystyle 2 imes 3 into a 5 × 6 box displaystyle 5 imes 6 gives an example of this. In the two-dimensional case, de Bruijn’s third result is easy to show. A box of dimensions A 1 = a 1 displaystyle A_ 1 = a_ 1 and A 2 = a 1 a 2 displaystyle A_ 2 = a_ 1 a_ 2 can be easily packed with a 1 displaystyle a_ 1 copies of bricks with dimensions a 1, a 2 displaystyle a_ 1, a_ 2, laid side by side. For the same reason, a box with dimensions A 1 = a 1 a 2 displaystyle A_ 1 = a_ 1 a_ 2 and A 2 = a 2 displaystyle A_ 2 = a_ 2 is also easy pack with copies of the same brick. Rotating one of these two boxes so that their long sides are parallel and placing the two boxes side-to-side, we get a package of bricks in a large box with dimensions A 1 = a 1 + a 2 displaystyle A_ 1 = a_ 1 + a_ 2 and A 2 = a 1 a 2 displaystyle A_ 2 = a_ 1 a_ 2. This large box is a multiple of a brick then and only then is the brick harmonious.