## Container Packing Problem

Arrangements, combinations and permutations, probability, ...
Holbi2004
Posts: 4
Joined: Tue May 01, 2018 7:01 pm

### Container Packing Problem

In how many different ways can 24 identical boxes (cuboids), each measuring 1 x 1 x 2 be packed into a single (cuboid) container measuring 2 x 2 x 12?

This is a math problem from school to which I do not have a clue. I tried to define possible sub-arrangements of two 1 x 1 x 2 cuboids and tried finding possible combinations for these but that didn´t really help. (I assume that arrangements that can be found by tilting
or turning the container are not counted).
Thanks!
Holbi

v6ph1
Posts: 113
Joined: Mon Aug 25, 2014 6:14 pm

### Re: Container Packing Problem

4541161

Try to solve it layer by layer.

I checked the options for a 2x2 layer (At which of the 4 positions the cuboid connects the current and the next layer)
Only 6 types of the 16 layer types are relevant.
And after this: Matrix multiplication n(12) times.

If mirror and rotation should not count, you should generate the number of solutions which do not change after rotation or mirroring and subtract.

DJohn
Posts: 42
Joined: Sat Oct 11, 2008 11:24 am

### Re: Container Packing Problem

This is a simpler version of Problem 324 https://projecteuler.net/problem=324

Holbi2004
Posts: 4
Joined: Tue May 01, 2018 7:01 pm

### Re: Container Packing Problem

Appreciate your advice, thank you. Thus, I start in the first 2 x 2 layer of the 2 x 2 x 12 container. Some of the 2 x 1 x 1 elements will cross the first layer and protrude into the second layer. With 4 squares in the layer there are 4^2 = 16 possibilities for protrusions to the next layer. Considering rotational symmetry out of these 16 possibilities I am left with only six “relevant” for 0, 1, 2, 3 or 4 protrusions, respectively. But then you say “matrix multiplication n(12) times” and I´m lost because I haven´t heard of this at all (I´m grade 9). I can only think of working myself up the layers counting and combining previous combinations with the new set of combinations thereby trying to eliminate symmetries. In the end layer (24) I cannot have any protrusion. But this seems quite daunting. Can you give me a nudge in the right direction? Thanks.

v6ph1
Posts: 113
Joined: Mon Aug 25, 2014 6:14 pm

### Re: Container Packing Problem

If you have a layer with e.g. the left two elements going to the next layer, then the next layer has to be of a special kind:
Option 1: there is 1 element in the layer on the right side.
Option 2: there are 2 elements on the right side going to the next-next layer.
The 2 places at the left side are filled by the two elements of the layer before.

And therefore you can design a 16x16 transition matrix for each of the 16 options.
So you can calculate simultaneously the number of ways from a flat end to each of the 16 options with n layers.
You can simplify your calculation in a way that counts flat layers in both orientations but doesn't distinguish between them.

Holbi2004
Posts: 4
Joined: Tue May 01, 2018 7:01 pm

### Re: Container Packing Problem

Thank you, smart approach - understood. But rather than working with a transition matrix (I´m grade 9 and haven´t heard of such thing) I would try to formulate a recursive formulation taking me step wise from layer to layer thereby differentiating between the possible protrusions of 0, 2 or 4 cuboids sticking out into the next layer (if at all possible). I think I found the repeating pattern. For the last layer (that must finish flush with the container wall) there can be no protrusions and I will thus only consider the solution with 0 protrusion to the 25 layer. Does this make sense?