Riddler Solutions

4 minute read

Published:

I like Riddler from 538 mostly because you can solve the riddles with some fun math. If the riddle is interesting enough, I will post solutions on my blog. This is one such riddle.

The Riddle

You and your infinitely many friends are sharing a cake, and you come up with two rather bizarre ways of splitting it. For the first method, Friend 1 takes half of the cake, Friend 2 takes a third of what remains, Friend 3 takes a quarter of what remains after Friend 2, Friend 4 takes a fifth of what remains after Friend 3, and so on. After your infinitely many friends take their respective pieces, you get whatever is left. For the second method, your friends decide to save you a little more of the take. This time around, Friend 1 takes $1/2^2$ (or one-quarter) of the cake, Friend 2 takes $1/3^2$ (or one-ninth) of what remains, Friend 3 takes $1/4^2$ of what remains after Friend 3, and so on. Again, after your infinitely many friends take their respective pieces, you get whatever is left.

Question 1: How much of the cake do you get using the first method?

Question 2: How much of the cake do you get using the second method?

The Solution

It is very easy to argue that method 1 leaves us no cake left. Let’s see why. First, let’s agree to model how much cake is left rather than how much the $k^{th}$ friend takes. The first friend takes half (leaving us half a cake). The second friend takes a third of what remains (meaning there are two thirds of one half left). The third friend takes a fourth of what remains (meaning there is three quarters of two thirds of one half left). See the pattern? Let $\pi_k$ be the proportion of pie (or, er cake) left after friend $k$ takes their share. The sequence is

\[\begin{align} \pi_1 &= \dfrac{1}{2}\\ \pi_2 &= \dfrac{2}{3} \times \dfrac{1}{2} = \dfrac{1}{3}\\ \pi_3 &= \dfrac{3}{4} \times \dfrac{2}{3} \times \dfrac{1}{2} = \dfrac{1}{4}\\ & \vdots\\ \pi_k &= \dfrac{1}{k+1} \end{align}\]

Since $\lim_{k \to \infty} \pi_k = 0$ we get no cake.

Method 2 is more interesting. Remember, we are modelling how much is left. The sequence is

\[\begin{align} \pi_1 &= \dfrac{3}{4}\\ \pi_2 &= \dfrac{8}{9} \times \dfrac{3}{4} \\ \pi_3 &= \dfrac{15}{16} \times\dfrac{8}{9} \times \dfrac{3}{4}\\ & \vdots\\ \pi_k &= \prod_{m=2}^{m=k} \dfrac{(m+1)^2-1}{(m+1)^2} \end{align}\]

It is not obvious what $\pi_k$ approaches as $k \to \infty$. Let’s see what this quantity approaches empirically and see if we can get some intuition.

cake = 1
for friend in range(2,100090):
    cake = cake *(friend**2-1)/friend**2
print(cake)
>>>0.5000049955540937

Looks like it is approaching 1/2. Now that we know where we are going, let’s prove it. It is easier to work with the log of the product because that turns it into sums. The use of $(m+1)$ in the expression for $\pi_k$ are to make the indicies work. Let’s just use $m$ because we’re mostly interested in the limit, not the indicies.

\[\log(\pi_k) = \sum_{m=2}^{m=k} \log(m^2-1) - \log(m^2) = \sum_{m=2}^{m-k} \log(m+1) + \log(m-1) - 2\log(m)\]

Here, I’ve just factored the difference of squares and applied some log rules.

Writing out the first few terms of the summand

\[\begin{align} &\log(3) + \log(1) - 2\log(2)\\ &\log(4) + \log(2) - 2\log(3)\\ &\log(5) + \log(3) - 2\log(4)\\ &\log(6) + \log(4) - 2\log(5)\\ \end{align}\]

and so on. Some nice cancellation occurs. The $\log(3)$ term appears in lines 1 and 3, and is cancelled by the 2 factors in line 2. Similar arguments are made for the $\log(4)$ terms in lines 2,4, and 3. What is left uncanceled is $\log(1)$ and one factor of $\log(2)$ as $k \to \infty$, meaning the product approaches $1/2$. Hence, we get half a cake.

Extra Credit

There is an extra credit portion to this question I can’t figure out. Suppose your friends start taking slices of cake which or proportions of squares of even numbers (the first takes $1/2^2$, the second takes $1/4^2$, the third $1/6^2$, and so on). The proportion of cake left is

\[\begin{align} \pi_1 &= \dfrac{3}{4}\\ \pi_2 &= \dfrac{15}{16}\times \dfrac{3}{4}\\ \pi_3 &= \dfrac{35}{36} \times \dfrac{15}{16}\times \dfrac{3}{4}\\ & \vdots\\ \pi_k &= \dfrac{3^2 \times 5^2 \times 7^2 \times \cdots}{2^2 \times 4^2 \times 6^2 \times \cdots} \end{align}\]

But I can’t seem to find a way to beak this sequence’s back. Hints are welcome.