# 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. May 4 '19 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}$. May 4 '19 at 7:49
• May 4 '19 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. May 4 '19 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". May 7 '19 at 20:47

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. May 4 '19 at 22:04
• I think he is cutting pieces again, into subpieces, so the sizes are smaller May 4 '19 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. May 5 '19 at 4:38
• @IlyaBogdanov Thank you for the explanations. Now I have understood. Very cute! May 5 '19 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 May 6 '19 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$. May 6 '19 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. May 6 '19 at 6:49
• @TarasBanakh: In fact, $f(6)=13$ - see my answer below. Sep 22 '20 at 16: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.