Das Kriterium von N. de Bruijn für beliebige Klötzer

Kategorie: Gleiche Klötzer in rechtwinklige Boxen packen

Das Packproblem für harmonische Klötzer (das sind solche mit Seitenlängen a, ab und abc) in eine quaderförmige Box wird durch das Theorem von de Bruijn vollständig gelöst. Aber wie ist das mit allgemein Klötzern mit ganzzahliger Seitenlänge?

Der allgemeine Fall ist nicht vollständig gelöst, aber es gibt das folgende Kriterium von de Bruijn, welches erfüllt sein muss, damit es überhaupt möglich sein könnte, eine Box vollständig zu füllen.

Damit eine Box mit den Seitenlängen A, B und C sich vollständig mit Klötzern der Seitenlängen a, b und c füllen lässt, muss folgendes gelten:

• eine der Seitenlängen A, B und C ist ein ganzzahliges Vielfaches von a, 
• eine der Seitenlängen A, B und C ist ein ganzzahliges Vielfaches von b und 
• eine der Seitenlängen A, B und C ist ein ganzzahliges Vielfaches von c.

Dabei kann durchaus beispielsweise C Vielfaches sowohl von a und b sein und weder A noch B Vielfache von a oder b. So kann man fünf Klötzer der Größe 1x2x3 in eine Box der Größe 1x5x6 packen:

Hier haben die Seitenlängen 2 und 3 des Klotzes als gemeinsames Vielfaches die Seitenlänge 6 der Box.

Andererseits ist reicht das Kriterium nicht aus, um die Lösbarkeit auch sicherzustellen. Ein einfaches Gegenbeispiel dafür ist ein 1x2x3-Klotz, den man nicht in eine 1x1x6-Box packen kann, obwohl das Kriterium erfüllt ist.  

Mehr Infos: 

[1] Wikipedia