# Dividing a cake between $n-1$, $n$, or $n+1$ guests

A housewife is waiting for guests and has prepared a cake. She doesn't know how many guests will come, but it will be $$n-1$$, $$n$$, or $$n+1$$. What is the minimal number $$f(n)$$ of pieces the cake should be cut to make it possible to divide between guests equally?

For $$n=2$$, $$f(n)=f(2)=4$$:

The problem was posed 16.10.2018 by Oleksandr Maksymets on page 76 of Volume 2 of the Lviv Scottish Book.

The prize: Cooked duck or lunch + beer!

• A more-or-less obvious upper bound for $f(n)$ is $3n-2$: divide the cake into $n$ pieces of size $\frac1{n+1}$ plus $n-1$ pieces of size $\frac1{n(n+1)}$ and plus $(n-1)$ pieces of size $\frac1{(n+1)n(n-1)}$. So, the question is if this upper bound $3n-2$ is exact. Commented May 4, 2019 at 6:30
• $f(3)=6$. To see that $f(3)\ge 6$, assume that the cake can be divided into less that 6 pieces. If 3 guests come then one of them should obtain a single piece, which means that there is a piece of size $\frac13$. But this piece is too large when 4 guests will come. So, $f(3)\le 6$. To see that $f(3)\le 6$, just divide the cake into 3 pieces of size $\frac14$ and 3 pieces of size $\frac1{12}$. Commented May 4, 2019 at 7:49
• Commented May 4, 2019 at 7:52
• if $n$ is odd, $3n-3$ pieces are enough, since the regular $k$-gons for $k=n-1, n, n+1$ inscribed in the same circle and sharing the same vertex have in total $3n-3$ vertices. Commented May 4, 2019 at 11:11
• Maybe this is a cultural thing or something lost in translation, but it's 2019 and this is a site for professional mathematicians, so I feel it would be better if the word "housewife" were replaced by some other noun such as "mathematician". Commented May 7, 2019 at 20:47

One has $$f(n) = 2n + O(\sqrt{n})$$ for sufficiently large $$n$$.

First, the lower bound. No cake piece can be of size $$\frac{1}{n}$$, since otherwise it would not be possible to serve $$n+1$$ guests. Hence if there are $$n$$ guests, each guest must be served at least two pieces, so there must be at least $$2n$$ pieces. So $$f(n) \geq 2n$$. [EDIT: as already noted by Petrov in a comment, this bound can be improved a little bit to $$f(n) \geq 2n+1$$.]

Now, the upper bound. The above analysis suggests a construction in which most guests are served exactly two pieces, creating three nearly perfect matchings on a graph of about $$2n$$ vertices (representing the pieces). After some experimentation with Cayley graph type constructions (trying to get as much of a symmetry reduction as I could), I hit upon a construction in which these three almost perfect matchings were simultaneously bipartite, as follows.

Firstly, it suffices to cut some of the cake into $$2n-O(\sqrt{n})$$ pieces in such a way that $$n - O(\sqrt{n})$$ disjoint slices of the form $$\frac{1}{n'}$$ can be served for $$n'=n-1,n,n+1$$, since to serve the remaining slices to the $$n' - (n-O(\sqrt{n})) = O(\sqrt{n})$$ guests not already served one can perform the construction in Ilya's answer by concatenating all the unserved portions of cake into a single interval (of length $$O(1/\sqrt{n})$$) and partitioning it into equal slices of length $$1/n'$$, creating $$O(\sqrt{n})$$ additional cuts three times.

Now set $$m := \lfloor \sqrt{n}\rfloor$$. Define the functions $$a, b: \{1,\dots,m\}^2 \to {\bf R}^+$$ by \begin{align*} a(i,j) &:= \frac{1}{2n} + \frac{i}{n(n-1)} + \frac{j}{n(n+1)}\\ b(i,j) &:= \frac{1}{n} - a(i,j). \end{align*} The following claims are easily verified for $$n$$ large enough:

1. All the $$a(i,j), b(i,j)$$ are positive (in fact they are $$\frac{1}{2n} + O( n^{-3/2})$$).
2. One has $$a(i,j) + b(i,j) = \frac{1}{n}$$, $$a(i+1,j) + b(i,j) = \frac{1}{n-1}$$, and $$a(i,j-1) + b (i,j) = \frac{1}{n+1}$$ whenever $$(i,j)$$ is such that the left-hand side is well-defined.

We now divide the cake into $$2m^2 = 2n - O(\sqrt{n})$$ pieces of length $$a(i,j), b(i,j)$$ for $$(i,j) = \{1,\dots,m\}^2$$, which uses up $$m^2 \frac{1}{n} \leq 1$$ of the cake since $$a(i,j)+b(i,j)=\frac{1}{n}$$, so this is a valid sub-partition of the cake by item 1. From item 2 above we see that we can serve at least $$m(m-1) = n - O(\sqrt{n})$$ portions of size $$1/n'$$ for any $$n' = n-1, n, n+1$$, as claimed.

It seems quite challenging to improve the $$O(\sqrt{n})$$ error significantly (the problem being the lack of short integer linear relations between $$\frac{1}{n-1}$$, $$\frac{1}{n}$$, $$\frac{1}{n+1}$$ to reduce the "boundary" of constructions such as the one I gave). It could possibly be asymptotically optimal up to constants; tentatively it seems that it may be possible to prove this using some sort of two-dimensional discrete isoperimetric inequality.

• Explicitly, this gives $f(n)\le2m^2+2(n-m(m-1))+n-m^2=3n-m^2+2m\le2n+4m=2n+4\lfloor\sqrt n\rfloor$ for all $n$. (The argument is valid when $\frac{2m}{n^2-1}<\frac1{2n}$, i.e., $n\ge17$, but the $2n+4\lfloor\sqrt n\rfloor$ bound holds for $n\le16$ as well, as it is then worse than the trivial bound $3n-2$, or $3n-3$ for odd $n$.) Commented Aug 10, 2023 at 11:15
• I think this can be improved to $f(n)\le2n+2\lfloor\sqrt n\rfloor+2$ if you include $a(i,j)$ and $b(i,j)$ for $n-m^2$ consecutive pairs $(i,j)$ with $i=m+1$ or $j=m+1$. Commented Aug 10, 2023 at 12:37
• More precisely, $2n+\lceil\sqrt{4n}\rceil-2$ (taking also into account that in the “partition the remaining interval” step, we don’t need to cut the endpoint). (Sorry for all these comments, I swear I will stop.) Commented Aug 10, 2023 at 13:34
• All right, one more comment: starting the indices $i,j$ at $0$ rather than $1$ makes it much easier to verify that the bound also holds for small $n$. In fact, they could even be made to go from $-m/2$ to $m/2$ or so. Commented Aug 10, 2023 at 15:37
• Great solution! Thank you, Terry Tao. Also thanks to @Emil Jerabek for tightening the upper bound. Maybe, for numbers of form $m(m+1)$ some even better upper bounds can be found? Commented Aug 12, 2023 at 9:24

Too long for a comment. Here is a way to use around $$8n/3$$ pieces.

Cut out as many pieces of length $$1/(n+1)+1/n+1/(n-1)$$ as you can; there are $$k\approx n/3$$ of them. Imagine each such piece as a segment; this segment can be cut into pieces $$1/(n+1),1/n,1/(n-1)$$ (in this order) and $$1/(n-1),1/(n+1),1/n$$ (in this order). Mark cutting points for both cuttings, and cut by all of them. Notice that pieces of the same desired length do not overlap within the segment.

Thus, after $$5k$$ cuttings you get $$2k$$ non-overlapping pieces of each type separately. To arrange other $$n-1-2k$$ pieces of length $$1/(n-1)$$, take away those $$2k$$ pieces of length $$1/(n-1)$$, form a single segment of the others, and cut it into desired pieces of length $$1/(n-1)$$ by $$n-2-2k$$ cuts. Similarly, we need $$(n-1-2k)+(n-2k)$$ additional cuts in order to get the other two distributions possible.

• Sorry, but I do not understand your idea. You just cut the cake into pieces of size $\frac1{n+1}$, $\frac1{n}$ or $\frac1{n-1}$. But the pieces $\frac1n$ and $\frac1{n-1}$ are forbidden as they are too large in case $(n+1)$ guests will come. Commented May 4, 2019 at 22:04
• I think he is cutting pieces again, into subpieces, so the sizes are smaller Commented May 4, 2019 at 22:35
• @TarasBanakh: In the first part, I cut the same piece into those segments twice. Now I tried to make it clear in the text. Commented May 5, 2019 at 4:38
• @IlyaBogdanov Thank you for the explanations. Now I have understood. Very cute! Commented May 5, 2019 at 8:12

Writing down the details of the argument of Ilya Bogdanov, we can obtain the following upper bound:

Theorem. $$f(n)\le\frac83n-1$$ for every $$n\ge 2$$.

Proof. If $$n=3k+1$$ or $$n=3k+2$$, then following the idea of Ilya Bogdanov, divide the cake into $$k$$ pieces of length $$\frac1{n-1}+\frac1n+\frac1{n-1}$$. This is possible since $$k(\tfrac1n+\tfrac1{n-1}+\tfrac1{n+1})<1$$. Cutting each of these pieces into 5 subpieces of lengths $$\tfrac1{n+1},\;\;\tfrac1{n-1}-\tfrac1{n+1},\;\;\tfrac1{n+1}+\tfrac1n-\tfrac1{n-1},\;\;\tfrac1{n-1}-\tfrac1n,\;\; \tfrac1n,$$ we can compose of these subpieces two pieces of any of the lengths: $$\frac1{n-1}$$, $$\frac1n$$, $$\frac1{n+1}$$. Cutting these $$k$$-pieces with 5 subpieces requires $$5k+1$$ cuts. To produce the remaining number of pieces it is necessary to make $$((n-1)-2k-1)+(n-2k-1)+(n+1-2k-1)=3n-6k-3$$ cuts. Summing up we obtain $$5k+1+3n-6k-3=3n-k-2$$ cuts.

Therefore, for $$n=3k+1$$ we have the desired upper bound: $$\begin{multline*} f(n)=f(3k+1)\le 3n-k-2=(9k+3)-k-2=8k+1=\\ =\tfrac83(n-1)+1=\tfrac83n-\tfrac53<\tfrac83n-1. \end{multline*}$$ For $$n=3k+2$$ we have a similar upper bound: $$\begin{multline*} f(n)=f(3k+2)\le 3n-k-2=(9k+6)-k-2=8k+4=\\=\tfrac83(n-2)+4=\tfrac83n-\tfrac43<\tfrac83n-1. \end{multline*}$$

For $$n=3k$$ we divide the cake into $$k-1$$ pieces of length $$\frac1{n-1}+\frac1n+\frac1{n+1}$$ and one piece of lenth $$\frac1{n-1}+\frac2{n+1}$$. Since $$(k-1)(\tfrac1{n-1}+\tfrac1n+\tfrac1{n+1})+(\tfrac1{n-1}+\tfrac2{n+1})<1$$such division is possible. Then divide each of $$(k-1)$$ pieces like in the preceding case. The remaining piece of length $$\frac1{n-1}+\frac2{n+1}$$ divide into 5 pices of lengths: $$\tfrac1{n+1},\;\; \tfrac1{n-1}-\tfrac1{n+1},\;\;\tfrac2{n+1}-\tfrac1{n-1},\;\; \tfrac1{n-1}-\tfrac1{n+1},\;\;\tfrac1{n+1}.$$ Of these 5 subpieces we can compose either 2 pieces of length $$\frac1{n-1}$$ or 3 pieces of length $$\frac1{n+1}$$.

Then it suffices to make $$(5k+1)+((n-1)-2k-1)+(n-2(k-1)-1)+((n+1)-(2k+1)-1)=3n-k-1$$cuts to have the required number of pieces of length $$\frac1{n-1}$$, $$\frac1n$$ or $$\frac1{n+1}$$. Then $$f(n)=f(3k)\le 3n-k-1=8k-1=\tfrac83n-1.\qquad\square$$

Remark. Comparing the known values (and upper bounds) of the function $$f(n)$$ for $$n\le 5$$ (resp. for $$n\le 8$$) with the upper bound $$u(k)=\lfloor\frac83n-1\rfloor$$, we see that $$f(n)=u(n)$$ only for $$n=2$$ and $$n=4$$:

$$f(2)=4=u(2)$$,

$$f(3)=6<7=u(3)$$,

$$f(4)=9=u(4)$$,

$$f(5)=11<12=u(5)$$,

$$f(6)=13<15=u(6)$$,

$$f(7)=15<17=u(7)$$,

$$f(8)\le 18<20=u(8)$$.

It is interesting to calculate the precise values of $$f(n)$$ for small $$n\ge6$$.

Remark. I have updated the values of $$f(n)$$ for n=6,7,8 according to the comments and answers of Max Alekseyev, Gerry Myerson, and Gabe K.

$$f(7)=15$$.

$$f(7)\ge15$$ follows from a comment of Fedor Petrov on the original question, so it suffices to find a way to cut the cake into $$15$$ pieces so as to serve $$6$$, $$7$$, or $$8$$ guests.

Let the size of the cake be $$168$$ (so that all the following computations involve only whole numbers). Let the $$15$$ pieces be of sizes $$1,2,4,5,7,8,10,11,13,14,16,17,19,20,21$$ (that is, every size not a multiple of $$3$$ up to $$20$$, and $$21$$). Then

$$1+20=2+19=4+17=5+16=7+14=8+13=10+11=21,$$

$$4+20=5+19=7+17=8+16=10+14=11+13=1+2+21(=24),$$

$$7+21=8+20=4+5+19=11+17=2+10+16=1+13+14(=28).$$

Note that this disproves my conjecture $$f(n)=[5n/2]-1$$ which evaluates to $$16$$ when $$n=7$$.

• The value $f(7)=15$ shows the difference of the problem with $n-1,n,n+1$ guests and the problem with $1,2,3,\dots,n$ guests, considered in oeis.org/A265286 Commented May 6, 2019 at 5:48
• By the way, what is the exact value of $f(6)$? At the moment we have only the bounds $13\le f(6)\le 14$. Commented May 6, 2019 at 5:50
• @Taras, I'm convinced it's $14$, but every time I try to write out a proof, new cases come up that I haven't considered. Commented May 6, 2019 at 6:49
• @TarasBanakh: In fact, $f(6)=13$ - see my answer below. Commented Sep 22, 2020 at 16:03

Proposition. $$f(n)\ge 2n+\tfrac 13\left(\sqrt{\tfrac{n}3+1}-2\right)$$ for any natural $$n\ge 13$$.

Proof. Fix the cake cutting with the minimum number $$f=f(n)$$ of slices. We shall work with the graph $$G$$ from David E Speyer’s answer, defined as follows:

The vertices are the slices of cake. There are edges in three colors: red, green and blue. For each person who gets exactly two slices in the $$n-1$$ person solution, draw a red edge between the two pieces that person gets. Similarly, draw green edges for each person who gets exactly two slices in the $$n$$ person solution, and draw exactly blue edges for each person who gets two slices in the $$n+1$$ person solution.

Let $$V_r$$ be the set of slices given to persons obtaining at the number of slices distinct from two in the $$n-1$$ person solution, similarly define $$V_g$$ and $$V_b$$. Moreover, let $$V’$$ be the set of slices of size $$\tfrac 1{n+1}$$. Clearly, $$V’\subset V_b$$. David E Speyer at the beginning of his answer showed that $$f\ge 2n+|V_g|/3$$ and $$f\ge 2n-2+|V_r|/3$$. Similarly we can show that $$f\ge 2n+2+(|V_b|-4|V’|)/3$$. Put $$F=3f-6n$$. Then $$|V_g|\le F$$, $$|V_r|\le F+6$$, and $$|V_b|-4|V’|\le F-6$$.

Let $$c$$ and $$d$$ be any two distinct colors among $$r$$ (red), $$g$$ (green), and $$b$$ (blue). Let a $$cd$$-path be a path whose edges have either the color $$c$$ or the color $$d$$. Note that a single vertex is a $$cd$$-path too. It is easy to check that there are no closed $$cd$$-paths. We shall call a $$cd$$-path short, if its length is less than $$n-2$$, and long, otherwise.

It is easy to check the following lemma.

Lemma 1. Let $$c$$ and $$d$$ be any two distinct colors among red, green, and blue. Then each vertex of $$G$$ belongs to a unique maximal $$cd$$-path. The end vertices of any maximal $$cd$$-path $$C$$ belong to $$V_c\cup V_d$$. Moreover, if a maximal $$cd$$-path consists of only one vertex, then it belongs to $$V_c\cap V_d$$. Therefore $$|V_c|+|V_d|\ge 2N_{cd}$$, where $$N_{cd}$$ is the number of maximal $$cd$$-paths. $$\square$$

Given a slice $$v$$, let $$|v|$$ be its size. The simple straightforward calculations provide the following lemma.

Lemma 2.. Let $$c$$ and $$d$$ be any two distinct colors among red, green, and blue. Let $$P$$ be any $$cd$$-path beginning from a vertex $$v$$ along the edge of color $$c$$. Let $$u$$ be any vertex of $$P$$ and $$p$$ be the distance from $$u$$ to $$v$$. Then $$|u|=|v|+(k_d-k_c)p/2$$, if $$p$$ is even, and $$|u|=k_c-|v|+(k_c-k_d)(p-1)/2$$, if $$p$$ is odd, where $$k_r=\tfrac 1{n-1}$$, $$k_g=\tfrac 1{n}$$, and $$k_b=\tfrac 1{n+1}$$. If $$|u|=|v|=\tfrac 1{n+1}$$ then $$d$$ is blue, and, moroever, if $$c$$ is green then $$p=2n-1$$ and if $$c$$ is red then $$n$$ is odd and $$p=n-2$$. Note that in both cases the path $$P$$ is long, so if $$P$$ is short then it contains at most one vertex from $$V’$$. $$\square$$

Lemma 3. Let $$c$$, $$d$$, and $$e$$ be the colors red, green, and blue in some order, $$v$$ and $$u$$ be distinct vertices of $$G$$ such that there exist a $$cd$$-path $$P$$ from $$v$$ to $$u$$ and a $$ce$$-path $$Q$$ from $$u$$ to $$v$$. Let $$p$$ and $$q$$ be the length of the path $$P$$ and $$Q$$, respectively, and $$p+q$$ is even. Then the path $$P$$ is long.

Proof. Let $$C$$ be the cycle which first follows $$P$$ and next follows $$Q$$. Let $$e_1$$, $$e_2$$, .., $$e_{p+q}$$ be the edges of $$C$$ enumerated along the cycle. We refer to the answer by David E Speyer again.

Let $$r$$ be the difference between the number of red edges among $$\{ e_1, e_3, e_5, \dots \}$$ and the number of red edges among $$\{ e_2, e_4, e_6, \dots \}$$, and define $$g$$ and $$b$$ similarly. Then we have $$r+g+b=0$$ ... and $$r/(n-1) + g/n + b/(n+1) = 0$$. .... Put $$\gamma = GCD(n-1, 2)$$. The integer solutions to $$r+g+b=\tfrac{r}{n-1} + \tfrac{g}{n} + \tfrac{b}{n+1} = 0$$ are the integer multiples of $$\tfrac{1}{\gamma} (n-1, -2n, n+1)$$.

Recall that each cycle in $$G$$ has edges of all three colors. Let $$R$$ be the shortest path among $$P$$ and $$Q$$. Then there exists a color among $$d$$ and $$e$$ such that $$C$$ has $$x>0$$ edges of this color and all these edges belong to $$R$$. When we follow $$R$$, the colors of its edges alternate, so David E Speyer’s arguments imply that $$x\ge \tfrac{n-1}{\gamma}\ge \tfrac{n-1}{2}$$. Thus the length of $$R$$ is at least $$n-2$$, and so the length of $$P$$ is at least $$n-2$$ too. $$\square$$

Lemma 4. Let $$c$$, $$d$$, and $$e$$ be the colors red, green, and blue in some order, $$P$$ be a short $$cd$$-path and $$Q$$ be a $$ce$$-path. Then $$P$$ and $$Q$$ have at most two common vertices.

Proof. Suppose for a contradiction that $$P$$ and $$Q$$ have three common vertices $$v_1$$, $$v_2$$, and $$v_3$$. Renaming these vertices, if needed, we can suppose that $$v_2$$ is between $$v_1$$ and $$v_3$$ along the path $$P$$. Let $$P_{12}$$ be the path from $$v_1$$ to $$v_2$$ along $$P$$, $$P_{23}$$ be the path from $$v_2$$ to $$v_3$$ along $$Q$$, $$Q_{21}$$ be the path from $$v_2$$ to $$v_1$$ along $$Q$$, and $$Q_{32}$$ be the path from $$v_3$$ to $$v_2$$ along $$Q$$, $$p_{12}$$, $$p_{23}$$, $$q_{21}$$, and $$q_{32}$$ be the length of the path $$P_{12}$$, $$P_{23}$$, $$Q_{21}$$, and $$Q_{32}$$, respectively. By Lemma 3, both $$p_{12}+q_{21}$$ and $$p_{23}+q_{32}$$ are odd. Let $$P_{13}$$ be the path from $$v_1$$ to $$v_3$$ which first follows $$P_{12}$$ and next follows $$P_{23}$$ and $$Q_{31}$$ be the path from $$v_3$$ to $$v_1$$ which first follows $$Q_{32}$$ and next follows $$Q_{12}$$. Then the path $$P_{13}$$ is a subpath of the path $$P$$ and so it is short, but the sum $$p_{12}+ p_{23}+q_{21}+q_{32}$$ of the lengths of $$P_{13}$$ and $$Q_{31}$$ is even, that contradicts Lemma 3. $$\square$$

By Lemma 2, each $$rg$$-path contains at most one vertex from $$|V’|$$, so $$N_{rg}\ge |V’|$$. By Lemma 1, $$|V_r|+|V_g|\ge 2N_{rg}\ge 2|V’|$$. But $$|V_g|\le F$$, $$|V_r|\le F+6$$, and $$|V_b|-4|V’|\le F-6$$. Since $$|V_r|+|V_g|\ge 2|V’|$$, we have $$|V_b|\le 2(|V_r|+|V_g|)+F-6\le 5F+6$$.

Suppose first that there exist two distinct colors $$c$$ and $$d$$ among $$r$$, $$g$$, and $$b$$, and a $$cd$$-path $$P$$ of length $$n-3$$. Let $$e$$ be the color among $$r$$, $$g$$, and $$b$$ distinct from $$c$$ and $$d$$. By Lemma 4, no $$ce$$-path has three common vertices with $$P$$, so there are at least $$\tfrac{n-2}2$$ maximal $$ce$$-paths. By Lemma 1, $$|V_c|+|V_e|\ge n-2$$. Similarly we can show that $$|V_d|+|V_e|\ge n-2$$. Then $$F+F+6+2(5F+6)\ge |V_c|+|V_d|+2|V_e|\ge 2n-4$$, so $$F\ge \tfrac{n-11}6>\sqrt{\tfrac{n}3+1}-2$$ because $$n\ge 13$$.

Suppose now that all $$cd$$-paths are short for any two distinct colors $$c$$ and $$d$$ among red, green, and blue. Fix $$c$$ and $$d$$ and let $$e$$ be the remaining color. Let $$L_{cd}$$ be the length the longest $$cd$$-path. By the pigeonhole principle, $$L_{cd}+1\ge f/N_{cd}$$. By Lemma 4, $$N_{ce}\ge (L_{cd}+1)/2$$, so $$2N_{cd}N_{ce}\ge f$$. By Lemma 1, $$|V_c|+|V_d|\ge 2N_{cd}$$ and $$|V_c|+|V_e|\ge 2N_{ce}$$. Thus $$(|V_c|+|V_d|)(|V_c|+|V_e|) \ge 2f$$. Since $$(|V_g|+|V_r|)(|V_g|+|V_b|) \ge 2f$$, we obtain that $$(2F+6)(6F+6) \ge 2f=2F/3+4n$$. The last inequality implies $$F>\sqrt{\tfrac{n}3+1}-2$$, and so $$f>2n+\tfrac 13\left(\sqrt{\tfrac{n}3+1}-2\right)$$. $$\square$$

• What are the current lower and upper bounds for $f(n)$? $2n+\frac13(\sqrt{\frac n3+1}-2)\le f(n)\le 2n+\lceil 2\sqrt{n}\rceil-2$? Are they achieved for some special $n$? Commented Sep 2, 2023 at 8:04
• @LvivScottishBook Yes, this best known general upper bound was provided by Emil Jeřábek. Probably, I can make a bit better lower bound, but with more complicated expression. Namely, the exact solution of the last inequality for $F$ gives $F\ge (\sqrt{1153+432n}-71)/36$, which looks bigger than $\sqrt{n/3+1}-2$ at most by $1/36$, so it can improve the lower bound for $f(n)$ at most by $1/108$. Commented Sep 2, 2023 at 10:03
• There is a hope that both bounds can be improved with a more donkish approach. But the proof of the lower bound is already rather complicated, so I probably shall need a help of specialists in graph theory to continue it. These bounds are asymptotically the best known, but none of them is known to be achieved for some special $n$. The best known bounds for small values of $n$ are listed in Taras Banakh's answer. Commented Sep 2, 2023 at 10:03

$$f(6) = 13$$ with a cake of size $$210$$ and piece sizes: $$\{3, 5, 8, 10, 12, 13, 17, 18, 20, 22, 25, 27, 30\},$$ where $$17+25 = 5+10+27 = 20 + 22 = 3+8+13+18 = 12+30,$$ $$10+25 = 5+30 = 3+12+20 = 17+18 = 13 + 22 = 8+27,$$ $$5+25 = 3+27 = 10+20 = 12+18 = 13+17 = 30 = 8+22.$$ It was computed with via solving MILP as explained in my other answer.

$$\def\ZZ{\mathbb{Z}}$$This answer is an attempt to spell out what Terry Tao might have meant by "it may be possible to prove [the $$O(\sqrt{n})$$ lower bound is optimal] using some sort of two-dimensional discrete isoperimetric inequality." I haven't found such a proof; I am just trying to set up the notation.

First, notice that every cake slice has size $$\leq \tfrac{1}{n+1}$$ (so that we can serve $$n+1$$ people). Thus, in the solutions for $$n-1$$ and $$n$$ people, each person gets at least $$2$$ slices. Let $$c_i$$ be the number of slices that the $$i$$-th person gets in the $$n$$-person solution, and let $$\delta_0$$ be the total number of slices given to people who get $$\geq 3$$ slices in the $$n$$-person solution. Then the number of slices is $$\sum c_i = 2n + \sum (c_i-2) \geq 2n + \sum_{c_i \geq 3} c_i/3 = 2n + \delta_0/3.$$ Similarly, let $$\delta_-$$ be the total number of slices given to people who get $$\geq 3$$ slices in the $$n-1$$-person solution. Then the total number of slices is $$\geq 2n-2 + \delta_-/3$$. So we can hope to prove a $$c \sqrt{n}$$ lower bound by showing that $$\max(\delta_0, \delta_-) \geq c \sqrt{n}$$. (It seems harder to make use of the analogous $$\delta_+$$ number, because we would have to consider people who get exactly one slice, although there is probably a way to deal with this.)

Define a graph $$G$$ as follows: The vertices are the slices of cake. There are edges in three colors: red, green and blue. For each person who gets exactly two slices in the $$n-1$$ person solution, draw a red edge between the two pieces that person gets. Similarly, draw green edges for each person who gets exactly two slices in the $$n$$ person solution, and draw exactly blue edges for each person who gets two slices in the $$n+1$$ person solution. So $$\delta_-$$ is the number of edges which are not matched in the red subgraph, and $$\delta_0$$ is the number of edges that are not matched in the green subgraph. Recall that our goal is to lower bound $$\max(\delta_0, \delta_-)$$.

Consider any cycle of even length in $$G$$, with edges $$e_1$$, $$e_2$$, .., $$e_{2 \ell}$$. Let $$r$$ be the difference between the number of red edges among $$\{ e_1, e_3, e_5, \dots \}$$ and the number of red edges among $$\{ e_2, e_4, e_6, \dots \}$$, and define $$g$$ and $$b$$ similarly. Then we have $$r+g+b=0$$ (there are the same number of total edges of each parity) and $$r/(n-1) + g/n + b/(n+1) = 0$$ (count the total amount of cake in two ways).

Put $$\gamma = GCD(n-1, 2)$$. The integer solutions to $$r+g+b=\tfrac{r}{n-1} + \tfrac{g}{n} + \tfrac{b}{n+1} = 0$$ are the integer multiples of $$\tfrac{1}{\gamma} (n-1, -2n, n+1)$$.

Let $$A$$ be the abelian group $$A = \ZZ^3 {\Big /} \ZZ \tfrac{1}{\gamma} (n-1, -2n, n+1).$$ Let $$V$$ be the subset of $$A$$ consisting of $$(x,y,z)$$ with $$0 \leq x+y+z \leq 1$$. Let $$\Gamma$$ be the infinite directed graph whose vertex set is $$V$$ and where there is an edge from $$(x,y,z)$$ to $$(x+1, y,z)$$, $$(x, y+1, z)$$ and $$(x,y,z+1)$$. We color the edges of $$\Gamma$$ red, blue and green according to which of these three types they are.

I picture $$\Gamma$$ as a large cylinder tiled with hexagons. To see why I describe it this way; project $$\{ (x,y,z) \in \ZZ^3 : 0 \leq x+y+z \leq 1 \}$$ orthogonally onto the plane $$x+y+z=0$$. You get the vertices of a hexagonal tiling; and the edges which I described are the edges of that hexagonal tiling. We are supposed to quotient by the vector $$\tfrac{1}{\gamma} (n-1, 2n, n+1)$$, so we are getting a hexagonal tiling of a cylinder, rather than a hexagonal tiling of the plane.

The next step is easier to describe if $$G$$ is bipartite, so assume this for now. Let $$G_0$$ and $$G_1$$ be the black and white vertex sets of $$G$$. Map $$G$$ to $$\Gamma$$ as follows: Choose an arbitrary vertex of $$G_0$$ to map to $$(0,0,0)$$. Then, whenever we follow a red edge of $$G$$ from $$G_0$$ to $$G_1$$, go along the edge $$(x,y,z) \to (x+1, y, z)$$ in $$\Gamma$$. Similarly, map green edges from $$G_0$$ to $$G_1$$ to edges $$(x,y,z) \to (x, y+1, z)$$ in $$\Gamma$$, and map blue edges $$G_0 \to G_1$$ to edges $$(x,y,z) \to (x, y, z+1)$$ in $$\Gamma$$. The condition above on even cycles of $$G$$, combined with the fact that $$G$$ is bipartite so every cycle is even, shows that we get a well defined color preserving map $$G \to \Gamma$$.

If $$G$$ is not bipartite, we need to replace $$G$$ by its bipartite double cover $$DG$$, we then get a color preserving map $$DG \to \Gamma$$.

Our goal is to give a lower bound for the number of vertices of $$G$$ which are not matched in either the red or green subgraphs.

Roughly speaking, we want to prove that a subset of $$\Gamma$$ of size $$2n$$ (or $$4n$$, in the non-bipartite case) has at least $$c \sqrt{n}$$ vertices which are not matched in either the red or green subgraphs (although, we have to fudge a little because the map to $$\Gamma$$ might not be injective.)

A good first goal would be just to work with the planar hexagonal grid, and prove a discrete isoperimetric inequality stating that any subgraph on $$m$$ vertices has at least $$c \sqrt{m}$$ vertices one of whose three neighbors is missing. We can then try to put in the colors and deal with the quotient by $$\tfrac{1}{\gamma} (n-1, -2n, n+1)$$.

For example, here is Gerry Myerson's solution for $$f(7)=15$$. It is interesting to notice that we didn't need to use that the graph is drawn on a cylinder; all the cycles already close up in the plane.

• It amuses me that the solution to a problem about cake involves pictures which look like carbohydrates. I suggest that we call them "carbohydrate diagrams". Commented Aug 9, 2023 at 16:22
• I'm not going to write out the details, but it isn't hard to switch from the cylinder to the plane. Divide the plane $x+y+z=0$ into strips of width $\approx 1$, orthogonal to $(n-1, -2n, n+1)$. Each edge is either between two vertices in the same strip, or vertices in adjacent strips. The cylinder is thus divided into $\approx n$ strips parallel to the axis. Deleting any one strip leaves a graph which embeds in the plane, with roughly the same number of boundary vertices as the original. And, since the original graph has $\approx n$ vertices, there is some strip with $O(1)$ vertices in it. Commented Aug 9, 2023 at 16:56
• I can propose the following discrete proof of a discrete isoperimetric inequality for the regular hexagonal grid. We assume that the grid has three families of pairwise parallel edges, colored into red, green, and blue, respectively. Let $G$ be a subgraph of the grid graph with the vertex set $V$ and $m=|V|\ge 2$. Let $V_-$ be the set of vertex from $V$ with a missing neighbor and $m_-=|V_-|$. Given vertices $v, u\in V$ we say that $v\sim_r u$ if there exists a path from $v$ to $u$ without red edges, the relations $\sim_g$ and $\sim_b$ are defined similarly. Commented Aug 11, 2023 at 4:03
• It is easy to see that each equivalence class of any of the relations contains a vertex with a missing neighbor and at least two such vertices if the class contains at least two elements. This easily implies that there exists a $\sim_r$-equivalence class $C$ of size at least $2m/m_-$. It is easy to check that non-adjacent vertices of $C$ are not $\sim_b$ equivalent, so there are at least $m/m_-$ $\sim_b$ equivalence classes, thus $m/m_-\le m_-$, and so $m_-\ge\sqrt{m}$. Commented Aug 11, 2023 at 4:03
• Now I am trying to adapt this idea to the graph $G$, namely, showing that $C$ has the intersection of size $O(1)$ s with any $\sim_b$-equivalence class, otherwise we should have an impossible cycle of even length in $G$. I expect to write my thoughts soon, if they will work. Commented Aug 13, 2023 at 11:38