Hoffman's packing puzzle

Last updated
A solution to Hoffman's packing puzzle with 4x5x6 cuboids coloured by orientation (1), and exploded to show each layer (2). In the SVG file, hover over the cuboids for their dimensions. Hoffman packing puzzle.svg
A solution to Hoffman's packing puzzle with 4×5×6 cuboids coloured by orientation (1), and exploded to show each layer (2). In the SVG file, hover over the cuboids for their dimensions.
Hoffman's packing puzzle, disassembled HoffmansPackingPuzzle.jpg
Hoffman's packing puzzle, disassembled

Hoffman's packing puzzle is an assembly puzzle named after Dean G. Hoffman, who described it in 1978. [1] The puzzle consists of 27 identical rectangular cuboids, each of whose edges have three different lengths. Its goal is to assemble them all to fit within a cube whose edge length is the sum of the three lengths. [2] [3]

Contents

Hoffman (1981) writes that the first person to solve the puzzle was David A. Klarner, and that typical solution times can range from 20 minutes to multiple hours. [2]

Construction

The puzzle itself consists only of 27 identical rectangular cuboid-shaped blocks, although physical realizations of the puzzle also typically supply a cubical box to fit the blocks into. If the three lengths of the block edges are x, y, and z, then the cube should have edge length x + y + z. Although the puzzle can be constructed with any three different edge lengths, it is most difficult when the three edge lengths of the blocks are close enough together that x + y + z < 4 min(x,y,z), as this prevents alternative solutions in which four blocks of the minimum width are packed next to each other. Additionally, having the three lengths form an arithmetic progression can make it more confusing, because in this case placing three blocks of the middle width next to each other produces a row of the correct total width but one that cannot lead to a valid solution to the whole puzzle. [2]

Mathematical analysis

Each valid solution to the puzzle arranges the blocks in an approximate 3 × 3 × 3 grid of blocks, with the sides of the blocks all parallel to the sides of the outer cube, and with one block of each width along each axis-parallel line of three blocks. Counting reflections and rotations as being the same solution as each other, the puzzle has 21 combinatorially distinct solutions. [2] [4]

The total volume of the pieces, 27xyz, is less than the volume (x + y + z)3 of the cube that they pack into. If one takes the cube root of both volumes, and divides by three, then the number obtained in this way from the total volume of the pieces is the geometric mean of x, y, and z, while the number obtained in the same way from the volume of the cube is their arithmetic mean. The fact that the pieces have less total volume than the cube follows from the inequality of arithmetic and geometric means. [2] [3]

Table of solutions

The 21 distinct solutions are tabulated here as described by the references cited above [2] [4] .

All boxes below are entered in the format (east-west length) x (north-south length) x (up-down length), denoting the size of each box with the dimensions A, B, and C, where A < B < C. (In the above example, A = 4, B = 5, and C = 6).

All 3x3 matrices describe a set of 9 boxes, with east-west neighbors along each row and north-south neighbors down each column, with the three stacked layers being listed in sequence for each solution.

SolutionBottom layerMiddle layerTop layer
Solution 01CxBxA AxCxB BxAxC
BxCxA CxAxB AxBxC
AxCxB BxAxC CxBxA
CxAxB AxBxC BxCxA
AxBxC BxAxC AxCxB
BxCxA CxBxA CxAxB
BxAxC CxBxA AxCxB
CxAxB BxCxA CxBxA
AxBxC AxCxB BxAxC
Solution 02CxBxA AxCxB BxAxC
BxCxA CxAxB AxBxC
AxCxB BxAxC CxBxA
CxAxB AxBxC AxCxB
AxBxC BxAxC BxCxA
BxCxA CxBxA CxAxB
BxAxC BxCxA CxBxA
CxAxB CxBxA AxCxB
AxBxC AxCxB BxAxC
Solution 03CxBxA AxCxB BxAxC
BxCxA CxAxB AxBxC
AxCxB BxAxC CxBxA
AxBxC BxAxC BxCxA
CxAxB AxBxC AxCxB
BxCxA CxBxA CxAxB
CxAxB CxBxA AxCxB
BxAxC BxCxA CxBxA
AxBxC AxCxB BxAxC
Solution 04CxBxA AxCxB BxAxC
BxCxA CxAxB AxBxC
AxCxB BxAxC CxBxA
AxBxC BxAxC AxCxB
CxAxB AxBxC BxCxA
BxCxA CxBxA CxAxB
CxAxB BxCxA CxBxA
BxAxC CxBxA AxCxB
AxBxC AxCxB BxAxC
Solution 05CxBxA AxCxB CxAxB
BxCxA CxBxA BxAxC
AxCxB BxAxC AxBxC
AxBxC BxCxA BxAxC
BxAxC AxCxB CxBxA
CxBxA CxAxB AxCxB
AxCxB BxAxC CxBxA
CxAxB AxBxC AxCxB
BxAxC CxBxA BxCxA
Solution 06CxBxA AxCxB CxAxB
BxCxA CxBxA BxAxC
AxCxB BxAxC AxBxC
AxBxC BxCxA BxAxC
CxAxB AxCxB CxBxA
BxAxC CxBxA AxCxB
AxCxB BxAxC CxBxA
BxAxC AxBxC AxCxB
CxBxA CxAxB BxCxA
Solution 07CxBxA AxCxB BxAxC
BxCxA CxBxA CxAxB
AxCxB BxAxC AxBxC
CxAxB CxBxA BxCxA
BxAxC AxCxB AxBxC
AxBxC BxCxA CxAxB
AxBxC BxAxC AxCxB
CxAxB AxBxC BxCxA
BxCxA CxAxB CxBxA
Solution 08CxBxA AxCxB BxAxC
BxCxA CxBxA CxAxB
AxCxB BxAxC AxBxC
BxAxC CxBxA BxCxA
CxAxB AxCxB AxBxC
AxBxC BxCxA CxAxB
CxAxB AxBxC AxCxB
AxBxC BxAxC BxCxA
BxCxA CxAxB CxBxA
Solution 09CxBxA AxCxB BxAxC
BxCxA CxBxA CxAxB
AxCxB BxAxC AxBxC
AxBxC BxCxA CxAxB
BxAxC AxCxB AxBxC
CxBxA CxAxB BxCxA
AxCxB BxAxC CxBxA
CxAxB AxBxC BxCxA
BxAxC CxBxA AxCxB
Solution 10CxBxA AxCxB BxAxC
BxCxA CxBxA CxAxB
AxCxB BxAxC AxBxC
AxBxC BxCxA CxAxB
CxAxB AxCxB AxBxC
BxAxC CxBxA BxCxA
AxCxB BxAxC CxBxA
BxAxC AxBxC BxCxA
CxBxA CxAxB AxCxB
Solution 11CxBxA AxCxB BxAxC
BxCxA BxAxC AxBxC
AxCxB CxBxA CxAxB
CxAxB AxBxC BxCxA
AxBxC CxAxB AxCxB
BxCxA BxAxC CxBxA
BxAxC CxBxA AxCxB
CxAxB BxCxA CxBxA
AxBxC AxCxB BxAxC
Solution 12CxBxA AxCxB BxAxC
BxCxA BxAxC AxBxC
AxCxB CxBxA CxAxB
CxAxB AxBxC AxCxB
AxBxC CxAxB BxCxA
BxCxA BxAxC CxBxA
BxAxC BxCxA CxBxA
CxAxB CxBxA AxCxB
AxBxC AxCxB BxAxC
Solution 13CxBxA AxCxB BxAxC
BxCxA BxAxC AxBxC
AxCxB CxAxB CxBxA
CxAxB AxBxC AxCxB
AxBxC BxCxA CxAxB
BxCxA CxBxA BxAxC
BxAxC CxBxA BxCxA
CxAxB AxCxB CxBxA
AxBxC BxAxC AxCxB
Solution 14CxBxA AxCxB BxAxC
BxCxA BxAxC AxBxC
AxCxB CxAxB CxBxA
BxAxC AxBxC AxCxB
AxCxB CxBxA CxAxB
CxBxA BxCxA BxAxC
CxAxB CxBxA BxCxA
BxAxC AxCxB CxBxA
AxBxC BxAxC AxCxB
Solution 15CxBxA BxCxA CxAxB
BxCxA CxAxB AxBxC
AxCxB AxBxC BxAxC
CxAxB AxBxC BxCxA
AxBxC BxAxC AxCxB
BxCxA CxBxA CxAxB
BxAxC AxCxB AxBxC
CxAxB BxCxA CxBxA
AxBxC CxAxB BxCxA
Solution 16CxBxA BxCxA CxAxB
BxCxA CxAxB AxBxC
AxCxB AxBxC BxAxC
CxAxB AxBxC BxCxA
AxBxC BxAxC AxCxB
BxCxA CxAxB CxBxA
BxAxC AxCxB AxBxC
CxAxB CxBxA BxCxA
AxBxC BxCxA CxAxB
Solution 17CxBxA BxCxA CxAxB
BxCxA CxAxB AxBxC
AxCxB AxBxC BxAxC
CxAxB AxCxB AxBxC
AxBxC BxAxC BxCxA
BxCxA CxAxB CxBxA
BxAxC AxBxC BxCxA
CxAxB CxBxA AxCxB
AxBxC BxCxA CxAxB
Solution 18CxBxA BxCxA CxAxB
BxCxA CxAxB AxBxC
AxCxB AxBxC BxAxC
BxAxC AxCxB AxBxC
CxAxB BxCxA CxBxA
AxBxC CxAxB BxCxA
CxAxB AxBxC BxCxA
AxBxC BxAxC AxCxB
BxCxA CxBxA CxAxB
Solution 19CxBxA BxCxA CxAxB
BxCxA CxAxB AxBxC
AxCxB AxBxC BxAxC
AxCxB BxAxC CxBxA
BxAxC AxBxC BxCxA
CxBxA CxAxB AxCxB
AxBxC AxCxB BxAxC
CxAxB CxBxA AxCxB
BxAxC BxCxA CxBxA
Solution 20CxBxA BxCxA CxAxB
BxCxA CxAxB AxBxC
AxCxB AxBxC BxAxC
AxCxB BxAxC CxBxA
BxAxC AxBxC AxCxB
CxBxA CxAxB BxCxA
AxBxC AxCxB BxAxC
CxAxB BxCxA CxBxA
BxAxC CxBxA AxCxB
Solution 21CxBxA BxCxA CxAxB
BxCxA CxAxB AxBxC
AxCxB AxBxC BxAxC
AxBxC AxCxB BxAxC
BxAxC BxCxA CxBxA
CxBxA CxAxB AxCxB
AxCxB BxAxC CxBxA
CxAxB AxBxC AxCxB
BxAxC CxBxA BxCxA

Higher dimensions

Solution to the 2d puzzle AM-GM inequality.svg
Solution to the 2d puzzle

A two-dimensional analogue of the puzzle asks to pack four identical rectangles of side lengths x and y into a square of side length x + y; as the figure shows, this is always possible. In d dimensions the puzzle asks to pack dd identical blocks into a hypercube. By a result of Raphael M. Robinson this is again solvable whenever d = d1 × d2 for two numbers d1 and d2 such that the d1- and d2-dimensional cases are themselves solvable. For instance, according to this result, it is solvable for dimensions 4, 6, 8, 9, and other 3-smooth numbers. In all dimensions, the inequality of arithmetic and geometric means shows that the volume of the pieces is less than the volume of the hypercube into which they should be packed. However, it is unknown whether the puzzle can be solved in five dimensions, or in higher prime number dimensions. [2] [5]

Related Research Articles

Cube Solid object with six equal square faces

In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex.

Pentomino Geometric shape formed from five squares

Derived from the Greek word for '5', and "domino", a pentomino is a polyomino of order 5, that is, a polygon in the plane made of 5 equal-sized squares connected edge-to-edge. When rotations and reflections are not considered to be distinct shapes, there are 12 different free pentominoes. When reflections are considered distinct, there are 18 one-sided pentominoes. When rotations are also considered distinct, there are 63 fixed pentominoes.

Rubiks Cube 3-D combination puzzle

The Rubik's Cube is a 3-D combination puzzle originally invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik. Originally called the Magic Cube, the puzzle was licensed by Rubik to be sold by Ideal Toy Corp in 1980 via businessman Tibor Laczi and Seven Towns founder Tom Kremer. The cube was released internationally in 1980 and became one of the most recognized icons in popular culture. It won the 1980 German Game of the Year special award for Best Puzzle. As of January 2009, 350 million cubes had been sold worldwide, making it the world's bestselling puzzle game and bestselling toy.

Rhombicuboctahedron Archimedean solid with 26 faces

In geometry, the rhombicuboctahedron, or small rhombicuboctahedron, is an Archimedean solid with eight triangular, six square, and twelve rectangular faces. There are 24 identical vertices, with one triangle, one square, and two rectangles meeting at each one. The polyhedron has octahedral symmetry, like the cube and octahedron. Its dual is called the deltoidal icositetrahedron or trapezoidal icositetrahedron, although its faces are not really true trapezoids.

Tesseract Four-dimensional analogue of the cube

In geometry, the tesseract is the four-dimensional analogue of the cube; the tesseract is to the cube as the cube is to the square. Just as the surface of the cube consists of six square faces, the hypersurface of the tesseract consists of eight cubical cells. The tesseract is one of the six convex regular 4-polytopes.

Hypercube Convex polytope, the n-dimensional analogue of a square and a cube

In geometry, a hypercube is an n-dimensional analogue of a square and a cube. It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length. A unit hypercube's longest diagonal in n dimensions is equal to .

Squaring the square

Squaring the square is the problem of tiling an integral square using only other integral squares. The name was coined in a humorous analogy with squaring the circle. Squaring the square is an easy task unless additional conditions are set. The most studied restriction is that the squaring be perfect, meaning the sizes of the smaller squares are all different. A related problem is squaring the plane, which can be done even with the restriction that each natural number occurs exactly once as a size of a square in the tiling. The order of a squared square is its number of constituent squares.

Doubling the cube Ancient geometric construction problem

Doubling the cube, also known as the Delian problem, is an ancient geometric problem. Given the edge of a cube, the problem requires the construction of the edge of a second cube whose volume is double that of the first. As with the related problems of squaring the circle and trisecting the angle, doubling the cube is now known to be impossible to construct by using only a compass and straightedge, but even in ancient times solutions were known that employed other tools.

Mechanical puzzle Mechanically-interlinked pieces to be manipulated

A mechanical puzzle is a puzzle presented as a set of mechanically interlinked pieces in which the solution is to manipulate the whole object or parts of it. One of the most well-known mechanical puzzles is the Rubik's Cube, invented by the Hungarian architect Ernő Rubik in 1974. The puzzles are mostly designed for a single player where the goal is for the player to see through the principle of the object, not so much that they accidentally come up with the right solution through trial and error. With this in mind, they are often used as an intelligence test or in problem solving training.

Packing problems Problems which attempt to find the most efficient way to pack objects into containers

Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few containers as possible. Many of these problems can be related to real-life packaging, storage and transportation issues. Each packing problem has a dual covering problem, which asks how many of the same objects are required to completely cover every region of the container, where objects are allowed to overlap.

In geometry, the kissing number of a mathematical space is defined as the greatest number of non-overlapping unit spheres that can be arranged in that space such that they each touch a common unit sphere. For a given sphere packing in a given space, a kissing number can also be defined for each individual sphere as the number of spheres it touches. For a lattice packing the kissing number is the same for every sphere, but for an arbitrary sphere packing the kissing number may vary from one sphere to another.

Polycube Shape made from cubes joined together

A polycube is a solid figure formed by joining one or more equal cubes face to face. Polycubes are the three-dimensional analogues of the planar polyominoes. The Soma cube, the Bedlam cube, the Diabolical cube, the Slothouber–Graatsma puzzle, and the Conway puzzle are examples of packing problems based on polycubes.

Square-1 (puzzle) Shape-shifting puzzle similar to Rubiks Cube

The Square-1 is a puzzle similar to the Rubik's Cube. Its distinguishing feature among the numerous Rubik's Cube variants is that it can change shape as it is twisted, due to the way it is cut, thus adding an extra level of challenge and difficulty. The Super Square One and Square Two puzzles have also been introduced. The Super Square One has two additional layers that can be scrambled and solved independently of the rest of the puzzle, and the Square Two has extra cuts made to the top and bottom layer, making the edge and corner wedges the same size.

Megaminx Puzzle

The Megaminx or Mégaminx is a dodecahedron-shaped puzzle similar to the Rubik's Cube. It has a total of 50 movable pieces to rearrange, compared to the 20 movable pieces of the Rubik's Cube.

Rhombille tiling Tiling of the plane with 60° rhombi

In geometry, the rhombille tiling, also known as tumbling blocks, reversible cubes, or the dice lattice, is a tessellation of identical 60° rhombi on the Euclidean plane. Each rhombus has two 60° and two 120° angles; rhombi with this shape are sometimes also called diamonds. Sets of three rhombi meet at their 120° angles, and sets of six rhombi meet at their 60° angles.

Slothouber–Graatsma puzzle Three-dimensional packing problem

The Slothouber–Graatsma puzzle is a packing problem that calls for packing six 1 × 2 × 2 blocks and three 1 × 1 × 1 blocks into a 3 × 3 × 3 box. The solution to this puzzle is unique. It was named after its inventors Jan Slothouber and William Graatsma.

Steinmetz solid Intersection of cylinders

In geometry, a Steinmetz solid is the solid body obtained as the intersection of two or three cylinders of equal radius at right angles. Each of the curves of the intersection of two cylinders is an ellipse.

Combination puzzle

A combination puzzle, also known as a sequential move puzzle, is a puzzle which consists of a set of pieces which can be manipulated into different combinations by a group of operations. Many such puzzles are mechanical puzzles of polyhedral shape, consisting of multiple layers of pieces along each axis which can rotate independently of each other. Collectively known as twisty puzzles, the archetype of this kind of puzzle is the Rubik's Cube. Each rotating side is usually marked with different colours, intended to be scrambled, then 'solved' by a sequence of moves that sort the facets by colour. As a generalisation, combination puzzles also include mathematically defined examples that have not been, or are impossible to, physically construct.

In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels. Such a labeling is called a Hamming labeling; it represents an isometric embedding of the partial cube into a hypercube.

Kellers conjecture Geometry problem on tiling by hypercubes

In geometry, Keller's conjecture is the conjecture that in any tiling of n-dimensional Euclidean space by identical hypercubes, there are two hypercubes that share an entire (n − 1)-dimensional face with each other. For instance, in any tiling of the plane by identical squares, some two squares must share an entire edge, as they do in the illustration.

References

  1. Rausch, John, "Put-Together – Hoffman's Packing Puzzle", Puzzle World, archived from the original on 2019-11-17, retrieved 2019-11-16
  2. 1 2 3 4 5 6 7 Hoffman, D. G. (1981), "Packing problems and inequalities", in Klarner, David A. (ed.), The Mathematical Gardner, Springer, pp. 212–225, doi:10.1007/978-1-4684-6686-7_19
  3. 1 2 Alsina, Claudi; Nelsen, Roger B. (2015), "Problem 3.10", A Mathematical Space Odyssey: Solid Geometry in the 21st Century, Dolciani Mathematical Expositions, vol. 50, Mathematical Association of America, p. 63, ISBN   9780883853580
  4. 1 2 Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2004), Winning Ways for Your Mathematical Plays, vol. IV, A K Peters, pp. 913–915
  5. von Holck, Nikolaj Ingemann (January 2018), An Experimental Approach to Packing Problems (PDF), Bachelor's thesis, supervised by Søren Eilers, University of Copenhagen, archived (PDF) from the original on 2019-11-17, retrieved 2019-11-17