A packing game!

Question

Amy and Ben are playing a game which is suggested by a genie. Amy first chooses $a,b,c\in\mathbb{R}^+$. Then a empty cuboid box with internal measurements $a+b,b+c,c+a$, and infinite supply of cuboid blocks with measurements $a,b,c$ magically appeared with the aid of the genie. Ben has to pack as much cuboid blocks into the box as he can with no part of the cuboid blocks hanging outside the box. How many blocks can Ben guarantee to fit into the box despite the values Amy chooses?

---

Problem by myself.

Answer 1

With the following arrangement you can easily stack

6

pieces into the box:

I have assumed without loss of generality that $a<b<c$, but as Damien_The_Unbeliever noted in the comments, it also assumes that $a+b>c$. That does not matter however, as this arrangement can be tweaked to insert one more piece:

Turn the piece at the bottom left and the piece at the bottom right so that their longest dimension points to the empty rear corner. This allows the piece at the front to be laid flat and makes room for another piece in the front corner.

If $a+b\le c$, then the piece at the back will not fit vertically. However, in that case we have $2a+b \le c+a$, so the gap between the pieces at the front left is wide enough to hold that piece instead. Thanks to Paul Panzer for pointing this out in the comments below.

Now it just remains to be proved that it is impossible to improve it further. I don't have a good proof of that yet, only this observation:

It would mean having 8 pieces. Note that all 12 edges of the box will have to be fully used (each piece uses up a length of $a+b+c$, and the total length of the edges of the box is exactly $8$ times that much.

Answer 2

Almost complete answer using Jaap's lower bound, i.e. ignore my lower bound and skip the first two blocks:

I'm sure it's $\ge 6$

Let's assume $a\ge b\ge c$. Then we can on the $a+b \times a+c$ floor place four small cuboids, two of them with their $a \times b$ face down, two of them with their $c \times a$ face down. As $a$ is the longest side this can be done in a "swirl" pattern leaving a small $a-b \times a-c$ rectangle free in the center. As the $a \times b$ face down cuboids are only $c$ high we can stack two of them on each spot, and that is six altogether.

Now that @Jaap Scherphuis has bumped the lower bound to

$7$

It remains to be shown that Amy can choose in such a way that more becomes impossible.

Choose $0<\epsilon<<1$ and $a,c = 1\pm\epsilon$, $b=1$ Assume to reach a contradiction that we can fit $8$ pieces.

Comparing to $\epsilon=0$ it should be possible (but rather too technical for me to bother carrying it out) to make a continuity argument that if there is a packing of eight we can assume all cubes to be parallel to the principal axes and the small boxes to be placed in the eight corners of the large one. In that case the only choices left is how for each small cube its dimensions $a,b,c$ map to $x,y,z$ and as pointed our by Jaap the total length of small box edges lining up with large box edges is equal to the latters' total length, so there is no wiggle room in that respect. Let us note for later use that this implies that along each of the four $a+b$ edges of the large box we must have one $a$ and one $b$ small box edge, the same for $b+c$ and, finally, also for $a+c$ because the $b$ edges are already used up and there are only $a$'s and $c$'s left

Can we make a similar argument for the surface area of the faces? They are $4\pm2\epsilon$ and $4-\epsilon^2$ for the large and $1\pm\epsilon$ and $1-\epsilon^2$ for each of the small boxes. Summing yields no contradiction here, we in fact have a tiny bit of slack of $O(\epsilon^2)$. But using our note on edge placement we find that the $a+b \times b+c$ face of the large box is tiled by two $a\times b$ and two $b\times c$ faces which is impossible since their areas sum to $4$ which is too large by $\epsilon^2$.

Note that the last argument does not really rely on our specific choices of $a,b,c$ other than $a>b>c$. The sole purpose of the specific choice was to enable the continuity argument which we did not even carry out.

Answer 3

I think it's

5

Reasoning:

Split the box into the 8 regions defined by the borders between the addition factors on each side, ie one border between a and b on the x-axis and so on (this would be so much easier to explain with an image...but I don't have the skills). This yields the following parallelogram regions:

1) An a x b x c volume. Let's consider this "base", ie what the box would be were it a x b x c
2) 3 volumes we can get by "extending the base" to each dimension, ie x: extend a to a+b, y:extend b to b+c, z: extend c to c+a. The new volumes have sizes b x b x c, c x c x a, a x a x b
3) 3 areas we cat get by extending each of the previous step's volume to the final cube's size. The new volumes have sizes a x b^2, b x c^2, c x a^2
4) What remains is another a x b x c volume

So, we have:

2 from the volumes of points 1 and 4 that are exactly a x b x c

For the rest 6 areas, notice that there are always two dimension sizes which equal the given abc sample-to-fit. So, how many samples can we fit in one of those? The answer is floor({dimension of sample not present in volume's size}/{dimension of volume not used in sample's size}). Example: The bxbxc volume has a bxc common term with the sample. So, we can fit floor(a/b) samples within this.

Due to symmetry, the 6 regions yield the 6 possible floor divisions: a/b, a/c, b/a, b/c, c/a, c/b. Without breaking generality, let's say a>=b>=c. Then, at least 3 of the aforementioned floors must be at least one. Thus, we got another 3 from these regions.

Which also leads to Amy's tactic:

In order to minimize samples, she must have a,b,c all differ from one another but not so much that any is double (or more) times any of the others. Ie, she must choose (a,b,c) be like (a,a+x,a+y), x<>y, x,y within (0,1)

Answer 4

Answer: (2 + (b-c)/c) + (2 + (b-c)/c) + (1 + (a-b)/c) + (b+c)/a (of course, using integer arithmetic only. no fractions)

Without loss of generality, we can assume (as George has done) a >= b >= c. The layout will be taken as (a+b) x (a+c) x (b+c) in x,y and z directions. A simple greedy stacking will try to keep axb on floor (x,y plane) as far as possible. Then axc, followed by bxc on floor.

1. axb on floor at origin. Stack along z axis. Total number = (b+c)/c = 2+(b-c)/c.
2. bxa on floor at starting at (a,0,0). Stack along z axis. Total number = (b+c)/c = 2+(b-c)/c
3. axc on floor starting at (0,a+c,0) Stack along y axis inwards. (height b now). Total number = 1 + (a-b)/c. Note: a-b is the space left of after 1 along y axis.
4. The last block bxc on floor starting at (a+b,a+c,0), the last bottom corner. Try stacking something with height a along z axis. Total number = (b+c)/a

So, minimum 5. Depending on values of a,b and c more can be fit. Example, 5,3,1 according to this strategy fits (2+2)+(2+2)+(1+2)+0 = 12 The same with 5,3,2 fits (2+0)+(2+0)+(1+1)+1 = 7. The last 1 is a bonus 2+3=5 (b+c=a).

Edit: While the overall steps remain the same, The solution wasn't fully greedy enough. Real greedy would repeat step 1 (a+c)/b times starting at (0,0,0), (0,b,0), (0,2b,0) etc. This leaves step 3 for (a+c)%b times. So answer is (a+c)/b [2+(b-c)/c] + [2+(b-c)/c] + [(a+c)%b]/c + (b+c)/a