Maths prize puzzle for 20 July 2018 cake numbers
In three dimensions, what is the maximum number of pieces you can cut a cake into with one cut? Two cuts? Three cuts?
What is the general formula for n cuts?
Howard Tran won the prize, with the following calculation.
For 0 cuts you get 1 piece
For 1 cut you get 2 pieces
For 2 cuts you get 4 pieces
For 3 cuts you get 8 pieces
Since this is a three-dimensional problem – or, perhaps you could say, because every piece has either a bottom vertex defined by three planes, or a bottom surface (on the bottom of the cake) defined by two or three planes – the formula will be of the order of n3.
So, if P(n) is the number of pieces for n cuts, it’s something like:
Substituting n = 0, 1, 2, 3 gives us
D = 1
A + B + C + 1 = 2
8A + 4B + 2C + 1 = 4
27A + 9B + 3C + 1 = 8
Subtracting the second equation × 2 from the third equation
6A + 2B = 1
Subtracting the second equation × 3 from the fourth equation
24A + 6B = 4
Howard’s method is good. Here’s another one.
Start by thinking about how many pieces you can divide a point into with n cuts. Just 1, however big n is. Or nC0.
Go from 0 dimensions (a point) to 1 dimension (a line). How many pieces can you divide a line into with n points? Assume the line isn’t exactly horizontal. (If it is, tilt it microscopically so it isn’t. That doesn’t change the number of pieces). Each of the n points has a piece with that point at the bottom of it, and there is one last piece with no “bottom”.
Number of pieces = n + 1 = nC1 + nC0
Go from 1 dimension to 2 dimensions – a plane, so the pizza problem.
Number of pieces = nC2 + nC1 + nC0
Now we can see the method used for the pizza problem – tilt the diagram microscopically if necessary, then consider the pieces with a bottom vertex, then consider those with no bottom vertex – as not just a trick, but a method of connecting the 2-dimensional problem to the 1-dimensional problem.
Go to 3 dimensions. As in two dimensions, or one for that matter, we can assume that either we “scale down” the cutting, or we “scale up” the cake, so that all the cuts (planes) cut through the bottom of the cake.
Then the bottom of the cake – the pieces of the cake which have no bottom vertex – reproduces the two-dimensional problem. That contributes nC2 + nC1 + nC0 pieces. And then we have nC3 pieces with bottom vertices (points where three planes meet).
Number of pieces = nC3 + nC2 + nC1 + nC0
Which, if you do a bit of algebra, comes out exactly the same as Howard’s formula.
The advantages of this method are:
- we can see the connection between the 0-dimensional, 1-dimensional, 2-dimensional, and 3-dimensional problems
- we can build the solution in the more complicated cases (3 dimensions) on the solution in simpler cases (2 dimensions, 1 dimension, 0 dimensions)
- the formulas are more memorable than In fact, the formula can be written as: number of pieces for n cuts = total of first four numbers in n’th row of Pascal’s triangle (if we count the top 1 in Pascal’s triangle as the 0’th row, which we usually do, and the 1 1 row as the first row).
For example, we can see straight away that we get 64 pieces with 7 cuts.
- This method is more rigorous, because the argument to say is not exactly watertight.
- Weirdly, we can see straight away how many pieces we would get by cutting a 4-dimensional cake with hyperplanes.
Number of pieces = nC4 + nC3 + nC2 + nC1 + nC0
We can “see” that even though we can’t “see” a four-dimensional cake.
All this stuff has more practical importance than you might think from the talk of four-dimensional cakes. This sort of counting-possibilities maths (called “combinatorics”) is very big in the maths you need for computer science.