100 people 100 money

Question

Imagine you have $100$ dollars or any currency. And you also have $100$ people numbered from Everyone one will be paid from that money. Number one will get $1$ percent of the money, number $2$ will get $2$ percent from the rest of the money. For example, number $2$ will get $2$ percent from $99$ dollars, because number one got $1$ dollars from the first $100$. The question is who will be paid the most

I really tried to solve this, but failed. Thank you in advance.

Answer 1

It is clear that the first person is not paid the most since he gets $1$\$ and the second person gets $1.98$\$. Let $P(m)$ denote the amount of money paid to the $m^{th}$ person for all $m\in\mathbb{N}_{\leqslant 100}$. Let $n\in\mathbb{N}_{<100}$. Suppose that $P(n)=u$ for some $u\in \mathbb{R}^+$. Then, $P(n+1)=\frac{u(100-n)(n+1)}{100n}$. $P(n+1)\geqslant P(n) \iff\frac{(100-n)(n+1)}{100n}\geqslant 1 \iff n^2+n\leqslant 100 \iff n\leqslant 9$. Also, if $n\leqslant 9$, then $\frac{(100-n)(n+1)}{100n}> 1$. This implies that $P(1)<P(2)<\ldots<P(10)>P(11)$. If $P(k)$ is maximum for some $k>11$, then we must have had $P(k-1)\leqslant P(k)$ but this is not possible since $k-1>9$. Hence, from the above arguments, the tenth person gets paid strictly more than the rest.

EDIT: I've elaborated and structured the argument.

Answer 2

Set $B(n)$ as the current balance of money remaining and $P(n)$ as the payout to the n-th person.

Then $B(0)=100$ and $B(n)=B(n-1)-P(n)$ as the balance decreases each turn by the value that has been paid out.

Also, $P(n)=\frac{n}{100} B(n-1)$ as the percentage that gets paid each turn.

Inserting that into the above formula we get

$$ B(n)=B(n-1)-\frac{n}{100} B(n-1)=(1-\frac{n}{100})B(n-1) $$

We can then reduce this recursive formula to the direct value $$ B(n)=B(0)\prod_{i=0}^n(1-\frac{i}{100})= 100 \prod_{i=0}^n(1-\frac{i}{100}) $$

Inserting that into $P(n)$ gives $$ P(n)=\frac{n}{100}100 \prod_{i=0}^{n-1}(1-\frac{i}{100})=n \prod_{i=0}^{n-1}(1-\frac{i}{100}) $$

where we notice the arising recursive formula

$$ P(n)=\frac{n}{n-1}\left(1-\frac{n-1}{100}\right) P(n-1) $$

If we can show that these factors are monotonically decreasing and start above $1$ for $n=0$, we can find the maximum by finding the first $n$, where the factor gets below $1$.

Thus, we compute $$ \frac{n}{n-1}\left(1-\frac{n-1}{100}\right) >1\\ \Leftrightarrow n^2-n-100<0\\ \Leftrightarrow \frac{1}{2}-\sqrt{\frac{1}{4}+100}<n<\frac{1}{2}+\sqrt{\frac{1}{4}+100} \\ \Leftrightarrow -9<n<10 $$

for integer numbers $n$. Thus we can conclude that $n=10$ will get the most amount of payout.

For the general case, the square root of the total number will approximately be the winning number.