300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | РусскийPacking©
Dieses Rätsel gewann/spielte: 4606/6928
The preparation of a proper "Food for Thought" section is underway. In the meantime here are some points to help you.
Definitions
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 dimensions are all odd, such as a 1x1x1 piece or a 1x3x5 piece.
A piece is even if it has at least two even dimensions, such as 1x2x4 or 2x2x2.
Are all pieces either even or odd?
No. A piece with exactly one even dimension, such as 1x2x3, does not fit either definition.
Cuboid
While all 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. Cuboids can be odd or even, like pieces.
Dimension
Any of the lengths of a piece or cuboid. A 1x1x2 piece has dimensions 1, 1, and 2. We will use D1, D2, D3 to represent the dimensions of a cuboid, and d1, d2, d3 for the dimensions of a piece.
Slice
A 'layer' of the cuboid in an orientation. A 3x4x5 cuboid has 3 slies of dimensions 4x5, 4 slices of dimensions 3x5, and 5 slices of dimensions 3x4.
Cube
A 1x1x1 cube. A 1x1x1 piece consists of 1 cube, while a 1x1x3 piece consists of 3 cubes.
Strategy
How can we place odd blocks first?
Some of the problems require is to construct odd cuboids, such as ones with dimensions 3x3x3 or 3x3x9. If one type of piece is odd, and all other types are even, we can find some restrictions on how the odd pieces must be placed. In the next few sections, we will derive these conditions.
How many cubes in a single slice can be occupied by a 1x2x4 piece?
When considering a slice in a cuboid, one of the cuboid's dimensions is replaced with 1, since a slice has thickness 1 in a certain dimension.
To find the number of cubes in a single slice occupied by a 1x2x4 piece, we can replace each dimension with 1. The three possibilities are 1x2x4 = 8, 1x1x4 = 4, or 1x2x1 = 2, coressponding to slices in different directions.
We can see that if a block has at least two even dimensions, it will contribute an even number of cubes to any slice, because there will always be at lest one even dimension left in the product. Even cubes occupy an even number of cubes in each slice.
What if all dimensions of a block are odd?
If all dimensions of a piece are odd, then since 1 is also odd, replacing any dimension with 1 will still give a product of odd numbers, which is odd. For example, a 1x1x3 block can occupy either 1 or 3 cubes in a slice.
How can we use this to place the odd pieces first?
When we are constructing a odd cuboid D1xD2xD3, each slice is composed of either D1xD2, D1xD3, or D2xD3 cubes, all of which are odd numbers.
An odd number cannot be expressed as a sum of even numbers. Adding an even number of odd numbers also results in an even number. To create an odd sum, there must be an odd number of odd terms. Therefore each slice must contain parts of an odd number of odd pieces.
In particular, since 0 is not odd, then each slice must contain part of at least one odd piece.
How many different slices will contain part of a 1x1x3 piece?
We can represent the position of a piece by the coordinates of the centers of its cubes in 3-dimensional space. A 1x1x3 piece can be placed along the x-axis so that the cubes have centers at (1, 1, 1), (2, 1, 1), and (3, 1, 1). Then choosing a slice is equivalent to fixing either the x-, y-, or z-coordinate. Since there are three x-coordinates, one y-coordinate and one z-coordinate, the 1x1x3 piece is in 3 + 1 + 1 = 5 different slices.
How many different slices will contain part of a d1xd2xd3 piece?
We can use the same argument as above to find that a d1xd2xd3 piece will be present in exactly d1 + d2 + d3 slices.
Using these observations, how can three 1x1x5 pieces be arranged to form a 3x7x11 cuboid if all other pieces are even?
The cuboid is odd, and exactly one type of piece is odd. Then, as we observed earlier, part of an odd number of these 1x1x5 piees must be present in each slice. Each 1x1x5 piece will occupy part of 1 + 1 + 5 = 7 slices. In total there are 3 + 7 + 11 = 21 slices. The three pieces can only contribute to all 21 slices if they are not present in any of the same slices.
Since there are 3 pieces and 3 11x7 slices, each 1x1x5 piece must be entirely within one 11x7 slice.
There are 11 slices of dimention 3x7. Recalling that a 1x1x5 piece can occupy either 1 or 5 cubes in a slice, there must be two pieces each present in 5 different 3x5 slices, and the remaining piece will be entirely within the remaining 3x7 slice.
Finally, there are 7 slices of dimension 3x11. One piece will occupy cubes in 5 of these slices. The other two pieces will each be in one of the remaining 3x11 slices.
What is a choice of coordinates for these pieces to satisfy the requirements we have just found?
There wre many correct answers; we will present one here. We label one corner cube of the cuboid (1, 1, 1), and the opposite corner (3, 7, 11), so that the cuboid has length 3 in the x-direction, 7 in the y-direction, and 11 in the z-direction.We determined earlier that each of the three 1x1x5 pieces must be entirely a different 7x11 slice. Therefore each piece must have a separate x-coordinate. Since two pieces will be present in 5 of the 11 3x7 slices, they must be parallel to the z-axis. One piece will be present in 5 of the 5 3x11 slices, and is therefore parallel to the y-axis.
We can choose the first piece to occupy the positions (1, 1, 1) to (1, 5, 1). This piece is parallel to the y-axis. The next piece can be placed from (2, 6, 2) to (2, 6, 6). Finally, the third piece will be placed from (3, 7, 7) to (3, 7, 11). Each slice contains an odd number of cubes from these three pieces (either 1 or 5). Then since each slice contains an odd total number of cubes, there are an even number of cubes left to fill in each slice. These will be filled by the even pieces.
What to do when there are no odd pieces left
Once the odd pieces have been placed, they may produce strange gaps that can only be filled in a specific way. In this case, it is a good idea to fill in these spots first. Whether the odd pieces have been placed already, or there were no odd pieces to begin with, it is a good strategy to work outwards from a single location, such as a corner. Placing pieces in separate areas of the cube is less and less likely to work as the size of the puzzle increases. In addition, when one gets stuck, it is impossible to draw any conclusions. Instead, working outwards from one area allows one to determine where certain pieces must be placed, and to note which piece caused trouble when gettin stuck.
Packing with only one type of piece
Can a 2x6x10 cuboid b formed from only 1x2x5 bricks?
Yes! Three 1x2x5 pieces can be placed side-by-side to form a 1x6x5 shape. We can then create a second 1x6x5 shape and combine them into a 1x6x10 shape. Finally, two 1x6x10 shapes can be placed together to form a 2x6x10 cuboid.
Is it possible to form a 10x12x14 cuboid using only pieces with dimensions 2x5x6?
Hint
It is not necessary to imagine how the pieces would be arranged.
Another hint?
A 2x5x6 piece is the same as a 5x6x2 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 2x2x7 arrangement of the 5x6x2 pieces.
How can we generalize these findings?
Suppose we have only pieces of dimensions d1xd2xd3. Then constructing a D1xD2xD3 cuboid is possible if there exist positive integers a1, a2, a3 such that a1d1, a2d2 and a3d3 equal D1, D2, and D3 in some order. The pieces can all be oriented in the same direction.
How many pieces will be used in this case?
There will be a1 pieces in one direction, a2 in another, and a3 in a third direction. In total a1 x a2 x a3 pieces will be used.
Why can a1d1, a2d2, a3d3 equal D1, D2, D3 in any order?
A D1xD2xD3 cuboid is the same as a D1xD3xD2 cuboid. The order does not matter because the cuboid can be rotated.
Is it true that any cuboid formed from 1x2x3 blocks must have dimensions a1, 2a2, 3a3 in some order, for some positive integers a,b,c?
No. Three 1x2x3 pieces can be used to create a 1x6x3 shape. Oriented differently, another two pieces can form a 1x2x6 shape, which can be rotated into 1x6x2. Placing these shapes side-by-side can result in a 1x6x5 cuboid. It is impossible to find 3 positive integers a1, a2, a3 such that a1, 2a2, and 3a3 are equal to 1, 5, and 6 (in any order).
Therefore, it is always possible to construct a cuboid of dimensions a1d1 x a2d2 x a3d3, but not all cuboids that can be constructed have dimensions a1d1xa2d2xa3d3.
We will now consider a special type of piece. A d1xd2xd3 piece is harmonic if each of its dimensions is divisible by the next smaller dimension. For example, a 1x2x6 block is harmonic since 2 / 1 = 1 and 6 / 2 = 3. A 1x4x6 block is not harmonic since 6 is not a multiple of 4.
Is a 1x2x3 piece harmonic?
No, because 3 is not divisible by 2.
How are harmonic pieces related to the observations above?
We already observed that any piece can form a cuboid whose dimensions are multiples of the piece’s dimensions. It turns out that the dimensions of any cuboid formed by identical harmonic pieces must be a multiples of the pieces dimensions. That is, if a harmonic piece has dimensions d1, d2, d3, any cuboid formed from copies of this piece must have one dimension divisible by d1, another divisible by d2, and the third divisible by d3.
Can 2x4x12 pieces form a cuboid of dimension 4x8x36? What about 10x10x12?
First, since 12 / 4 = 3 and 4 / 2 = 2, the 2x4x12 piece is harmonic.
Since 4/2 = 2, 8/4 = 2, and 36 / 12 = 3, then a 4x8x36 cuboid can be formed.
One of the dimensions of a 10x10x12 cuboid is divisible by 12. The other dimensions are 10 and 10, neither of which is divisible by 4. Therefore, it is not possible to construct a 10x10x12 cuboid from 2x4x12 pieces.
Can pieces of dimensions 1x3x5 form a cuboid of dimensions 2x15x8? What about a cuboid of dimensions 3x9x14?
Since 5 is not divisible by 3, the piece is not harmonic. We cannot apply the rules we have found for harmonic pieces.
It is possible to form a 2x15x8 cuboid. Three 1x3x5 pieces can form a 1x3x15 (or 1x15x3) shape, and 5 of the pieces arranged differently can form a 1x15x5 shape. These two shapes can be used to create a 1x15x8 cuboid, two of which can form a 2x15x8 cuboid.
Whenever 1x3x5 pieces are combined, the total number of cubes is a multiple of 5. Since 3x9x14 is not divisible by 5, it cannot be created from 1x3x5 pieces.
Summary of rules for harmonic and non-harmonic pieces
Knowing that a piece is harmonic can allow us to quickly rule out certain cuboids. If a piece is non-harmonic, we cannot immediately conclude whether a cuboid can be formed or not without thinking more carefully.
We can combine our results into the following true statement: Consider a piece of arbitrary dimensions. Then there exists a cuboid whose dimensions are not multiples of the pieces dimensions, which can be filled using only copies of the piece, if and only if the piece is not harmonic.
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 dimensions equal to 1 is equivalent to reducing the problem to 2 dimensions. The results discussed in this 'Packing with only one type of piece' section are valid in any number of dimensions. For example, a 1x3x12x24 piece is harmonic. Therefore any cuboid formed from these pieces must have dimensions a1, 3a2, 12a3 and 24a4 for some positive integers a1, a2, a3, a4. The positions of pieces in more than 3-dimensions can be represented by adding more coordinates. For example, a 1x1x1x2x4 piece could occupy the positions (1, 1, 1, 1, 1) to (1, 2, 1, 1, 4).
How to get hands-on puzzles?
If you have 125 spare dice then take a tape to bundle them to blocks.
Instead of a 5x5x5 box one could use, for example, a shoebox.
If one holds it diagonally then blocks stay where one puts them.
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 https://en.wikipedia.org/wiki/De_Bruijn%27s_theorem.
Folgen oder abonnieren für Updates: