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!
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:
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.
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.
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$.
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$
$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.
