Here is my take1 on the June 19th Huge Pie puzzle in the Guardian:

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. Who gets the biggest piece?"

Tables are always good to get a quick overview of what we’ve got, the tricky part being the rest of the pie:

Guest Percentage Rest of pie (before guest is served)
1 \(\frac{1}{100}\) \(\frac{100}{100}\)
2 \(\frac{2}{100}\) \(\frac{100}{100}\cdot\left(1 - \frac{1}{100}\right) = \frac{100}{100}\cdot\frac{99}{100}\)
3 \(\frac{3}{100}\) \(\frac{100}{100}\cdot\left(1 - \frac{1}{100}\right)\cdot\left(1 - \frac{2}{100}\right) = \frac{100}{100}\cdot\frac{99}{100}\cdot\frac{98}{100}\)
\(\vdots\) \(\vdots\) \(\vdots\)
99 \(\frac{99}{100}\) \(\frac{100}{100}\cdot\frac{99}{100}\cdot\ \cdots\ \cdot\frac{2}{100}\)
100 \(\frac{100}{100}\) \(\frac{100}{100}\cdot\frac{99}{100}\cdot\ \cdots\ \cdot\frac{1}{100}\)

If we number the guests \(i = 1...100\) then each one of them gets a percentage \(p_i = \frac{i}{100}\) of the rest of the pie at the time she is being served, and we can write this rest as \(r_i = \prod_{j=0}^{i-1} \frac{100 - j}{100}\). The actual size of the piece of pie that guest \(i\) gets is \[s_i = p_i\cdot r_i = \frac{i}{100}\cdot\prod_{j=0}^{i-1} \frac{100 - j}{100}.\] Of course, for the very next guest \(i + 1\) we have \[s_{i+1} = p_{i+1}\cdot r_{i+1} = \frac{i+1}{100}\cdot\prod_{j=0}^{i} \frac{100 - j}{100}.\] The difference in their pieces’ sizes is

\[\begin{align}\label{eq:diff} s_{i+1} - s_i &= \frac{i+1}{100}\cdot\prod_{j=0}^{i} \frac{100 - j}{100} - \frac{i}{100}\cdot\prod_{j=0}^{i-1} \frac{100 - j}{100} \\ &= \frac{i+1}{100}\cdot\frac{100 - i}{100}\cdot\prod_{j=0}^{i-1} \frac{100 - j}{100} - \frac{i}{100}\cdot\prod_{j=0}^{i-1} \frac{100 - j}{100} \\ &= \left(\frac{i+1}{100}\cdot\frac{100 - i}{100} - \frac{i}{100}\right)\prod_{j=0}^{i-1} \frac{100 - j}{100} \end{align}\]

For the first few guests, sizes are increasing (you can check this easily from the table above) but at some point this trend must be reversed. We are searching for the guest with the largest piece of pie, so we will look for the first instance of \(s_{i+1} - s_i\) being negative. Because \(\prod_{j=0}^{i-1} \frac{100 - j}{100}\) is always \(> 0\) this will occur when the term in parentheses becomes negative: \[\begin{align} & &\frac{i+1}{100}\cdot\frac{100 - i}{100} - \frac{i}{100} &< 0 \\ &\iff &(i+1)(100-i) - 100\,i &< 0\\ &\iff &100\,i -i² + 100 - i - 100\,i &< 0 \\ &\iff &i² + i - 100 &> 0 \end{align}\]

This inequality holds true for all \(i \geq 10\). And thus the guest with the largest piece of pie is number \(10\).

With the help of R, we can also solve the puzzle rather more quickly by brute force. In keeping with our variable names from above:

i <- 1:100                       # guest numbers
p <- i/100                       # percentages
r <- c(1, cumprod(1 - p))[i]     # rests before guests are served
s <- p * r                       # sizes of pieces of pie

First, we may check that the whole pie gets eaten:

all.equal(sum(s), 1)
## [1] TRUE

And now we simply search for the index of the largest piece of pie:

imax <- which.max(s)
## [1] 10

Let’s wrap this up with a nice plot illustrating pieces of pie sizes:

l <- list(Guest = i, Rest = r, Percentage = p, Size = s)
df <- as_tibble(l) %>% 
    mutate(gets_largest_piece = Guest == imax)
ggplot(df, aes(x = Guest, y = Size)) +
    geom_col(aes(fill = gets_largest_piece),
             col = "white", width = 1, show.legend = FALSE) +
    xlim(0, 40) +
    scale_y_continuous("Size in % of whole pie", labels = scales::percent) +
    scale_fill_manual(values = c("lightgray", "skyblue")) +

Take-home message: Be among the first 30 guests or so in the queue because otherwise you’ll have to be content with barely some crumbs…

  1. I know I am writing this post at a time when the solution has already been published. But I haven’t had a look at the solution yet, promise! Gotta believe me here…