Mailing incongruent cubes to a friend

[BMAD]

Call a set of cubes incongruent if they all have different side lengths. Prove that it is impossible to exactly fill a rectangular box with incongruent cubes.

Note: The phrase "exactly fill" means that there is no space in the box which is not occupied by a cube, and that the cubes themselves should be packed together to form the shape of the rectangular box that envelops them.

[jamieg]

Trivial case excluded?

(Rectangular box of sides nxnxn, filled with a single cube of sides nxnxn, no two cubes have the same length)

[bonanova]

Suppose the box can be filled completely.

Consider the bottom layer of cubes - those that touch the bottom of the box.

Their bottom faces tile the box bottom into squares.

Consider the smallest of these squares.

• It cannot be a corner square:
  One of its (larger) neighbors prevents its other (also larger) neighbor from touching it.
  
• It cannot be an edge square:
  Two of its (larger) neighbors prevent its third (also larger) neighbor from touching it.
  
• It must be an interior square:
  Four (larger) neighboring squares can bound a smallest interior square.
  Now, the top face of the smallest bottom cube (call it A) and the inner faces of its (larger)
  surrounding cubes comprise five walls of a new space to be filled entirely with cubes.

Cube A's top face is tiled with squares, the smallest of which is an interior square.The cube (call it B) that sits on this square is surrounded by four larger cubes. Its top face and their inner faces comprise five walls of a new space to be filled entirely with cubes.

Cube B's top face is tiled with squares, the smallest of which is an interior square.The cube (call it C) that sits on this square is surrounded by four larger cubes. Its top face and their inner faces comprise five walls of a new space to be filled entirely with cubes.

Cube C's top face is tiled with squares, the smallest of which is an interior square.The cube (call it D) that sits on this square is surrounded by four larger cubes. Its top face and their inner faces comprise five walls of a new space to be filled entirely with cubes.

... etc. ...

No matter how finely the box bottom is partitioned into squares, or how nearly equal the sizes of the cubes are, there will always be space above the stack of cubes A, B, C, D, ... that remains unfilled.

The box therefore cannot be completely filled with cubes.

[Anza Power]

1st, the problem can be reduced to 2D, if you just look at the bottom row, then it's a problem of fitting a rectangle using several squares of different sizes.

Imagine that someone tried to do it in 2D, take a look at the squares touching the bottom side of the rectangle, they may look something like this:

####

#########

#########

#########

Now look at the smallest of these squares (in this example the green one) I say you cannot fill the row directly above it, because you cannot use another square of the same size, so you'll have to use smaller squares, but then reapply this proof recursivly until you get to the smallest square of size 1x1 with a 1x1 gap above it and you are stuck.

Edited October 16, 2013 by Anza Power

[bonanova]

1st, the problem can be reduced to 2D, if you just look at the bottom row, then it's a problem of fitting a rectangle using several squares of different sizes.Imagine that someone tried to do it in 2D, take a look at the squares touching the bottom side of the rectangle, they may look something like this:

###############################Now look at the smallest of these squares (in this example the green one) I say you cannot fill the row directly above it, because you cannot use another square of the same size, so you'll have to use smaller squares, but then reapply this proof recursivly until you get to the smallest square of size 1x1 with a 1x1 gap above it and you are stuck.

It works in 2D. The smallest square just can't be on an edge.

[phil1882]

could you give a pictorial example of it working in 2d bonanova?

i can't find an example.

[bonanova]

could you give a pictorial example of it working in 2d bonanova?

i can't find an example.

http://en.wikipedia.org/wiki/Squaring_the_square