Sunday, May 16, 2021

Cake or countably infinite friends?

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.

How much of the cake do you get using the first method? How much of the cake do you get using the second method?

When you've invited over infinitely many friends, I suppose the unstated alternative of just getting more cake becomes less feasible, so let's figure out how much of the original cake you would be left with. Your countably infinite friends are given your explicit ranking of them, from which they know how much cake to cut using the various methods, and you know what they seem surpringingly cool with the entire setup. Let's say that the amount remaining after the $n$th friend takes her slice is $C_n^i$ when using method $i$.

Under method $1$, the $(n+1)$th friend takes a piece measuring $\frac{1}{n+2}C_n^1$ leaving the recurrence equation of $$C_{n+1}^1 = \left(1- \frac{1}{n+2}\right) C_n^1.$$ We can iterate backward to find that \begin{align*}C_{n+1}^1 &= \prod_{i=1}^{n+1} \left( 1 - \frac{1}{i+1} \right) = \prod_{i=1}^{n+1} \frac{i}{i+1} \\ &= \frac{n!}{(n+1)!} = \frac{1}{n}.\end{align*} Since you are a good friend you are at the end of the line and would receive $$C^1_\infty = \lim_{n \to \infty} C^1_n = \lim_{n \to \infty} \frac{1}{n} = 0$$ under method $1,$ which is not so great. Maybe method $2$ will yield some non-zero cake amounts left for you.

Under method $2$, the $(n+1)$th friend takes a piece measuring $\frac{1}{(n+2)^2} C^2_n$ leaving the recurrence equation of $$C_{n+1}^2 = \left(1 - \frac{1}{(n+2)^2}\right) C_n^2.$$ We can iterate backward to find that \begin{align*}C^2_{n+1} &= \prod_{i=1}^{n+1} \left(1 - \frac{1}{i+1}^2 \right) = \prod_{i=1}^{n+1} \frac{(i+1)^2 - 1}{(i+1)^2} \\ &= \prod_{i=1}^{n+1} \frac{(i+2) i}{(i+1)^2} = \frac{\frac{(n+4)!}{2} (n+2)!}{((n+3)!)^2} \\ &= \frac{n+4}{2(n+3)}.\end{align*} In this case, you receive $$C^2_\infty = \lim_{n\to \infty} C^2_n = \lim_{n\to\infty} \frac{n+3}{2(n+2)} = \frac{1}{2},$$ which is altogether not too shabby! In effect, method $2$ leaves you with twice the amount of anyone else and just as much as anyone would get under method $1.$


Your friends are feeling rather guilty for not saving enough of the cake for you, so they try one more method. (Though to be fair, these are some extremely nice friends to be upset that you took half of the cake under method $2.$ Though, maybe it took you a long time to source this infinitely divisible cake, or you figured out how to effectively distribution food to infinitely many people, so OK I guess some gratitude is deserved.) This time, they only take the fractions with even denominators from the second method. So Friend 1 takes $1/2^2$ of the cake, Friend 2 takes $1/4^2$ of what remains, Friend 3 takes $1/6^2$ of what remains after Friend 2, and so on. After your infinitely many friends take their respective pieces, how much of the cake do you get?

Under this bonus $3$rd method, the $(n+1)$the friend takes a piece measuring $\frac{1}{4(n+1)^2} C_n^3$ leaving the recurrence equation of $$C_{n+1}^3 = \left(1 - \frac{1}{4(n+1)^2}\right) C_n^3$$ We can iterate backward to find that \begin{align*}C^3_{n+1} &= \prod_{i=1}^{n+1} \left(1 - \frac{1}{4i^2} \right) = \prod_{i=1}^{n+1} \frac{(4i^2 - 1)}{4i^2} \\ &=\prod_{i=1}^{n+1} \frac{(2i+1)(2i-1)}{4i^2} = \frac{(2n+3)!! (2n+1)!!}{4^{n+1} ((n+1)!)^2},\end{align*} where $n!!$ is the double-factorial and in particular the following identity holds $$(2n-1)!! = (2n+1)(2n-1) \cdots 5 \cdot 3 \cdot 1 = \frac{(2n)!}{2^n n!}.$$ So we have $$C_n^3 = \frac{(2n+1)!! (2n-1)!!}{4^n (n!)^2} = \frac{ \frac{(2n+2)!}{2^{n+1}(n+1)!} \frac{(2n)!}{2^{n} n!}}{4^n(n!)^2} = \frac{(2n+2)! (2n)!}{2^{4n+1} (n+1)! (n!)^3}.$$ Using Stirling's approximation of $n! \sim \sqrt{2\pi n} (n/e)^n$ we get \begin{align*} C^3_n &\sim \frac{ \sqrt{2\pi (2n+2)} ((2n+2)/e)^{2n+2} \sqrt{4\pi n} (2n/e)^{2n}}{2^{4n+1} \sqrt{2\pi(n+1)} ((n+1)/e)^{n+1} \left(\sqrt{2\pi n} (n/e)^n\right)^3}\\ & =\frac{(2\pi) \, \sqrt{(n+1)n} \, 2^{4n+3} \, (n+1)^{2n+2} \, n^{2n} \, e^{-(4n+2)}}{(2\pi)^2 \, \sqrt{(n+1)n} \, 2^{4n+1} \, (n+1)^{n+1} \, n^{3n+1} \, e^{-(4n+1)}}\\ &=\frac{2}{\pi e} \left(1 + \frac{1}{n}\right)^{n+1}\end{align*} Since $\ln (1 + 1/x) = \frac{1}{x} - \frac{1}{2x^2} +O(x^{-3})$ as $x \to \infty,$ we have $$\left(1 + \frac{1}{n}\right)^{n+1} = \exp \left( (n+1) \ln \left(1 + \frac{1}{n}\right) \right) = \exp\left(1 + \frac{1}{2n} + O(n^{-2})\right) \to e.$$ Thus, under method $3$ you are left with a whopping $$C^3_\infty = \lim_{n\to\infty} C^3_n = \lim_{n\to \infty} \frac{2}{\pi e} \left(1 + \frac{1}{n}\right)^{n+1} = \frac{2}{\pi} \approx 63.66\%.$$

No comments:

Post a Comment