11
$\begingroup$

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.

$\endgroup$
  • 15
    $\begingroup$ Thank you for letting Alice and Bob rest for the meantime. :P $\endgroup$ – oAlt Aug 3 at 6:50
  • $\begingroup$ Would you please mind telling what is the purpose of choosing one from a,b,c?? $\endgroup$ – Lakshay Sura Aug 3 at 7:25
  • $\begingroup$ WLOG, assume that a<b<c, and scale it down by the a = minimum of (a,b,c). Then the dimensions of blocks are 1,B,C, and of the box are (B+1),(B+C),(C+1). $\endgroup$ – smci Aug 3 at 17:09
7
$\begingroup$

With the following arrangement you can easily stack

6

pieces into the box:

enter image description here

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.
enter image description here
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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ One picture truly is 1000 words! $\endgroup$ – George Menoutis Aug 3 at 11:31
  • $\begingroup$ Doesn't that arrangement assume a+b must exceed c? Otherwise I have trouble seeing how that upright block at the front is fitting in height-wise. $\endgroup$ – Damien_The_Unbeliever Aug 3 at 15:56
  • $\begingroup$ @Damien_The_Unbeliever Suppose that our sides are of length $X$, $Y$ and $Z$. At least one of those must be less than the sum of the other two (i.e. if $X>Y+Z$, then $Y<X+Z$ and $Z<X+Y$, since our lengths cannot be negative) - so, we simply let that (or one of those) equal $c$. It is impossible to pick $X$, $Y$ and $Z$ such that $X+Y<Z$, $Y+Z<X$ and $Z+X<Y$ $\endgroup$ – Chronocidal Aug 3 at 16:00
  • 1
    $\begingroup$ @Chronocidal In the picture the remaining gap at the front corner has dimensions $(a+b-c)\times(b+c-a)\times(c+a-b)$, so one of them is always going to have that problem regardless of their ordering (I assumed $a<b<c$ for this picture). $\endgroup$ – Jaap Scherphuis Aug 3 at 16:05
  • 1
    $\begingroup$ @Damien_The_Unbeliever's comment also applies to the back corner, doesn't it? No big problem, though, because if $c\le a+b$ then in your modified arrangement you can fit two of the currently one block in the bottom left next to each other, leaving your total unchanged. (The combined width of the three blocks there will be $2a+b \le a+c$ by assumption, and the other dimensions can be checked to be ok, too.) $\endgroup$ – Paul Panzer Aug 3 at 17:37
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, I think your surface area argument works. I had a different argument in mind, but didn't know how to make it rigorous. With the edges filled, every face must become a "swirl" pattern. However, the swirl pattern on adjacent faces must go in opposite directions. This is not possible for the three mutually adjacent faces around a corner of the box. Your surface area argument shows directly the trouble the third face causes. $\endgroup$ – Jaap Scherphuis Aug 4 at 15:34
1
$\begingroup$

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)

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Doesn't the box split into 8 regions, like a 2x2x2 cube? $\endgroup$ – Jaap Scherphuis Aug 3 at 8:50
  • 2
    $\begingroup$ @Jaap correct! I changed the number - fortunately, I actually did consider all 8 of them. $\endgroup$ – George Menoutis Aug 3 at 8:56
1
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ There is a step 3a which I missed. This is (a+c-b)/b boxes that can be stacked over step 3. This is what gives 12 for 5,3,1. The addiitional box is laid over the boxes. $\endgroup$ – Mahesh Dyaram Aug 5 at 16:34
  • 2
    $\begingroup$ You can edit your answer if you want to add something to it. $\endgroup$ – Rand al'Thor Aug 5 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.