Loading [MathJax]/jax/output/HTML-CSS/jax.js

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/22 (or one-quarter) of the cake, Friend 2 takes 1/32 (or one-ninth) of what remains, Friend 3 takes 1/42 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 nth friend takes her slice is Cin when using method i.

Under method 1, the (n+1)th friend takes a piece measuring 1n+2C1n leaving the recurrence equation of C1n+1=(11n+2)C1n. We can iterate backward to find that C1n+1=n+1i=1(11i+1)=n+1i=1ii+1=n!(n+1)!=1n. Since you are a good friend you are at the end of the line and would receive C1=limnC1n=limn1n=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 1(n+2)2C2n leaving the recurrence equation of C2n+1=(11(n+2)2)C2n. We can iterate backward to find that C2n+1=n+1i=1(11i+12)=n+1i=1(i+1)21(i+1)2=n+1i=1(i+2)i(i+1)2=(n+4)!2(n+2)!((n+3)!)2=n+42(n+3). In this case, you receive C2=limnC2n=limnn+32(n+2)=12, 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/22 of the cake, Friend 2 takes 1/42 of what remains, Friend 3 takes 1/62 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 3rd method, the (n+1)the friend takes a piece measuring 14(n+1)2C3n leaving the recurrence equation of C3n+1=(114(n+1)2)C3n We can iterate backward to find that C3n+1=n+1i=1(114i2)=n+1i=1(4i21)4i2=n+1i=1(2i+1)(2i1)4i2=(2n+3)!!(2n+1)!!4n+1((n+1)!)2, where n!! is the double-factorial and in particular the following identity holds (2n1)!!=(2n+1)(2n1)531=(2n)!2nn!. So we have C3n=(2n+1)!!(2n1)!!4n(n!)2=(2n+2)!2n+1(n+1)!(2n)!2nn!4n(n!)2=(2n+2)!(2n)!24n+1(n+1)!(n!)3. Using Stirling's approximation of n!2πn(n/e)n we get C3n2π(2n+2)((2n+2)/e)2n+24πn(2n/e)2n24n+12π(n+1)((n+1)/e)n+1(2πn(n/e)n)3=(2π)(n+1)n24n+3(n+1)2n+2n2ne(4n+2)(2π)2(n+1)n24n+1(n+1)n+1n3n+1e(4n+1)=2πe(1+1n)n+1 Since ln(1+1/x)=1x12x2+O(x3) as x, we have (1+1n)n+1=exp((n+1)ln(1+1n))=exp(1+12n+O(n2))e. Thus, under method 3 you are left with a whopping C3=limnC3n=limn2πe(1+1n)n+1=2π63.66%.

No comments:

Post a Comment