50
$\begingroup$

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

enter image description here

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!

$\endgroup$
26
  • 14
    $\begingroup$ 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. $\endgroup$ May 4, 2019 at 6:30
  • 10
    $\begingroup$ $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}$. $\endgroup$ May 4, 2019 at 7:49
  • 6
    $\begingroup$ Related: Minimal possible cardinality of a $(a_1, ..., a_k)$-distributable multiset $\endgroup$ May 4, 2019 at 7:52
  • 6
    $\begingroup$ 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. $\endgroup$ May 4, 2019 at 11:11
  • 17
    $\begingroup$ 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". $\endgroup$ May 7, 2019 at 20:47

7 Answers 7

30
$\begingroup$

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.

$\endgroup$
5
  • 3
    $\begingroup$ 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$.) $\endgroup$ Aug 10, 2023 at 11:15
  • 2
    $\begingroup$ 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$. $\endgroup$ Aug 10, 2023 at 12:37
  • 3
    $\begingroup$ 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.) $\endgroup$ Aug 10, 2023 at 13:34
  • 3
    $\begingroup$ 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. $\endgroup$ Aug 10, 2023 at 15:37
  • $\begingroup$ 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? $\endgroup$ Aug 12, 2023 at 9:24
24
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ May 4, 2019 at 22:04
  • $\begingroup$ I think he is cutting pieces again, into subpieces, so the sizes are smaller $\endgroup$
    – kodlu
    May 4, 2019 at 22:35
  • $\begingroup$ @TarasBanakh: In the first part, I cut the same piece into those segments twice. Now I tried to make it clear in the text. $\endgroup$ May 5, 2019 at 4:38
  • $\begingroup$ @IlyaBogdanov Thank you for the explanations. Now I have understood. Very cute! $\endgroup$ May 5, 2019 at 8:12
18
$\begingroup$

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.

$\endgroup$
1
11
$\begingroup$

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

$\endgroup$
4
  • 3
    $\begingroup$ 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 $\endgroup$ May 6, 2019 at 5:48
  • $\begingroup$ 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$. $\endgroup$ May 6, 2019 at 5:50
  • $\begingroup$ @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. $\endgroup$ May 6, 2019 at 6:49
  • 1
    $\begingroup$ @TarasBanakh: In fact, $f(6)=13$ - see my answer below. $\endgroup$ Sep 22, 2020 at 16:03
9
$\begingroup$

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$

$\endgroup$
3
  • 1
    $\begingroup$ 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$? $\endgroup$ Sep 2, 2023 at 8:04
  • $\begingroup$ @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$. $\endgroup$ Sep 2, 2023 at 10:03
  • $\begingroup$ 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. $\endgroup$ Sep 2, 2023 at 10:03
7
$\begingroup$

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

$\endgroup$
5
$\begingroup$

$\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.

enter image description here

$\endgroup$
6
  • 3
    $\begingroup$ 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". $\endgroup$ Aug 9, 2023 at 16:22
  • $\begingroup$ 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. $\endgroup$ Aug 9, 2023 at 16:56
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 11, 2023 at 4:03
  • 1
    $\begingroup$ 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}$. $\endgroup$ Aug 11, 2023 at 4:03
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 13, 2023 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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