ド・ブリュインの定理

1969 年の論文で、オランダの数学者ニコラス・ゴバート・デ・ブリュインは、合同な長方形のブロック (任意の寸法) をより大きな長方形の箱に詰めて、空間を残さないようにすることに関するいくつかの結果を証明しました。これらの結果の 1 つは、現在ではデ・ブリュインの定理として知られています。この定理によると、「調和ブロック」(各辺の長さが次に短い辺の長さの倍数であるブロック) は、そのブロックの寸法の倍数である箱にのみ詰めることができます。^[1]

デ・ブリュインがこの結果を証明したのは、当時7歳だった息子のFW・デ・ブリュインが、ある次元のレンガを立方体に詰めることができなかったことがきっかけだった。^{[2] [3]}立方体の体積はレンガと同じだが、詰められるのはレンガだけである。これを確認する方法の1つは、立方体を同じ大きさの小さな立方体に分割し、交互に黒と白に色を塗ってみることである。この色分けでは一方の色のセルがもう一方の色よりも多くなるが、この色分けではレンガを配置する際に各色のセルの数が等しくなければならない。したがって、レンガでタイルを敷くと各色のセルの数が等しくなり、これは不可能である。^[4]デ・ブリュインの定理は、これらの次元で完全な詰め込みが不可能であることを、より一般的な方法で証明しており、これはレンガや箱の他の多くの次元にも当てはまる。 ${\displaystyle 1\cdot 2\cdot 4}$${\displaystyle 6\cdot 6\cdot 6}$${\displaystyle 27}$${\displaystyle 26}$${\displaystyle 27}$${\displaystyle 2\cdot 2\cdot 2}$${\displaystyle 1\cdot 2\cdot 4}$

次元の長方形の箱（数学的には直方体）の辺の長さが整数で、レンガの長さが であるとします。レンガの辺を別の整数の集合で乗算して がの順列になる場合、その箱はレンガの倍数と呼ばれます。その場合、すべてのレンガを同じ方向に向ければ、箱はそのようなレンガで簡単に埋めることができます。^[1]${\displaystyle d}$${\displaystyle A_{1}\cdot A_{2}\cdot \dotso \cdot A_{d}}$${\displaystyle a_{1}\cdot a_{2}\cdot \dotso \cdot 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}}$

すべてのパッキングがレンガの倍数である箱を必要とするわけではありません。例えば、de Bruijn が指摘しているように、長方形の箱は長方形のレンガのコピーで埋めることができますが、すべてのレンガが同じ方向に向いているわけではありません。しかし、de Bruijn (1969) は、レンガが箱を埋めることができる場合、それぞれについて少なくとも 1 つは倍数であることを証明しています。上記の例では、長さの辺はとの両方の倍数です。^[1]${\displaystyle 5\cdot 6}$${\displaystyle 2\cdot 3}$${\displaystyle a_{i},}$${\displaystyle A_{i}}$${\displaystyle 6}$${\displaystyle 2}$${\displaystyle 3}$

de Bruijn の 2 番目の結果は、de Bruijn の定理と呼ばれ、レンガの各辺が次に小さい辺の整数倍である場合に関するものです。De Bruijn はこの特性を持つレンガを調和と呼んでいます。たとえば、米国で最も頻繁に使用されるレンガの寸法は(インチ単位) で、これは調和的ではありませんが、「ローマン レンガ」として販売されている種類のレンガは調和寸法 です。^[5]${\displaystyle 2{\tfrac {1}{4}}\cdot 4\cdot 8}$${\displaystyle 2\cdot 4\cdot 12}$

ド・ブリュインの定理によれば、調和ブリックをボックスに詰める場合、ボックスはブリックの倍数でなければならない。たとえば、辺の長さが 1、2、6 の 3 次元調和ブリックは、3 辺のうち 1 辺が 6 の倍数で、残りの 2 辺のうち 1 辺が偶数であるボックスにのみ詰めることができる。^{[1] [6]}調和ブリックをボックスに詰めるには、ブリックのコピーを互いに回転させる必要がある。ただし、この定理によれば、このように詰めることができるボックスは、ブリックを平行移動させることによっても詰めることができるボックスのみである。

ボイセン（1995）は、多項式代数に基づいて、3次元の場合のド・ブリュイン定理の別の証明を提供した。^[7]

de Bruijn の 3 つ目の結果は、レンガが調和的でない場合、レンガの倍数ではない箱を埋めることができるというものです。レンガを箱に詰め込むことは、この現象の例を示しています。^[1]${\displaystyle 2\cdot 3}$${\displaystyle 5\cdot 6}$

2 次元の場合、de Bruijn の結果の 3 つ目は簡単に視覚化できます。次元が と のボックスは、隣り合わせに配置された次元 のブリックのコピーで簡単にパックできます。同じ理由で、次元が と のボックスも同じブリックのコピーで簡単にパックできます。これらの 2 つのボックスのいずれかを回転して長辺が平行になるようにし、隣り合わせに配置すると、とのより大きなボックスがパックされます。この大きなボックスは、ブリックが調和的である場合に限り、ブリックの倍数になります。 ${\displaystyle A_{1}=a_{1}}$${\displaystyle A_{2}=a_{1}\cdot a_{2}}$${\displaystyle a_{1}}$${\displaystyle a_{1},a_{2}}$${\displaystyle A_{1}=a_{1}\cdot a_{2}}$${\displaystyle A_{2}=a_{2}}$${\displaystyle A_{1}=a_{1}+a_{2}}$${\displaystyle A_{2}=a_{1}\cdot a_{2}}$

• Weisstein、Eric W.、「de Bruijn's Theorem」、MathWorld