Maths Olympiad Prep

Library / /1 of 4

Algebra Difficulty 6.9 National Olympiad Prove it Italy

Problem:

n=10000n=10000 competitors take part in a mathematical competition.
At the closing party, in succession, the first takes 1/n1/n of the cake, the second takes 2/n2/n of the remaining cake, the third takes 3/n3/n of the cake that remains after the first and second have helped themselves, and so on until the last one, who takes all the remaining cake.
Determine which competitor takes the largest piece of cake.

Solution

Solution:

The competitor who takes the largest slice is the one who serves himself 100th.
For every k=1,2,,10000k=1,2, \ldots, 10000, let us denote by FkF_{k} the slice belonging to the kk-th competitor, and by TkT_{k} the amount of cake remaining after the first kk competitors have served themselves. Let us set by convention T0=1T_{0}=1. We must determine the value of kk for which FkF_{k} is maximum. The statement of the problem tells us that
Fk=knTk1andTk=nknTk1. F_{k}=\frac{k}{n} \cdot T_{k-1} \quad \text{and} \quad T_{k}=\frac{n-k}{n} \cdot T_{k-1} .
From these two equations we derive that
Fk+1=k+1nTk=k+1nnknTk1, F_{k+1}=\frac{k+1}{n} \cdot T_{k}=\frac{k+1}{n} \cdot \frac{n-k}{n} \cdot T_{k-1},
and hence
Fk+1Fk=k+1nnknnk=(k+1)(nk)nk=1k(k+1)nkn. \frac{F_{k+1}}{F_{k}}=\frac{k+1}{n} \cdot \frac{n-k}{n} \cdot \frac{n}{k}=\frac{(k+1)(n-k)}{n k}=1-\frac{k(k+1)-n}{k n} .
This tells us in particular that Fk+1F_{k+1} is greater than FkF_{k} if and only if
k(k+1)<n. k(k+1)<n .
Taking into account that n=10000n=10000, this happens if and only if k99k \leq 99 (it suffices to observe that k(k+1)k(k+1) is an increasing function of the positive integer kk and the inequalities 99100<10000and99 \cdot 100<10000 \mathrm{and} 100101>10000100 \cdot 101>10000 hold).
It follows that the value of FkF_{k} initially increases until it reaches the maximum when k=100k=100, and then decreases from there on until the end of the competitors.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.