Теорема де Брёйна

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

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

Пример

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

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

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

Обобщение

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

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

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

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

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

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

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