2

The question goes:

There are $100$ people and a cake. The first person gets $1$% of the cake, the next gets $2$% of the remaining cake, and so on. Find out which person gets the highest amount of cake.

This was given to me by one of my friends, and here's what I thought: This is easily reduced to a recurrence relation, and if I can solve it, it's simple to maximize the same.

I considered the cake to be equivalent to $1$, and got the following recurrence: $$P_n=\frac{n}{100}(1-P_{n-1})$$ where $P_n$ denotes the amount of cake received by the $n^{th}$ person.

Aaaaand I'm stuck. Please help me. Thanks in advance.

Edit: As pointed out by lulu, my recurrence is incorrect. It should be $$P_n=\frac{n}{100}\left(1-\sum_{i=1}^{n-1} P_i\right)$$

AryanSonwatikar
  • 2,728
  • 4
    That's not the right recursion. You should have $P_n=\frac n{100}\left(1-\sum_{i=1}^{n-1}P_i\right)$. – lulu Mar 04 '20 at 02:44
  • Ahhh. I see. But unfortunately that complicates it further. – AryanSonwatikar Mar 04 '20 at 02:53
  • 1
    https://www.youtube.com/watch?v=9PVcTdSlGBA Basically what this video illustrates is that you can unravel the recursion to derive the general formula $P_n=\frac{99!}{(100-n)!} \frac{n}{100^n}$ so that $\frac{P_{n+1}}{P_n}=\frac{100-n}{100} \frac{n+1}{n}$, at which point the problem is pretty straightforward. – Ian Mar 04 '20 at 02:56
  • 1
    Also relevant: https://puzzling.stackexchange.com/questions/52787/who-gets-the-biggest-piece – an4s Mar 04 '20 at 02:59

1 Answers1

2

In general $P_n=\frac{n}{100} \left ( 1 - \sum_{i=1}^{n-1} P_i \right )$. Now use that to relate $P_{n+1}$ directly to $P_n$:

$$P_{n+1}=\frac{n+1}{100} \left ( 1 - \sum_{i=1}^n P_i \right ) = \left ( \frac{n}{100} + \frac{1}{100} \right ) \left ( \left ( 1- \sum_{i=1}^{n-1} P_i \right ) - P_n \right ) \\ = P_n - \frac{n}{100} P_n + \frac{P_n}{n} - \frac{P_n}{100} \\ = \left ( 1 - \frac{n+1}{100} + \frac{1}{n} \right ) P_n.$$ Thus $P_{n+1} > P_n$ if and only if $1-\frac{n+1}{100}+\frac{1}{n}>1$. Clearing denominators gives $100n-n(n+1)+100>100n$ or $-n^2-n+100>0$. You can find where the range of values of $n$ where this inequality holds (either by brute force or by solving the quadratic).

Ian
  • 101,645