The 271st Riddler presents us with a fun problem about your infinite number of friends trying to share some cake. In the first question, friend 1 eats 1/2 of the cake, friend 2 eats 1/3 of what remains of the cake, friend 3 eats 1/4 of what remains of the cake and so on.
If we let \(R_0 = 1\) represent the whole cake at step 0, and \(R_n\) represent the amount of cake remaining after friend \(n\) has had thier share, then we see that \(R_1 = (1-1/2) = 1/2\), \(R_2 = (1-1/3)(1-1/2) = 1/3\), and so on. This is an infinite product, each of which reducing nicely to \(R_n = 1/n\). This goes to 0, so there won’t be any cake remaining using the first allocation method.
The second question changes it to \(1/2^2\), \(1/3^2\), \(1/4^2\), … instead. Using our work and notation from above, we find \(R_1 = (1-1/2^2)=3/4\), \(R_2 = (1-1/3^2)(1-1/2^2) = 2/3\), and \(R_3 = (1-1/4^2)*2/3 = 5/8\). If we rewrite \(R_2 = 4/6\) instead, we can see a pattern with the numerators increasing by 1 and denominators increasing by 2. Indeed, \(R_n = (n+2)/(2n+2)\) through induction. As \(n\rightarrow \infty\), \(R_n \rightarrow 1/2\).!
The third question is a little trickier, in that at the \(n\)th stage, \(1/(2n)^2\) of the cake is eaten. Using the above ideas, we can find that \(R_1= 3/4\), and \(R_n = \frac{(2^2-1)(4^2-1)*\cdots * ((2n)^2-1)}{2^2*4^2*\cdots * (2n)^2}\) for \(n >1\). We’ll use R to give us an idea of where this converges to.
Riddle271 <- function(N){
K <- (2^2*(1:N)^2-1)/(2^2*(1:N)^2)
return(prod(K))
}
(ans <- Riddle271(1000000))## [1] 0.6366199This answer doesn’t look that familiar. I happened to look at the inverse and it did!
1/ans## [1] 1.570796pi/2## [1] 1.570796So the answer is \(\frac{2}{\pi}\). A nice proof of this can be found at http://www.intuitive-calculus.com/pi-infinite-product.html.
If there are two players, A and B, then you want to be the one that can get to 5, 10, and finally 15. Then the other player at 15 has to at least get to 16 and at most get to 19. Then you can take it all the way to 20. So, we don’t want to go first if there are two players since after the first player says 1, the second can say 4 and make 5.
If there are three players, you definitely don’t want the person behind you in this game winning. You’d like to win, but will take a loss as long as the next person gets the win to advance to the next round. If an individual is on 15, then the next person wins no matter what, so you don’t want the individual ahead of you to land on 15. If you’re on 14, then the least you can give the next person is 15, which will ensure your demise, so your strategy should be to give the next person the game by stating a number from 2-4.
Given this strategy, you don’t want to put the person ahead of you on 14! If you’re on 13 then you want to avoid both 14 and 15 because of these reasons, so you should state 3 or 4 as your number and give the next person the game so you can advance to the next round.
Likewise with 12! If you give the next person a 13, 14, or 15, then they will end the game with the person behind you. So state 4!
It looks like 11 is a bad number that you don’t want to be stuck with, since any number you state will put the next person with a 12, 13, 14, or 15, which is the position in which they will throw the game to the following player which is the player behind you.
Ideally, you want to be in a position to be able to give the player following you an 11. Second to that, you want the person behind you to be stuck on 11. We can give the player in front of us an 11 if we are on 7, 8, 9, or 10. If we have 3, 4, 5, or 6, we can place the person in front of us with the ability to give the person behind us an 11.
So, consider player B’s situation. Player A begins with “one”. If player B says anything greater than 1, he will place player C with a 3, 4, or 5. In that situation, player C can throw the game to player A by giving them a 7, 8, or 9, and the ability to stick us with 11. Thus, player B will say “one” and stick player C with 2. Player C must then put Player A in the 3, 4, 5, or 6 position, and, knowing they cannot win, will throw the game to player B by providing them with a 7, 8, 9, or 10 and the ability to stick player C with an 11.
Player B wins the first round, then player C is eliminated and player A begins the next round with “one”. As we saw above, this gives player B the power to stick player A with the dreadful 5, 10, and 15, so that player B ultimately wins.