16
$\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$
12
  • 11
    $\begingroup$ I am interested in the evidence, if any, that this puzzle actually has anything to do with Pythagoras. $\endgroup$
    – Gareth McCaughan
    Jun 20, 2017 at 10:17
  • 8
    $\begingroup$ If the puzzle is taken from somewhere else, you need to cite your source. $\endgroup$
    – Gareth McCaughan
    Jun 20, 2017 at 12:06
  • 3
    $\begingroup$ @GarethMcCaughan I think Pythagoras just wanted to be the 10th guest $\endgroup$ Jun 20, 2017 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, 2017 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, 2017 at 11:03

6 Answers 6

24
$\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$
4
  • $\begingroup$ In fact, the closest integer to $\sqrt{n}$ gets the most... or equal most $\endgroup$
    – Wen1now
    Jun 20, 2017 at 9:56
  • $\begingroup$ so for n=2 and n=3 this convoluted approach is completely fair :-) $\endgroup$ Jun 20, 2017 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, 2017 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$ Jun 21, 2017 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$
2
  • $\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, 2017 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, 2017 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$
2
  • $\begingroup$ Unfortunately this is Puzzling, if you went to Programming Puzzles and Code Golf you'd have more competition. $\endgroup$
    – boboquack
    Jun 21, 2017 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, 2017 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.