Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Jan 23, 2015

Box in Box problem

Source: Sent to me by Sudeep Kamath

Problem:

Airline check-in baggage has size restriction by ​so-called ​linear dimension: length + breadth + height should not exceed 62 inches. Prove that you can't "cheat" by packing a box with higher linear dimension into a box with ​lower​ linear dimension.


5 comments:

  1. Here is a proof: Let's define the r-extension of a box as the set of points in space that are at a distance of at most r from some point in the box. For a box of dimensions x,y,z, the volume of it's r-extension is given by 2r(xy+yz+zx) + pi*r^2*(x+y+z) + 4/3*pi*r^3.

    Further note that if box A (x,y,z) is inside box B (x', y', z'), the r-extension of box A is inside the r-extension of box B for any r and hence has a smaller volume.

    For large r, the dominant term in the volume that depends on the dimensions of the box is pi*r^2*(x+y+z). Hence it follows that x+y+z <= x'+y'+z'.

    ReplyDelete
  2. Let us say we successfully packed a box with higher linear dimension into a box with lower linear dimension. Choose three perpendicular axes to be "length", "breadth" and "height" axes. So now, the length, breadth and height of each of the boxes is defined. Let l,b,h be the length, breadth and height of the inner box and L,B,H be the length, breadth and height of the outer box. Clearly, since the inner box went inside the outer box, it must be the case that l < L, b < B and h < H. But this implies that l+b+h < L+B+H, or in other words, the inner box had a lesser linear dimension than the outer box, which is a contradiction to our assumption.

    ReplyDelete
    Replies
    1. The box of higher dimension may be tilted also.

      Delete
  3. (Inspired by GoKu's splendid solution.)

    For a box of dimensions x,y,z, let l be the linear dimension x+y+z, d the length of the long diagonal (so, d^2=x^2+y^2+z^2), and S the surface area 2(xy+yz+zx). Then,

    l^2 = (x+y+z)^2 = d^2 + S.

    Now, given box B_i contained in box B_o, we clearly have

    d_i^2 <= d_o^2,

    i.e.,

    l_i^2 - S_i <= l_o^2 -S_o.

    If we knew that

    S_i <= S_o,

    we could add the last two inequalities to obtain the desired conclusion. In other words, we have reduced the original problem to showing that one cannot pack a box with higher surface area into a box with lower surface area. The latter statement may be seen to hold for arbitrary compact convex bodies; here's a direct proof:

    Let F be a face of B_i, and let P be the plane containing F. We define F* to be the set of surface points of B_o that belong to the P-halfspace not containing B_i and whose projections onto P belong to F. It is easily seen that the projection of F* onto P is F, and hence the area of F is <= the area of F*. Furthermore, if G is another face of B_i, then G* is disjoint from F*. This concludes the proof.

    ReplyDelete