300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | РусскийPacking©
This puzzle won/played: 4774/7172
Why should I read this "Food for Thought"?
Because you will be surprised.
After trying a few packing puzzles, which area of mathematics do you think is the most useful for solving them:
1) Algebra, 2) Probability Theory, 3) Geometry, 4) Number Theory, 5) Symmetries, 6) Another area?
What turns out to be most useful is to think about divisibility of numbers, especially divisibility by 2. This is a subject of Number Theory. The things we stack are geometric objects, but that does not mean that geometric knowledge is needed to solve the puzzles. From Geometry we need to know what the area of a square or rectangle is, but nothing more.
For some puzzles, thinking about symmetry is also very useful.
Quick hints
These are hints for those seeking help but who are not interested in the mathematical background.
- By looking at the numbers next to "This puzzle won/played" for each puzzle, check which ones are the easiest. Starting with the easiest puzzles is always a good idea, and will give you practice with handling the interface.
- The puzzles "2×3×3 1" and "2×3×3 2" are easily solved by trial and error.
- If your first try on the "1×7×10 1" puzzle is not successful, rotate the pieces on your next try.
- "1×7×7 1" is a puzzle where thinking about symmetry helps. The reason is that the cuboid (grid) has a square base with 4 equally long sides, and we have 4 long pieces of the same shape. One should therefore put them in symmetrically. There is only one purple square-shaped piece. To have a 90° rotationally symmetric solution, this piece must be in the middle. Any other place would break the 90° symmetry of the solution.
- The puzzles with darker buttons require more thinking. Start by fully understanding the "3×3×3 2" puzzle before advancing to 5×5×5 puzzles.
How can one solve these puzzles without trial and error?
Here are some hints:
- Split a hard problem into easier ones, i.e. into sub-goals. For example, to fill the whole cuboid, one needs to fill each layer.
- Arrange pieces in a symmetric way, especially if the cuboid is symmetric like a 3×3×3 cube or the 1×7×7 square-shaped cuboid.
- Make the most out of the given information. What are the sizes of the pieces? How many of them have the same shape?
The remainder of this "Food for Thought" has the goal of solving all puzzles without trial and error, by instead coming up with simple questions and answering them.
Definitions
For clarity, here are a few terms we will use to discuss packing problems:
Piece
One of the shapes which will be put together to form the larger solid.
An odd piece is a piece whose lengths are all odd, such as a 1×1×1 piece or a 1×3×5 piece.
A piece is even if it has at least two even lengths, such as 1×2×4 or 2×2×2.
Are all pieces either even or odd?
NO. A piece with exactly one even length, such as 1×2×3, does not fit either definition. In the following sections, we will focus on odd and even pieces.
Cuboid
While all the pieces are technically rectangular cuboids, we will use the term "cuboid" to refer specifically to the larger solid which we aim to create from multiple pieces by filling the grid.
Layer
A layer is a slice of thickness 1 in a direction parallel to a face of the cuboid. A 3×4×5 cuboid has 3 layers of size 4×5, 4 layers of size 3×5, and 5 layers of size 3×4.
How many layers does a 1×5×7 cuboid have?
It has one 5×7 layer, five 1×7 layers, and seven 1×5 layers. In total it has 1 + 5 + 7 = 13 layers.
Cube
Specifically, a 1×1×1 cube, not a larger cube. A 1×1×1 piece consists of 1 cube, while a 1×1×3 piece consists of 1 × 1 × 3 = 3 cubes.
Building Block
A few pieces attached to each other form a Building Block. Interesting building blocks will have a symmetry. For harder puzzles, several identical or mirror-identical building blocks plus a center piece will form the cuboid.
Strategy
Half of the solution of a difficult problem is to split the hard problem into smaller problems.
To do this, one should ask oneself simple questions. The following questions will be useful in solving the packing puzzles.
Can every cuboid be formed with pieces of size 1×2×2 ? For example, can a 3×3×3 cuboid be formed using only pieces of size 1×2×2 ?
NO. A 1×2×2 piece consists of an even number of cubes. Therefore, any number of 1×2×2 pieces will together have an even total number of cubes. Since a 3×3×3 cuboid consists of an odd number of cubes, it cannot be formed in this way.
In the next few sections, we will explore how divisibility, especially by 2, determines how pieces must be placed to solve certain puzzles.
Can 1×2×2 pieces at least fill any layer of the 3×3×3 cuboid?
The answer is again NO. The area in a layer that can be occupied by a piece is the area of one of the faces of the piece, right?
What are the faces of a 1×2×2 piece?
A 1×2×2 piece has two pairs of parallel 1×2 faces, and one pair of 2×2 faces.
What are the areas of these faces, and what do the areas have in common?
The areas are 1 × 2 = 2 and 2 × 2 = 4. 2 and 4 are both even numbers.
We observe that a 1×2×2 piece can only occupy an even number of cubes (2 or 4) in each layer.
Is this true for all even pieces?
Each face of a piece has two lengths. Since even pieces have at most one odd length, then each of their faces will have at least one even length. Because even × odd = even, the area of each face will be even. This is why we call them even pieces!
We learned that cuboids with odd side lengths cannot be formed from only even pieces. A layer with odd area cannot be filled with even pieces either. Therefore, the puzzle "3×3×3 2" has a few 1×1×1 pieces, which are odd pieces.
Here is another helpful question to consider:
Is one of the two types of pieces (1×1×1 and 1×2×2) more 'precious' than the other?
YES. If we had only 1×1×1 pieces, then any puzzle would be trivial, do you agree? If we had only 1×2×2 pieces, then an odd cuboid could not be filled, as shown above.
The obvious question is: What is the minimum number of 1×1×1 pieces that makes the 3×3×3 cuboid possible?
Naturally, the next question arises:
Why are three 1×1×1 pieces enough?
To answer this question, we will compare the number of odd layers (layers with odd area) to the number of odd area layers that can be filled with even pieces and only 3 cubes.
How many layers does a 3×3×3 cuboid have?
In each of the three directions (width, height, depth), the cuboid has 3 layers. There are 3 + 3 + 3 = 9 odd layers that are filled when the cuboid is filled.
How many odd 3×3 layers can be completed with a single 1×1×1 piece (and some even 1×2×2 pieces)?
Three layers: the horizontal layer and the two vertical layers that contain the 1×1×1 piece. Therefore 3 cubes can help to fill at most 3 × 3 = 9 layers.
This shows that 3 cubes are necessary, and because the "3×3×2 2" puzzle is solvable, 3 cubes are also sufficient to fill the 9 odd layers.
What does that tell us about the location of the 3 cubes?
In each of the 9 layers there can only be 1 cube, not 0 cubes and not 2 cubes! Otherwise, 3 cubes would not be enough for the 9 layers.
This is the breakthrough for the solution. Furthermore, the only way to place the cubes is along a diagonal - with one cube in the center, and the other two cubes in diagonally opposite corners. Otherwise, the bulky 1×2×2 pieces would be too large to fill the space around the 3 cubes.
Therefore, put one cube in a corner, and three 1×2×2 pieces in a symmetric way around that cube. Put one cube in the center, one in the opposite corner, and the rest will be obvious.
What else can we learn from this solution? For example, does it have symmetries?
The symmetries are visible after placing the first cube in the corner and the three 1×2×2 pieces around it. The solution has a 120° rotational symmetry with the diagonal of the cube as a rotational axis (120° = 1/3 of the full circle rotation).
Is the solution the sum of identical or symmetric building blocks, each consisting of several pieces?
YES. The cuboid is the sum of 2 building blocks that are mirror symmetric (1 cube in a corner + three 1×2×2 pieces around it) and one cube in the middle.
Is there another way to solve this puzzle using different building blocks?
YES. The left and right images below show two mirror symmetric building blocks for the "3×3×3 2" puzzle. They can be combined with a center cube (middle image) to solve the puzzle.
Why should we bother to think about building blocks?
It is easier to use a small given number of pieces and create something symmetric from them, than to fill the larger cuboid with all the pieces.
Can building blocks be used to solve larger puzzles, such as "3×5×7 1" ?
YES. Larger cuboids, even if their lengths are all different, can be filled using identical/mirror symmetric building blocks. There are multiple ways of solving the "3×5×7 1" puzzle using building blocks and a center odd piece. We leave it to you to find some examples.
How do we know which pieces should make up a building block?
Let us think about the center of an odd cuboid first. Because the center position is unique, if we want a symmetric solution the center must be occupied by a piece with the same shape as the cuboid. The 3×3×3 cuboid is a cube so the center piece for that needs to be a cube. A 1×2×2 piece in the center would break the symmetry.
This means we have 6 yellow and 3 − 1 = 2 pink pieces to build a number of identical building blocks.
How many building blocks should we try to create?
The building blocks should form the cuboid minus the center piece. Therefore, the number of yellow pieces in a building block must be a divisor of 6 (the total number of yellow blocks) and the number of pink pieces of a building block needs to divide 2 (the number of pink cubes remaining after reserving one for the center).
Thus, the number N of identical building blocks is the greatest common divisor of the number of identical pieces, here 6 and 2, which is GCD(6,2) = 2. So, we should create a building block from 2 / 2 = 1 pink cube and 6 / 2 = 3 yellow blocks. This is what we did.
Summarize the mathematical algorithm to use it for larger puzzles.
For an odd cuboid:
- Align the odd pieces to make sure they are not overlapping in any layer. They should link one corner of the cuboid with the opposite corner of the cuboid. If the odd pieces are cubes, they form a diagonal. If the odd pieces are larger (1x1x3), then they form a non-straight diagonal.
- If there is only one type of even piece, then use them to fill up the cuboid.
- If there are different types of even pieces:
- Put aside the center odd piece. From the remaining pieces, find the greatest common divisor N of the numbers of pieces of the different types. N is the number of building blocks.
- Create N identical building blocks and put them together with the center piece in case of an odd cuboid.
While small puzzles may be easily solved by trial and error, this strategy does not work for larger puzzles. Our exploration of odd and even pieces reveals an important reason: the placement of odd pieces is crucial, as there are very few ways they can be correctly placed. Using trial and error, one can make a mistake right at the start and only realize that something went wrong after placing many pieces. This makes it incredibly difficult to determine what caused the error, so there is no usable feedback; the trial-and-error method is not effective for larger cuboids. Thinking is required.
Packing with only one type of piece
In this section we will explore the sizes of cuboids that can be filled with a single type of piece. This is a theoretical section, not needed for solving the puzzles above. This section does not require difficult math.
With enough 1×1×1 pieces, we can easily create a cuboid of any size. But what about other pieces, such as 2×3×4 or 1×2×5 pieces? There are two main questions to investigate. First, given the lengths of a piece and the lengths of a cuboid, how can we determine whether the cuboid can be created from copies of the piece? Second, how can we, starting from a single piece, generate the lengths of cuboids which can be formed? Throughout this section, we will consider simpler questions while exploring these two important problems.
Can a 2×6×10 cuboid be formed from only 1×2×5 pieces?
YES! Three 1×2×5 pieces can be placed side-by-side to form a 1×6×5 shape (3 × 2 = 6). We can then create a second 1×6×5 shape and combine them into a 1×6×10 shape. Finally, two 1×6×10 shapes can be placed together to form a 2×6×10 cuboid.
Is it possible to form a 10×12×14 cuboid using only pieces of size 2×5×6 ?
Hint
It is not necessary to imagine how the pieces would be arranged.
Another hint?
A 2×5×6 piece is the same as a 5×6×2 piece since it can be rotated.
Answer
YES. Since 10 / 5 = 2, 12 / 6 = 2, and 14 / 2 = 7, the larger cuboid can be thought of as a 2×2×7 arrangement of the 5×6×2 pieces. The pieces can all be placed with the same orientation.
How can we generalize these findings?
Suppose we have only pieces of size x × y × z. Then constructing a X × Y × Z cuboid is possible if there exist positive integers A, B, C such that Ax, By and Cz equal X, Y and Z in some order.
How many pieces will be used in this case?
We can arrange A pieces in one direction, B in another, and C in a third direction. In total A × B × C pieces will be used.
Why can Ax, By and Cz equal X, Y and Z in any order?
A cuboid of size X × Y × Z is the same as a Z × X × Y cuboid. The order of the lengths does not matter because the cuboid can be rotated.
Is it true that any cuboid formed from 1×2×3 pieces must have lengths A, B × 2, C × 3, for some positive integers A, B, C ?
NO. If all 1×2×3 pieces are oriented in the same direction, the cuboid will have size A × (B × 2) × (C × 3). But pieces can be oriented differently and still form a cuboid. For example, the 1×2×3 pieces can form a 1×5×6 cuboid, even though 1, 5 and 6 do not equal A, B × 2, and C × 3 in any order. Another example is the puzzle "1×7×10 1", which is composed of 1×2×5 pieces.
What is the relation between the piece's lengths and the cuboid's lengths in these two examples?
In both of these examples, one of the lengths of the cuboid is the sum of two of the piece's lengths. A different length of the cuboid is the LCM (Lowest Common Multiple) of the same two lengths of the piece. In the case of the 1×5×6 cuboid formed from 1×2×3 pieces, we have 1×5×6 = 1 × (2 + 3) × LCM(2,3). Similarly, 1×7×10 = 1 × (2 + 5) × LCM(2,5).
How can we use this fact to find a way of generating the lengths of cuboids which can be constructed from a given piece?
We start by representing the length of a piece as an ordered triple. For example, a 1×2×3 piece is represented by (1, 2, 3). Now, there are 3 operations we can repeatedly perform to give the lengths of cuboids which can be formed from this piece. They are:
- Change the order of the lengths. This is known as a permutation. In our case, it represents a rotation in 3-dimensional space. An example is
(1, 2, 3) → (2, 3, 1). - Multiply the lengths by positive integers A, B and C, respectively. This corresponds to forming a larger cuboid by placing A pieces in one direction, B in another direction, and C along the third direction. For example, we can multiply by 1, 4, and 3 to give (1, 2, 3) → (1 × 1, 4 × 2, 3 × 3) = (1, 8, 9).
- Replace two lengths with their sum and their LCM. This corresponds to forming a larger cuboid with pieces oriented in different directions. For example, choosing lengths 2 and 3, we would obtain (1, 2, 3) → (1, 2 + 3, LCM(2,3)) = (1, 5, 6).
Can one combine the pieces in a 4th way to produce a cuboid whose shape is different from the result of the 3rd operation?
YES. Consider a piece of size x × y × z. The third operation produces a cuboid of size x × (y + z) × LCM(y,z), where one length x is unchanged from the piece to the cuboid.
A similar but different way would be to put again LCM(y,z)/y many pieces next to each other and LCM(y,z)/y many pieces next to each other, like before, but now to rotate one set by 90° so that the two blocks have the same length LCM(y,z), but different heights. In mathematical terms, we are not attaching x × y × LCM(y,z) and x × z × LCM(y,z) to form x × (y + z) × LCM(y,z). Instead, one of them, say, x × z × LCM(y,z), is rotated to z × x × LCM(y,z) and then attached.
The rectangular base area is then not (y + z) × LCM(y,z), but rather (x + z) × LCM(y,z). Then the two building blocks x × y × LCM(y,z) and z × x × LCM(y,z) have lengths x and z, respectively, in the X-direction.
Stacking LCM(x,z)/x many building blocks of height x and LCM(x,z)/z many building blocks of height z, both stacks reach height LCM(x,z). When they are attached, the result is a cuboid of size LCM(x,z) × (x + z) × LCM(y,z), which has a different shape and size than any cuboid resulting from the third operation.
One can repeat these operations in any order, first generating a cuboid from a piece, and then using the cuboid as a "piece" to generate an even larger cuboid. We discussed earlier how a 2×6×10 cuboid can be formed from 1×2×5 pieces. In this case only one operation is needed, multiplying by 2, 3 and 2, respectively: (1, 2, 5) → (2 × 1, 3 × 2, 2 × 5) = (2, 5, 10).
Thus, pieces of size x × y × z can not only construct cuboids of size Ax × By × Cz but, for example, also with size x × (y + z) × LCM(y,z), where LCM(y,z) is the Lowest Common Multiple of y and z. Putting several of these building blocks together gives cuboids of size Ax × B(y + z) + C(LCM(y,z)).
We will now consider a special type of piece. A piece is harmonic if each of its larger lengths is divisible by the next smaller length. For example, a 1×2×6 piece is harmonic since 2 / 1 = 1 and 6 / 2 = 3. A 1×4×6 piece is not harmonic since 6 is not a multiple of 4.
Is a 1×2×3 piece harmonic?
NO, because 3 is not divisible by 2.
What makes harmonic pieces special in packing? How do they relate to our discussion of the lengths of pieces and cuboids?
We already observed that any piece can form a cuboid whose lengths are multiples of the piece’s lengths. It turns out that the lengths of any cuboid formed by identical harmonic pieces must be multiples of the pieces' lengths. That is, if a harmonic piece has lengths x, y and z, any cuboid formed from copies of this piece must have one length divisible by x, another divisible by y, and the third divisible by z. While this is a simple statement, the proof requires concepts beyond the scope of this article. A link to the proof can be found in the "Acknowledgement" section.
How is this fact consistent with the four operations we discussed above?
We can start by thinking of a piece as also a cuboid formed from one copy of the piece. An x × y × z piece is also an x × y × z cuboid. The lengths of this cuboid are multiples of the piece's lengths, since every number is a multiple of itself. We will show why the four methods we introduced produce cuboids whose lengths are still multiples of the piece's lengths.
- Changing the order of the lengths (permutation): this is simply a rotation, and does not actually change the lengths of the cuboid. The lengths of the cuboid will still be multiples of the piece's lengths.
- Multiplying the lengths of the cuboid by positive integers: if the lengths of the cuboid are already multiples of the piece's lengths, this will not change. They will simply become larger multiples. If X = Ax is a multiple of x, then DX = DAx is also a multiple of x, for any positive integer D.
- Replacing two lengths by their sum and LCM: this is why harmonic pieces are important; we will need to use the definition of harmonic pieces. Suppose we started with a harmonic piece (x, y, z), from which we have already formed the cuboid (Ax, By, Cz). The order of the lengths does not matter since the cuboid can be rotated. We will now perform the third operation on any two of the cuboid's lengths, say Ax and By: (Ax, By, Cz) → (Ax + By, LCM(Ax,By), Cz). Now, since the piece (x, y, z) is harmonic, one of the two lengths x and y is a multiple of the other. Suppose y is a multiple of x. Therefore, By is also a multiple of x, and since Ax is as well, the sum Ax + By is a multiple of x. Next, LCM(Ax,By) is the lowest common multiple of Ax and By, so it is by definition a multiple of By, hence it is divisible by y. Finally, Cz is, of course, a multiple of z. Therefore, the lengths of the new cuboid (Ax + By, LCM(Ax,By), Cz) are still multiples of the piece's lengths.
- What about the fourth operation? Because this operation is similar to the third operation, the argument presented above can be adapted for this case. We leave it as an exercise.
We have shown that the four operations, performed repeatedly in any order on any harmonic piece, will result in a cuboid whose lengths are multiples of the piece's lengths. It is important to note that in our discussion of the third operation (and the fourth!), we rely on the fact that the piece is harmonic. When a piece is not harmonic, the argument fails. This is the key difference between harmonic and non-harmonic pieces. For harmonic pieces, the third and fourth methods do not produce extra shapes compared to the first two methods.
As a result, any cuboid formed from harmonic pieces can have all pieces in the same orientation. Therefore, if we are trying to form a cuboid from identical harmonic pieces, it is enough to try arranging them all facing in the same direction. If this is not possible, then the cuboid cannot be formed at all.
Since a 1×2×2 piece is harmonic, any cuboid formed from copies of this piece must have lengths A, B × 2, and C × 2 for some integers A, B, and C. The image below shows a 5×4×4 cuboid formed by 1×2×2 pieces, which all have the same orientation.
What are the values of A, B and C ?
Setting A, B × 2, and C × 2 equal to 5, 4, and 4, respectively, we find A = 5 / 1 = 1, B = 4 / 2 = 2, and C = 4 / 2 = 2.
When packing with harmonic pieces, do the pieces have to face the same direction?
NO! Although it is always possible for all pieces to have the same orientation, there may be other arrangements, but they do not form new shapes. The image below shows a different way to form a 5×4×4 cuboid from 1×2×2 pieces.
What are the rules for non-harmonic pieces?
When working with a non-harmonic piece x × y × z, there are some cuboids that can be formed whose sizes are not Ax × By × Cz for any integers A, B, C. For example, a 1×5×6 cuboid can be created from 1×2×3 pieces. This is a result of the third operation, as discussed earlier.
It is important to note that the number of cubes in the cuboid must always be divisible by the number of cubes in the piece. When the lengths of the cube are not each a multiple of a different length of the piece, one of the cuboid's lengths will be a common multiple of at least 2 lengths of the piece, due to the third and fourth methods. This fact can be used to determine whether certain cuboids can be formed from non-harmonic pieces.
Some questions to review what we have explored:
Can 2×4×12 pieces form a cuboid of size 4×8×36 ? What about a cuboid of size 10×10×12 ?
Since 4 / 2 = 2, 8 / 4 = 2, and 36 / 12 = 3, a 4×8×36 cuboid can be formed.
One of the lengths of a 10×10×12 cuboid is divisible by 12. The other lengths are 10 and 10, neither of which is divisible by 4. Therefore, the lengths of the 10×10×12 cuboid are not multiples of the piece's lengths. Since 12 / 4 = 3 and 4 / 2 = 2, the piece is harmonic, hence a 10×10×12 cuboid cannot be formed from pieces of size 2×4×12.
Can pieces of size 1×3×5 form a cuboid of size 2×15×8 ? What about a 3×9×14 cuboid?
Since 5 is not divisible by 3, the piece is not harmonic. We cannot apply our knowledge of harmonic pieces.
It is possible to form a 2×15×8 cuboid with these pieces. Three 1×3×5 pieces can form a 1×3×15 (or 1×15×3) shape, and 5 of the pieces arranged differently can form a 1×15×5 shape. These two shapes can be used to create a 1×15×8 cuboid, two of which can form a 2×15×8 cuboid. We can make use of the operations we discussed to be more concise: (1, 3, 5) → (1, 3 + 5, LCM(3,5)) = (1, 8, 15) → (2, 8, 15) → (2, 15, 8).
Whenever 1×3×5 pieces are combined, the total number of cubes is a multiple of 5. Since 3 × 9 × 14 is not divisible by 5, a 3×9×14 cuboid cannot be created from pieces of size 1×3×5.
Summary of rules for harmonic and non-harmonic pieces
Here is an overview of what we have learned:
- If a cuboid's lengths are multiples of a piece's lengths, then it can be formed from copies of that piece, regardless of whether the piece is harmonic. Such cuboids can be formed with all pieces in the same orientation, but there may also exist arrangements in which the pieces have different orientations.
- If a piece is harmonic, then any cuboid formed must have lengths that are multiples of the piece's lengths. As a result, any cuboid formed from harmonic pieces may have all pieces in the same orientation, though this is not always necessary.
- If a piece is not harmonic, there are some cuboids that can be formed whose lengths are not multiples of the piece's lengths (see the third and fourth operations). In this case, the pieces cannot all have the same orientation. We can give a simple description of how a cuboid can be formed from non-harmonic pieces, using the four operations we introduced.
Are these observations only valid in three dimensions?
NO. In this context, there is nothing special about 3 dimensions. In fact, setting one of the lengths equal to 1 is equivalent to reducing the problem to 2 dimensions. The results are also valid in more than 3 dimensions. For example, a 1×3×12×24 piece is harmonic. Therefore, any 4-dimensional cuboid formed from these 4-dimensional pieces must have dimensions A, B × 3, C × 12 and D × 24 for some positive integers A, B, C, and D.
How to get hands-on puzzles?
We cannot tell you how to make 4-dimensional pieces :) but in 3-dimensions if you have many spare dice, you can tape them together to form pieces.
Instead of a 5×5×5 box one could use, for example, a shoebox. If one holds it diagonally, the pieces will stay where they are placed.
Some of the puzzles have a height of 1 (for example, "1×7×10 1") and are therefore 2-dimensional puzzles. One can cut rectangles from graph paper to use as pieces for these puzzles.
Acknowledgement
Our interest in packing puzzles was ignited when seeing the wood version of puzzle "5x5x5 1" at a math exhibition. Following the reference to its author, the famous mathematician John Horton Conway, we found puzzles "3x3x3 2", "5x5x5 2", and "5x5x5 3" from him.
The "Packing with only one type of piece" section was inspired by the work of Dutch mathematician de Bruijn. To learn more about de Bruijn's observations on packing rectangular pieces, consult this article. You can read de Bruijn's proof of the properties of harmonic pieces here.
Theo dõi cập nhật sắp tới