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

В статье 1969 года голландский математик Николаас Говерт де Брейн доказал несколько результатов об упаковке одинаковых прямоугольных кирпичей (любого размера) в более крупные прямоугольные коробки таким образом, чтобы не оставалось места. Один из этих результатов теперь известен как теорема де Брейна . Согласно этой теореме, «гармонический кирпич» (тот, в котором длина каждой стороны кратна длине следующей меньшей стороны) можно упаковать только в коробку, размеры которой кратны размерам кирпича. ^[1]

Пример

Де Брёйну пришлось доказать этот результат после того, как его тогдашний семилетний сын Ф. В. де Брёйн не смог упаковать кирпичи размерного размера. $1\cdot 2\cdot 4$ в $6\cdot 6\cdot 6$ куб. ^[2]^[3] Куб имеет объем, равный объему $27$ кирпичи, но только $26$ в него можно укладывать кирпичи. Один из способов убедиться в этом — разбить куб на $27$ кубики меньшего размера $2\cdot 2\cdot 2$ окрашены попеременно в черный и белый цвета. В этой раскраске элементарных ячеек одного цвета больше, чем другого, но при этой раскраске любое размещение $1\cdot 2\cdot 4$ кирпич должен иметь одинаковое количество ячеек каждого цвета. Следовательно, любое замощение кирпичами также будет иметь равное количество ячеек каждого цвета, что невозможно. ^[4] Теорема де Брейна доказывает, что идеальная упаковка таких размеров невозможна в более общем смысле, который применим ко многим другим размерам кирпичей и коробок.

Коробки, кратные кирпичу

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

Обобщение

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

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

Второй результат де Брейна, называемый теоремой де Брейна, касается случая, когда каждая сторона кирпича является целым числом, кратным следующей меньшей стороне. Де Брейн называет кирпич с этим свойством гармоничным . Например, наиболее часто используемые кирпичи в США имеют размеры $2{\tfrac {1}{4}}\cdot 4\cdot 8$ (в дюймах), что не является гармоничным, но кирпич, продаваемый как «римский кирпич», имеет гармоничные размеры. $2\cdot 4\cdot 12$ . ^[5]

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

Бойзен (1995) предоставил альтернативное доказательство трехмерного случая теоремы де Брейна, основанное на алгебре полиномов . ^[7]

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

Третий результат де Брейна заключается в том, что если кирпич негармоничен, то существует ящик, который он может заполнить, но не кратный кирпичу. Упаковка $2\cdot 3$ кирпич в $5\cdot 6$ во вставке приводится пример этого явления. ^[1]

В двумерном случае третий результат де Брейна легко визуализировать. Коробка с размерами $A_{1}=a_{1}$ и $A_{2}=a_{1}\cdot a_{2}$ легко упаковать $a_{1}$ копии кирпича с размерами $a_{1},a_{2}$ , расположенные рядом. По этой же причине коробка с размерами $A_{1}=a_{1}\cdot a_{2}$ и $A_{2}=a_{2}$ также легко упаковать копии одного и того же кирпича. Поворот одной из этих двух коробок так, чтобы их длинные стороны были параллельны, и размещение их рядом друг с другом приводит к упаковке большей коробки с $A_{1}=a_{1}+a_{2}$ и $A_{2}=a_{1}\cdot a_{2}$ . Эта большая коробка кратна кирпичу тогда и только тогда, когда кирпич гармоничен.

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и де Брейн, Н.Г. (1969), «Наполнение коробок кирпичами» , The American Mathematical Monthly , 76 (1): 37–40, doi : 10.2307/2316785 , JSTOR 2316785 , MR 0234841 .
^ Хонсбергер, Росс (1976), Mathematical Gems II , Вашингтон, округ Колумбия: Математическая ассоциация Америки, стр. 69, ISBN 9780883853009 .
^ Ниенхейс, JW (11 сентября 2011 г.), Клокс, Тон; Хунг, Лин-Джу (ред.), Комбинаторика Де Брейна: конспекты занятий , стр. 156 .
^ Уоткинс, Джон Дж. (2012), Через доску: Математика задач на шахматной доске , Princeton University Press, стр. 226, ISBN 9781400840922 .
^ Крех, RT (2003), Навыки каменной кладки (5-е изд.), Cengage Learning, с. 18, ISBN 9780766859364 .
^ Штейн, Шерман К .; Сабо, Шандор (1994), Алгебра и мозаика: гомоморфизмы на службе геометрии , Математические монографии Каруса, том. 25, Вашингтон, округ Колумбия: Математическая ассоциация Америки, с. 52 , ISBN 0-88385-028-1 , МР 1311249 .
^ Бойзен, Пол (1995), «Полиномы и упаковки: новое доказательство теоремы де Брёйна», Discrete Mathematics , 146 (1–3): 285–287, doi : 10.1016/0012-365X(94)00070-1 , MR 1360122 .

Внешние ссылки

Вайсштейн, Эрик В. , «Теорема де Брёйна» , MathWorld

[db69-1] Jump up to: ^а ^б ^с ^д ^и де Брейн, Н.Г. (1969), «Наполнение коробок кирпичами» , The American Mathematical Monthly , 76 (1): 37–40, doi : 10.2307/2316785 , JSTOR 2316785 , MR 0234841 .

[2] Хонсбергер, Росс (1976), Mathematical Gems II , Вашингтон, округ Колумбия: Математическая ассоциация Америки, стр. 69, ISBN 9780883853009 .

[3] Ниенхейс, JW (11 сентября 2011 г.), Клокс, Тон; Хунг, Лин-Джу (ред.), Комбинаторика Де Брейна: конспекты занятий , стр. 156 .

[4] Уоткинс, Джон Дж. (2012), Через доску: Математика задач на шахматной доске , Princeton University Press, стр. 226, ISBN 9781400840922 .

[5] Крех, RT (2003), Навыки каменной кладки (5-е изд.), Cengage Learning, с. 18, ISBN 9780766859364 .

[6] Штейн, Шерман К .; Сабо, Шандор (1994), Алгебра и мозаика: гомоморфизмы на службе геометрии , Математические монографии Каруса, том. 25, Вашингтон, округ Колумбия: Математическая ассоциация Америки, с. 52 , ISBN 0-88385-028-1 , МР 1311249 .

[7] Бойзен, Пол (1995), «Полиномы и упаковки: новое доказательство теоремы де Брёйна», Discrete Mathematics , 146 (1–3): 285–287, doi : 10.1016/0012-365X(94)00070-1 , MR 1360122 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]