Container Packing Problem

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

Container Packing Problem

Post by Holbi2004 » Tue May 01, 2018 7:16 pm

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: 98
Joined: Mon Aug 25, 2014 6:14 pm

Re: Container Packing Problem

Post by v6ph1 » Tue May 01, 2018 9:30 pm

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.
Image

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

Re: Container Packing Problem

Post by DJohn » Wed May 02, 2018 11:08 am

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

Post by Holbi2004 » Wed May 02, 2018 3:38 pm

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: 98
Joined: Mon Aug 25, 2014 6:14 pm

Re: Container Packing Problem

Post by v6ph1 » Wed May 02, 2018 9:25 pm

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.
Image

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

Re: Container Packing Problem

Post by Holbi2004 » Thu May 03, 2018 4:01 pm

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?

Post Reply