Теорема де Брёйна (Mykjybg ;y >j~wug)

Раскраска единичных кубов в $6\times 6\times 6$ коробке, которую можно использовать для доказательства невозможности упаковки в коробку кирпичей с размерами $1\times 2\times 4$

Теорема де Брёйна — результат комбинаторной геометрии, согласно которому прямоугольные блоки (любой размерности), у которых длина каждой стороны кратна следующей меньшей длины стороны («гармоничные кирпичи»), могут быть упакованы только в прямоугольный блок («коробку»), размер сторон которого кратен сторонам кирпича.

Установлена и опубликована в 1969 году нидерландским математиком Николасом де Брёйном в одной статье наряду с другими результатами об упаковке конгруэнтных прямоугольных блоков — кирпичей в бо́льшие прямоугольные блоки — коробки, таким образом, чтобы не оставалось пустого места.

Пример

Де Брёйн доказал это утверждение после того, как его семилетний сын не смог уложить блоки размера $1\times 2\times 4$ в куб $6\times 6\times 6$. Куб имел объём, равный объёму $27$ блоков, но только $26$ блоков можно в него уложить. Чтобы это понять, разобьём куб на $27$ меньших кубов, раскрашенных поочерёдно в белый и чёрный цвет, и заметим, что такое разбиение имеет единичных кубиков (ячеек) одного цвета больше, чем другого, в то время как любая упаковка блоков $1\times 2\times 4$ в куб должна иметь равное число ячеек каждого цвета. Теорема де Брёйна доказывает, что совершенная упаковка с такими величинами сторон невозможна. Теорема применима и к другим размерам кирпичей и коробок.

Коробки, кратные блокам

Предположим, что $d$-мерная прямоугольная коробка (в математических терминах — прямоугольный параллелепипед) имеет целочисленные длины сторон $A_{1}\times A_{2}\times \dots \times A_{d}$, а кирпичи имеют длины сторон $a_{1}\times a_{2}\times \dots \times a_{d}$. Если длины сторон кирпича можно умножить на целые числа $b_{i}$ и результат перемножения $a_{1}b_{1},a_{2}b_{2},\dots a_{d}b_{d}$ будет перестановкой чисел $A_{1},A_{2},\dots ,A_{d}$, коробка называется кратной кирпичу. Коробка может быть тогда заполнена такими кирпичами тривиальным образом с одинаковой ориентацией кирпичей.

Обобщение

Не для всякой упаковки обязательно коробка должна быть кратна кирпичу. Например, как заметил де Брёйн, прямоугольную коробку $5\times 6$ можно заполнить копиями прямоугольных $2\times 3$ кирпичей, но при этом не все кирпичи будут одинаково ориентированы. Однако де Брёйн доказал, что если кирпичи могут заполнить коробку, то для каждого $a_{i},$ по меньшей мере одна из величин $A_{i}$ должна быть кратна одной из сторон кирпича. В вышеприведённом примере длина стороны коробки $6$ кратна как $2$, так и $3$.

Гармоничные кирпичи

Второй результат де Брёйна, который называют теоремой де Брёйна, касается случая, когда каждая сторона кирпича кратна ближайшей по размеру меньшей стороне. Де Брёйн называет эти кирпичи гармоничными. Например, наиболее часто применяемые в строительстве в США кирпичи имеют размеры $2{\frac {1}{4}}\times 4\times 8$ (в дюймах) и не являются гармоничными, в России стандарт кирпича 250×120×65 мм, так что они тоже негармоничные, а вот «римские кирпичи» (из которых строили здания в Древнем Риме) имели гармоничные размеры $2\times 4\times 12$.

Теорема де Брёйна утверждает, что если гармоничный кирпич упакован в коробку, то коробка должна быть кратной кирпичу. Например, трёхмерные гармоничные кирпичи с длинами сторон 1, 2 и 6 могут быть упакованы лишь в коробки, в которых одна из трёх сторон кратна шести, а одна из двух других имеет чётную длину. Упаковки гармоничного кирпича в коробку могут использовать копии кирпича с поворотом. Как бы то ни было, теорема утверждает, что даже при существовании такой упаковки должна существовать упаковка с параллельными переносами кирпича.

В 1995 году дано альтернативное доказательство трёхмерного случая теоремы де Брёйна с использованием алгебры многочленов.

Негармоничные кирпичи

Коробка $(a_{1}+a_{2})\times (a_{1}a_{2})$, разбитая на кирпичи $a_{1}\times a_{2}$ для случая $a_{1}=2$ и $a_{2}=5$

Третий результат Брёйна — если кирпич негармоничный, то существует некратная кирпичу коробка, которая может быть заполнена данным кирпичом. Упаковка кирпича $2\times 3$ в коробку $5\times 6$ даёт пример этого. В двумерном случае третий результат де Брёйна легко показать. Коробку размерами $A_{1}=a_{1}$ и $A_{2}=a_{1}a_{2}$ легко упаковать с помощью $a_{1}$ копий кирпича с размерами $a_{1},a_{2}$, уложенными сторона к стороне. По той же причине коробку с размерами $A_{1}=a_{1}a_{2}$ и $A_{2}=a_{2}$ также легко упаковать копиями того же кирпича. Вращая одну из этих двух коробок так, что их длинные стороны станут параллельны и расположив эти две коробки сторона-к-стороне, получим упаковку кирпича в бо́льшую коробку с размерами $A_{1}=a_{1}+a_{2}$ и $A_{2}=a_{1}a_{2}$. Эта бо́льшая коробка кратна кирпичу тогда и только тогда кирпич гармоничен.

Литература

• N. G. de Bruijn. Filling boxes with bricks // The American Mathematical Monthly. — 1969. — Т. 76. — С. 37–40. — doi:10.2307/2316785.
• Ross Honsberger. Mathematical Gems II. — Washington, DC: Mathematical Association of America, 1976. — С. 69. — ISBN 9780883853009.
• J. W. Nienhuys. De Bruijn's combinatorics: classroom notes. — 2011. — С. 156.
• John J. Watkins. Across the Board: The Mathematics of Chessboard Problems. — Princeton University Press, 2012. — С. 226. — ISBN 9781400840922.
• R. T. Kreh. Masonry Skills. — 5th. — Cengage Learning, 2003. — С. 18. — ISBN 9780766859364.
• Sherman K. Stein, Sándor Szabó. Algebra and Tiling: Homomorphisms in the Service of Geometry. — Washington, DC: Mathematical Association of America, 1994. — Т. 25. — С. 52. — (Carus Mathematical Monographs). — ISBN 0-88385-028-1.
• Paul Boisen. Polynomials and packings: a new proof of de Bruijn's theorem // Discrete Mathematics. — 1995. — Т. 146, вып. 1-3. — С. 285–287. — doi:10.1016/0012-365X(94)00070-1.

Ссылки

• Weisstein, Eric W. de Bruijn's Theorem (англ.) на сайте Wolfram MathWorld.