8
$\begingroup$

You are the author for the magazine Extreme Cuisine Quarterly. Your articles are not concerned with cooking, but rather with the presentation of the meal.

Recently, there have been rumors of a Russian chef who performs the following amazing feat. They say that during the appetizer course he brings out a huge cube of cheese and, in front of everyones eyes, cuts it up into several smaller cubes, all of which have different sizes.

Your editor wants you to fly Russia to write an article about this Russian chef.

Save your magazine the cost of a plane ticket by proving the feat is impossible.

$\endgroup$
  • 1
    $\begingroup$ @Miniman "several" refers to "finitely many". $\endgroup$ – Mike Earnest Dec 8 '15 at 3:56
  • $\begingroup$ Should we consider the possibility that this chef is creating some of his cubes by recombining non-cube cuts together? Like this: channel4.com/learning/main/netnotes/images/m4r/ML6.10.gif $\endgroup$ – Zerris Dec 8 '15 at 4:09
  • 7
    $\begingroup$ Even if this chef is a fraud, why would I want to discourage my employer from giving me a free vacation? $\endgroup$ – Darrel Hoffman Dec 8 '15 at 15:30
5
$\begingroup$

Can't be done.

If it could, then every planar cross-section of the cube would consist of a big square divided into several smaller squares all of which would have different sizes. This can be done (see picture below), but the smallest square in any solution is always internal to the big square (i.e. not on an edge or corner). Consider the planar cross sections that cut through the smallest cube in the entire block. The smallest-cube will be the smallest-square in these cross sections and will be internal to the large square (and also internal to the block). At least one of the surfaces of this smallest cube will be surrounded by 'walls' consisting the touching faces of the surrounding cubes. The only way to 'cover' this walled in face is to use still smaller cubes, so the cube cannot be the smallest. Hence disproof by contradiction.

I hope this is clear enough - it is hard to describe properly without complicated drawings or models.

enter image description here

$\endgroup$
  • 4
    $\begingroup$ The picture you chose is incorrect because it is not quite square (it is 32 x 33). The smallest number of distinct squares you can get is 21 - example on this Wikipedia article. $\endgroup$ – Darrel Hoffman Dec 8 '15 at 15:40
  • $\begingroup$ Notice it is possible for a smaller cube to be surrounded by bigger cubes with no gaps. $\endgroup$ – Fimpellizieri Dec 20 '15 at 2:18
  • $\begingroup$ It is not a square, but it doesn't matter. In fact, Penguino proved you cannot cut any rectangular prism into cubes of all different sizes. The cube is just a special case. $\endgroup$ – Florian F Jan 11 '16 at 21:33
  • $\begingroup$ Actually, I don't think this proof works. The proof says that something like this will happen: some cross-section next to the smallest cube (gold) will "squish" the cubes adjacent to the tiny cube into being the same size as the tiny cube. (imgur.com/a/H1qx1) $\endgroup$ – Deusovi Apr 23 '16 at 4:25
  • $\begingroup$ But that's not necessarily the case! What if something like this happens? (imgur.com/a/kMsND) (The two views are the front and back.) You can successfully place two larger cubes on both sides indicated in the pictures to completely surround the small cube. $\endgroup$ – Deusovi Apr 23 '16 at 4:30
8
$\begingroup$

Making a cut on a cubiod will create two pieces that have have at least one side with similar dimensions. As such, one piece will have to have that side cut through, and since it too is a cubiod, the same problem will be created again.

$\endgroup$
  • 1
    $\begingroup$ You assume, then, that all cuts must be completely through the cube? Why not partial cuts, which is easily accomplished with a kitchen knife and cheese block? $\endgroup$ – Adam Davis Dec 8 '15 at 15:10
  • $\begingroup$ I don't quite understand this solution. It seems there's a lot that's unclear but assumed. $\endgroup$ – Fimpellizieri Dec 8 '15 at 15:12
  • $\begingroup$ @Adam Davis, Penguino's worried me, as I did make this assumption. However, my answer holds true. It is impossible to make a cut that makes two sides with unequal lengths. $\endgroup$ – Carl Dec 8 '15 at 15:35
  • 1
    $\begingroup$ I believe this shows that one cannot obtain the desired partition of the cube via one-at-a-time cutting moves rather than show that one such partition does not exist. $\endgroup$ – Fimpellizieri Dec 8 '15 at 16:08
  • 1
    $\begingroup$ Now that I've seen that a square can be squared ( a perfect square ), I'm not sure that this is correct. $\endgroup$ – Carl Dec 8 '15 at 16:42
2
$\begingroup$

I assume the huge cube $C$ is cut up into several finite smaller cubes $C_i$. Moreover, I assume that any finite partition of a cube into cubes must be stacked (that is, no $C_i$ is tilted relative to $C$). I provide no proof of this but I think this is pretty straightforward (examine a corner of $C$ and verify that it propagates to the rest).

We will show that such a partition of the cube contains an 'decreasing' sequence of cubes, contradicting its finiteness. The proof follows primarily a two-dimensional reasoning, which I think is pretty neat and makes it easier to follow even without pictures.

Consider the bottom face $f_0$ of $C$. The partition of $C$ determines a partition of the square $f_0$ into finite squares each of which is a different size. Consider the smallest square $s_0$ of such a partition.

Claim: $s_0$ must lie in the interior of $f_0$.

Indeed, let $s_0 = ABCD$, $f_0 = PQRS$ and suppose $s_0$ touches the boundary $\partial f_0$ of $f_0$. There are two cases:

  • $s_0$ is not in a corner of $f_0$.

In this case, assume without loss of generality that $AB \subset PQ$ (so that $PQ$ is a barrier to squares surrounding $s_0$ in the partition of $f_0$) and that no other side of $s_0$ is contained in $\partial f_0$.

The square that touches $BC$ must be larger than $s_0$, and because of the barrier $PQ$ its side along $BC$ must begin at $B$ and end past $C$. This means part of it acts as a barrier to squares that touch $CD$. We may repeat the process, deducing that the square that touches $CD$ must begin at $C$ and end past $D$, so part of it acts as a barrier to squares that touch $DA$.

Now $DA$ is walled near $D$ by this last square and near $A$ by $PQ$, so a square that touches $DA$ cannot be larger than $s_0$, contradicting its (strict) minimality.

  • $s_0$ is in a corner of $f_0$.

This case is actually easier than the previous one. Assume without loss of generality that $AB \subset PQ$ and $DA \subset SP$. Like before, part of the square that touches $BC$ acts as a barrier to the square that touches $CD$ near $C$.

Now $CD$ is walled near $C$ by this last square and near $D$ by $SP$, and once again we derive a contradiction with $s_0$'s minimality.

The claim is thus proved.

Now, consider the cube $c_0$ that $s_0$ is a face of; it stands on the bottom face $f_0$ of $C$. $c_0$ is surrounded on all sides by larger cubes that also stand on $f_0$, and thus its top face $f_1$ is walled on all sides. It follows that cubes touching $f_1 $ must all be smaller than $c_0$ and stand on $f_1$.

These cubes determine a partition of the square $f_1$ into finite squares each of which is a different size; we may thus consider the smallest square $s_1$ of such a partition and the cube $c_1$ that $s_1$ is a face of.

Procceeding by induction, we obtain a sequence ${(c_n)}_{n \geq0}$ of cubes in our partition in which $c_n$ is larger than $c_{n+1}$, as desired.

$\endgroup$
  • 1
    $\begingroup$ I agree with your case 1, but I don't think your case 2 works similarly. In particular, if the $v$ from $f_1$ and the $v$ from $f_2$ are opposite corners, then there is no limit on the space between parallel faces like in the first case. I tried to create a picture of this here. In the picture, there are six bigger cubes surrounding a smaller one, but the image is broken up into three separate images for "ease" of viewing. $\endgroup$ – Tyler Seacrest Dec 8 '15 at 5:36
  • $\begingroup$ You are right, the second case needs some work. It is possible for a smaller cube to be surrounded by bigger cubes with no gaps. $\endgroup$ – Fimpellizieri Dec 8 '15 at 15:07
  • $\begingroup$ @TylerSeacrest I altered the solution and I think it's all good now. Turns out thinking about it in a more 2D-oriented way is better! $\endgroup$ – Fimpellizieri Dec 8 '15 at 16:05
  • $\begingroup$ Looks good to me; very clever! $\endgroup$ – Tyler Seacrest Dec 8 '15 at 18:19

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.