30
$\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$
  • 6
    $\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$ – Taras Banakh May 4 at 6:30
  • 2
    $\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$ – Taras Banakh May 4 at 7:49
  • 4
    $\begingroup$ Related: Minimal possible cardinality of a $(a_1, ..., a_k)$-distributable multiset $\endgroup$ – YuiTo Cheng May 4 at 7:52
  • 3
    $\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$ – Fedor Petrov May 4 at 11:11
  • 2
    $\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$ – Simon Willerton May 7 at 20:47
14
$\begingroup$

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

Cut щге 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$
  • 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$ – Taras Banakh May 4 at 22:04
  • $\begingroup$ I think he is cutting pieces again, into subpieces, so the sizes are smaller $\endgroup$ – kodlu May 4 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$ – Ilya Bogdanov May 5 at 4:38
  • $\begingroup$ @IlyaBogdanov Thank you for the explanations. Now I have understood. Very cute! $\endgroup$ – Taras Banakh May 5 at 8:12
8
$\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)\le 14<15=u(6)$,

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

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

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

$\endgroup$
6
$\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$
  • 1
    $\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$ – Taras Banakh May 6 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$ – Taras Banakh May 6 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$ – Gerry Myerson May 6 at 6:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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