15
$\begingroup$

This is a puzzle by the famous mathematician Pythagoras, who is widely known for his theorem on triangles. Here is a Puzzle:

A huge pie is divided among 100 guests. The first guest gets 1% of the pie. The second guest gets 2% of the remaining part. The third guest gets 3% of the rest, etc. The last guest gets 100% of the last part.

Now the question is: who gets the biggest piece?

[This puzzle comes from Pythagoras magazine and, more specifically, from a recently-published collection of their puzzles. The poster of this puzzle probably found it on the Guardian newspaper's website but neglected to say so, hence this note.]

$\endgroup$
  • 10
    $\begingroup$ I am interested in the evidence, if any, that this puzzle actually has anything to do with Pythagoras. $\endgroup$ – Gareth McCaughan Jun 20 '17 at 10:17
  • 8
    $\begingroup$ If the puzzle is taken from somewhere else, you need to cite your source. $\endgroup$ – Gareth McCaughan Jun 20 '17 at 12:06
  • 3
    $\begingroup$ @GarethMcCaughan I think Pythagoras just wanted to be the 10th guest $\endgroup$ – Totumus Maximus Jun 20 '17 at 15:07
  • 2
    $\begingroup$ Ashwin Indianic, you've posted three puzzles here so far. All of them have come from other sources which you haven't linked to or credited. We have a strict policy against plagiarism here; please cite your sources in future. Thanks! $\endgroup$ – Gareth McCaughan Jun 21 '17 at 8:37
  • 2
    $\begingroup$ (Sorry, that may not have been clear. I mean: If Way2 shows you a puzzle and you want to post it here, then you need to credit not Way2 but whoever actually made the puzzle, and if Way2 doesn't show you that information then you need to find it out some other way.) $\endgroup$ – Gareth McCaughan Jun 21 '17 at 11:03
22
$\begingroup$

A quick excel document shows that the tenth guest gets the most:

Excel

which leads me to believe it is $\sqrt{n}$ where $n$ is the number of guests. A proof may be coming soon.

Proof:

Let $S_{n,k}$ be the amount the kth person gets if there are n people. Then

$\begin{align*} S_{n,k} &=\frac{k}{n}\times \frac{n}{n}\times \frac{n-1}{n} \times \cdots \times \frac{n-k+1}{n} \\ &= \frac{kn!}{(n-k)!n^{k+2}} \end{align*}$

Now

$\begin{align*} &S_{n,k}<S_{n,k+1}\\ \implies & \frac{kn!}{(n-k)!n^{k+2}}<\frac{(k+1)n!}{(n-k-1)!n^{k+3}}\\ \implies & nk<(n-k)(k+1)\\ \implies & k^2+k<n \end{align*}$

So $S_{n,k}$ is increasing in $k$ precisely when $k^2+k<n$ which means that when $n=100$, if $k\leq9$ it increases and when $k\geq10$ it decreases. So the tenth guest gets the most.

$\endgroup$
  • $\begingroup$ In fact, the closest integer to $\sqrt{n}$ gets the most... or equal most $\endgroup$ – Wen1now Jun 20 '17 at 9:56
  • $\begingroup$ so for n=2 and n=3 this convoluted approach is completely fair :-) $\endgroup$ – Kate Gregory Jun 20 '17 at 16:50
  • $\begingroup$ @KateGregory Yes, for n=2. But for n=3, doesn't the second person get 2/3 of the remainder (2/3), i.e. 4/9, vs 1/3 for the first? $\endgroup$ – Lawrence Jun 21 '17 at 16:27
  • $\begingroup$ ah, you're right, I was decrementing the denominator: 1/3, half the rest, all the rest. That's always fair for all n. $\endgroup$ – Kate Gregory Jun 21 '17 at 16:33
11
$\begingroup$

Well, the guests get the following parts:

$$\frac{1}{100}$$
$$\frac{99}{100}\cdot\frac{2}{100}$$
$$\frac{99}{100}\cdot\frac{98}{100}\cdot\frac{3}{100}$$
$$\frac{99}{100}\cdot\frac{98}{100}\cdot\frac{97}{100}\cdot\frac{4}{100}$$
$$\vdots$$
$$\frac{99}{100}\cdot\frac{98}{100}\cdot\frac{97}{100}\cdot\dots\cdot\frac{2}{100}\cdot\frac{1}{100}\cdot\frac{100}{100}$$

Now observe that for the $n^{th}$ guest, this is equal to:

$$\frac{99!}{(100-n)!}\cdot\frac{n}{100^n}$$

And it changes by a ratio of: (from the $n^{th}$ to the $(n+1)^{th}$ person)

$$(100-n)\cdot\frac{n+1}{n}\cdot\frac{1}{100}$$
$$=\left(1-\frac{n}{100}\right)\cdot\frac{n+1}{n}$$
$$=\frac{n+1}{n}-\frac{n+1}{100}$$
$$=\frac{100n+100}{100n}-\frac{n^2+n}{100n}$$
$$=\frac{-n^2+99n+100}{100n}$$

But for the portion of the slice to increase, we want this to be above $1$:

$$\frac{-n^2+99n+100}{100n}\ge1$$
$$\Leftrightarrow-n^2+99n+100\ge100n$$
$$\Leftrightarrow-n^2-n+100\ge0$$
$$\Leftrightarrow-\left(n-\frac{1}{2}-\frac{\sqrt{401}}{2}\right)\left(n-\frac{1}{2}+\frac{\sqrt{401}}{2}\right)\ge0$$

So we have:

The ratio $\ge1\Leftrightarrow\frac{1}{2}-\frac{\sqrt{401}}{2}\ge n\ge\frac{1}{2}+\frac{\sqrt{401}}{2}$ and $\le1$ otherwise (note by our early equation it is $\ge0$ if $-1\le n\le100$)

And since:

$$\frac{1}{2}+\frac{\sqrt{401}}{2}\approx10.51249219725$$

the slice is maximised at the:

$10^{th}$ guest

(Note: this is easy to generalise)

$\endgroup$
9
$\begingroup$

Let's say after $k-1$ guests have had a slice there is $X_{k-1}$ cake left.

The $k^{th}$ guest gets $X_{k-1}\frac{k}{100}$ cake.

The $(k+1)^{th}$ guest gets $X_{k-1}\left(1-\frac{k}{100}\right)\frac{k+1}{100}$ cake.

Let us assume that the $(k+1)^{th}$ guest gets more cake than the $k^{th}$ guest, i.e.: $$\left(1-\frac{k}{100}\right)\frac{k+1}{100}\gt \frac{k}{100}$$

$$(100-k)(k+1)\gt 100k$$

$$-k^2-k+100\gt 0$$

This is true for $k=1\dots 9$, and false for $k\ge 10$, so the $11^{th}$ guest gets less than the $10^{th}$ guest, who gets more than the $9^{th}$ and we can proceed using induction to show that the $10^{th} $ guest gets the largest slice of cake.

$\endgroup$
  • $\begingroup$ +1 This is by far the simplest, most insightful, and most elegant solution, because it avoids the brute force work exhibited in all the others (to date). Although it might not be something Pythagoras could have accomplished, Euclid might have been able to. $\endgroup$ – whuber Jun 20 '17 at 19:53
  • $\begingroup$ Nice! The only thing is that you do not mention the 100th guest, which might still have more than number 10. $\endgroup$ – Sjorszini Jun 21 '17 at 17:47
4
$\begingroup$

I am a swift developer so I made a program in which I have calculated the size of pizza for each person till 100.

enter image description here

To conclude, 10th person who is getting 6.2815 is getting the biggest piece of pizza.

$\endgroup$
3
$\begingroup$

I answered this question as a code challenge; I managed it as a one-liner in MATLAB using 34 characters:

[~,i]=min(diff(cumprod(1:-.01:0)))

The output is, of course, 10. To generalize this to n people, the same number of characters is required, provided you define n beforehand:

[~,i]=min(diff(cumprod(1:-1/n:0)))

Of course, if I had read the other answers before trying it myself, I would have come to the (nearly enough) twice as efficient solution to the general case with only 16 characters:

i=round(sqrt(n))

Thanks for the fun puzzle!

$\endgroup$
  • $\begingroup$ Unfortunately this is Puzzling, if you went to Programming Puzzles and Code Golf you'd have more competition. $\endgroup$ – boboquack Jun 21 '17 at 2:11
  • $\begingroup$ I enjoy that site as well, but stumbling across this one was too tempting to pass up! And believe me, I can't come close to competing with most of those in the Code Golf realm... $\endgroup$ – J. Tibbs Jun 21 '17 at 18:15
1
$\begingroup$

A graphical solution could be the following:

who's getting more pizza

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.