Twierdzenie De Bruijna
W artykule z 1969 roku holenderski matematyk Nicolaas Govert de Bruijn udowodnił kilka wyników dotyczących pakowania przystających prostokątnych cegieł (dowolnych wymiarów) do większych prostokątnych pudełek w taki sposób, że nie pozostaje żadne miejsce. Jeden z tych wyników jest obecnie znany jako twierdzenie de Bruijna . Zgodnie z tym twierdzeniem „cegła harmoniczna” (taka, w której długość każdego boku jest wielokrotnością następnej mniejszej długości boku) może być zapakowana tylko w pudełko, którego wymiary są wielokrotnością wymiarów cegły.
Przykład
De Bruijn udowodnił ten wynik po tym, jak jego wówczas siedmioletni syn FW de Bruijn nie był w stanie spakować cegieł o wymiarze do sześcian Kostka ma objętość równą objętości ale można w nią zmieścić tylko podzielenie sześcianu na mniejsze kostki o rozmiarze w kolorze na przemian czarnym i białym. To zabarwienie ma więcej komórek elementarnych jednego koloru drugiego, ale przy tym zabarwieniu każde umieszczenie cegły każdego koloru. Dlatego jakiekolwiek układanie płytek za pomocą cegieł miałoby również taką samą liczbę komórek każdego koloru, co jest niemożliwe. Twierdzenie De Bruijna dowodzi, że idealne upakowanie przy tych wymiarach jest niemożliwe, w bardziej ogólny sposób, który dotyczy wielu innych wymiarów cegieł i pudełek.
Pudełka, które są wielokrotnością cegły
Załóżmy, że prostokątne pudełko (matematycznie prostopadłościan ) ma całkowite długości boków , a cegła ma długości . Jeśli boki cegły można pomnożyć przez inny zestaw liczb całkowitych, 1 są permutacją ZA , pudełko nazywamy wielokrotnością cegły . Pudełko można następnie w banalny sposób wypełnić takimi klockami, ustawiając wszystkie klocki w ten sam sposób.
Uogólnienie
Nie każde opakowanie zawiera pudełka, które są wielokrotnością cegieł. Na przykład, jak zauważa de Bruijn, kopiami cegły są w ten sam sposób. Jednak de Bruijn (1969) udowadnia, że jeśli cegły mogą wypełnić pudełko, to dla każdego jeden z nich jest wielokrotnością . W powyższym przykładzie bok o długości wielokrotnością obu 3 .
Cegły harmoniczne
Drugi z wyników de Bruijna, zwany twierdzeniem de Bruijna, dotyczy przypadku, w którym każdy bok cegły jest całkowitą wielokrotnością następnego mniejszego boku. De Bruijn nazywa cegłę o tej właściwości harmoniczną . Na najczęściej używane w USA mają wymiary calach), , ale rodzaj cegły sprzedawanej jako „cegła rzymska” ma wymiary harmoniczne .
Twierdzenie De Bruijna mówi, że jeśli cegła harmoniczna jest zapakowana w pudełko, to pudełko musi być wielokrotnością cegły. Na przykład trójwymiarową cegłę harmoniczną o długościach boków 1, 2 i 6 można zapakować tylko w pudełka, w których jeden z trzech boków jest wielokrotnością sześciu, a jeden z pozostałych dwóch boków jest parzysty. Pakowanie cegły harmonicznej do pudełka może obejmować kopie cegły, które są obracane względem siebie. Niemniej jednak twierdzenie mówi, że jedynymi pudełkami, które można zapakować w ten sposób, są pudełka, które można również zapakować za pomocą translacji cegły.
Boisen (1995) dostarczył alternatywnego dowodu trójwymiarowego przypadku twierdzenia de Bruijna, opartego na algebrze wielomianów .
Cegły nieharmoniczne
Trzecim wynikiem de Bruijna jest to, że jeśli cegła nie jest harmoniczna, to istnieje pudełko, które może wypełnić, które nie jest wielokrotnością cegły. pakowanie cegły _
W przypadku dwuwymiarowym trzeci z wyników de Bruijna jest łatwy do wizualizacji. Pudełko o wymiarach i z cegły o wymiarach siebie Z tego samego powodu pudełko o wymiarach i jest również łatwy do spakowania z kopiami tego samego klocka. Obrócenie jednego z tych dwóch pudełek tak, aby ich długie boki były równoległe i umieszczenie ich obok siebie, daje w wyniku upakowanie większego pudełka z i . To większe pudełko jest wielokrotnością cegły wtedy i tylko wtedy, gdy cegła jest harmoniczna.