This Riddler puzzle asks about finding the maximum-volume shape subject to constraints.
A mathematician who has a birthday coming up asks his students to make him a cake. He is very particular and asks his students to make him a three-layer cake that fits under a hollow glass cone he has on his desk. He requires that the cake fill up the maximum amount of volume under the cone as possible and that the layers of the cake have straight vertical sides. What are the thicknesses of the three layers of the cake in terms of the height of the glass cone? What percentage of the cone’s volume does the cake fill?
Here is my solution.
[Show Solution]
Although one could write a formula for the total volume of the cake as a function of each layer height, this turns out to be impractical if there are many layers. A better approach is to use dynamic programming. The key lies in realizing that if you have an optimal cake with $k+1$ layers and you remove the bottom layer, you’ll be left with an optimal cake with $k$ layers.
Let’s define $v_k$ to be the fraction of the total cone volume taken up by a cake with $k$ layers. We can write that:
\[
v_{k+1} = \frac{(\text{bottom layer vol.}) + v_{k}\cdot(\text{cone vol. above bottom layer})}{(\text{total cone volume})}
\]Suppose the total cone has a height $h$ and base radius $r$, and the bottom layer occupies a fraction $\lambda$ of the total height $h$. The cone above the bottom layer therefore has a height of $(1-\lambda)h$ and a base radius of $(1-\lambda)r$. This base radius is also the radius of the cylinder that forms the bottom layer.
We must choose $\lambda$ so that the right-hand side is maximized. Substituting the formulas for the volume of a cone and cylinder, we obtain:
\begin{align}
v_{k+1} &= \max_\lambda \,\frac{\pi (1-\lambda)^2 r^2 \lambda h + v_{k}\cdot \tfrac{1}{3} \pi(1-\lambda)^2 r^2 (1-\lambda) h }{\tfrac{1}{3}\pi r^2 h}\\
&= \max_\lambda \,\left( 3\lambda(1-\lambda)^2 + v_{k}(1-\lambda)^3 \right)
\end{align}This expression is maximized when $\lambda=\tfrac{1-v_k}{3-v_k}$ and the maximum value is $\tfrac{4}{(3-v_k)^2}$. So the max volume fraction satisfies
\[
v_{k+1} = \frac{4}{(3-v_k)^2},\qquad\text{with }v_0=0
\]and the fraction of the total height taken up by the bottom layer is:
\[
\lambda_{k+1} = \frac{1-v_k}{3-v_k}
\]
Three layers
For example, if the cake has three layers, we can use the recursion to find:
\begin{align}
v_1 &= \tfrac{4}{9} & v_2 &= \tfrac{324}{529} & v_3 &= \tfrac{1119364}{1595169} & v_4 &= \dots\\
\lambda_1 &= \tfrac{1}{3} & \lambda_2 &= \tfrac{5}{23} & \lambda_3 &= \tfrac{205}{1263} & \lambda_4 &= \dots
\end{align}We can then build the layers from bottom to top. If the cake is $1$ unit tall, the bottom layer takes up a fraction $\lambda_3$ of the total height, or $\tfrac{205}{1263}$. Out of the remaining $\tfrac{1058}{1263}$, the next layer takes up a fraction $\lambda_2$, which is $\tfrac{230}{1263}$. So far, the two bottom layers have taken up $\tfrac{435}{1263}$. Finally, out of the remaining $\tfrac{828}{1263}$, the top layer takes a fraction $\lambda_1$, which is $\tfrac{276}{1263}$. So in all, the layers (from bottom to top) have heights:
$\displaystyle
h_3 = \tfrac{205}{1263} \approx 0.1623,\quad
h_2 = \tfrac{230}{1263} \approx 0.1821,\quad
h_1 = \tfrac{276}{1263} \approx 0.2185
$
and this fills a fraction $v_3 = \tfrac{1119364}{1595169} \approx 0.7017$ of the volume of the cone.
In general, volume ratios $v_k$ and layer heights $h_k$ are given by:
\begin{align}
v_{k+1} &= \frac{4}{(3-v_k)^2}, & & \text{(go forward from }v_0=0\text{)}\\
\lambda_{k+1} &= \frac{1-v_k}{3-v_k} & & \\
h_{k-1} &= \lambda_{k-1}(\lambda_k^{-1} – 1) h_k, & & \text{(go backward from }h_N=\lambda_N h\text{)}
\end{align}The recursion for $v_k$ is nonlinear and likely does not have a nice closed-form expression. However, it’s easy to compute its value for large $k$ by simply iterating. Here is a plot that goes up to $k=30$.
Here is an animation showing how the cake looks as we add more layers.
Note that the top layer is always $\tfrac{1}{3}$ the height of the remaining cone since $\lambda_1 = \tfrac{1}{3}$.
Here, I go into more detail about bounding the optimal cake volume as the number of layers becomes large.
[Show Solution]
Although we can’t find a closed-form expression for $v_k$, we can approximate it quite well for large $k$. To see how, make the substitution $f_k = (1-v_k)^{-1}$, which results in the recursion:
\[
f_{k+1} = f_k + \frac{3}{4} + \frac{1}{16f_k+4},\qquad f_0=1
\]From here, it’s clear $f_k$ is increasing. Moreover, $f_{k+1} > f_k + \frac{3}{4}$. If this inequality were an equality instead, the recurrence would be satisfied by $f_k = \tfrac{3}{4}k+1$. Therefore, we have the lower bound:
\[
f_k > \frac{3}{4}k+1
\]To find an upper bound, substitute the lower bound into the recursion:
\[
f_{k+1} < f_k + \frac{3}{4} + \frac{1}{12k+20}
\]At equality, this recurrence also has a closed-form expression, which leads to the upper bound
\[
f_k < \frac{3}{4}k+1+\frac{1}{4}\sum_{j=1}^k\frac{1}{2+3j} < \frac{3}{4}k+1+\frac{1}{12}\log\left(1+\frac{3}{2}k\right)
\]Combining the lower and upper bounds:
\[
\frac{3}{4}k+1 < f_k < \frac{3}{4}k+1+\frac{1}{12}\log\left(1+\frac{3}{2}k\right)
\]Substituting back the definition for $v_k$:
$\displaystyle
\frac{3k}{3k+4} < v_k < \frac{3k+\tfrac{1}{3}\log\left(1+\tfrac{3}{2}k\right)}{3k+\tfrac{1}{3}\log\left(1+\tfrac{3}{2}k\right)+4}
$
The difference between the upper and lower bounds satisfies
\[
\Delta_k < \frac{\tfrac{4}{3}\log\left(1+\tfrac{3}{2}k\right)}{ (3k+4)^2 }
\]which goes to zero rapidly as $k\to\infty$. For example, if we wanted to know what fraction of the cone's volume we could fill with a 1000-layer cake, we would set $k=1000$ and the bound above tells us that
\[
99.86684\% < v_{1000} < 99.86695\%
\]The true value turns out to be $99.86694\dots\%$.
Well done.
I too (originally) had dynamic programming in mind for this problem and I was able to get the 44.4% of volume for the single layer. For some reason, I then changed gears and tried to set this up as a Lagrangian for 3 layers all at once, which was…. not a good idea.
After ruining quite a few sheets of paper I ended up numerically getting to the answer with a few for loops. This is still a bit bothersome, though, as ‘Layer Cake’ is such a good movie.
Also– that birthday cake animated gif is very cool.