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

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

Пример

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

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

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

Обобщение

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

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

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

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

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

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

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

Примечания

Литература

• N. G. de Bruijn. // The American Mathematical Monthly. — 1969. — Т. 76 . — С. 37–40 . — doi : .
• Ross Honsberger. Mathematical Gems II. — Washington, DC: Mathematical Association of America, 1976. — С. 69 . — ISBN 9780883853009 .
• J. W. Nienhuys. . — 2011. — С. 156.
• John J. Watkins. . — Princeton University Press, 2012. — С. 226. — ISBN 9781400840922 .
• R. T. Kreh. . — 5th. — Cengage Learning, 2003. — С. 18. — ISBN 9780766859364 .
• Sherman K. Stein, Sándor Szabó. . — 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 : .

Ссылки

• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .