41
$\begingroup$

You probably know the following problem:

We have two circular cakes of the same height but unknown and potentially different radii, and we want to cut them into two equal shares. Each cut can only cut one piece of one cake. What is the minimal number of cuts required?

The solution is easily found:

It's $1$ cut. Stack the two cakes and center them, then cut the big one around the small one : enter image description here Here you go.

While I was thinking about this easy problem, the following question logically arose:

We have $n\in\mathbb{N}^*$ circular cakes of unknown and potentially different radii (hmm yummy) but the same height, and we want to cut them into $p\gt n$ equal shares. Each cut can only go through one piece of cake. What is the minimal number $c$ of cuts required? How do you cut the cakes?

The cuts can be done however you want (i.e. lines, curves, etc) and stacking cakes etc is allowed. You are of course not allowed to measure the exact radius. To make it simple, let's say you have a straightedge (unlabelled ruler), an arbitary-precision protractor and a compass.


Any help/thoughts are appreciated.

$\endgroup$
19
  • 1
    $\begingroup$ Initial results: The largest cake must always be cut into $p$ pieces, so $p-1$ is a lower bound. Otherwise, there don't seem to be any answers as elegant as the $p = 2, n = 2$ case. I've made a few drawings. $\endgroup$
    – Paul Z
    Jun 26, 2014 at 19:26
  • 5
    $\begingroup$ @johannesvalks: OP said that each cut could only cut one cake. $\endgroup$ Jun 26, 2014 at 20:10
  • 1
    $\begingroup$ What sorts of cake-cutting tools and techniques are allowed? I wouldn't have realized that we could properly align the centers of the cakes, or that we could properly return to the original line of a cut after taking a detour around another cake, and it may not be clear to everyone that putting a cake on top of another cake results in two neatly stacked cakes instead of an awful mess. Do we have rulers? Compass and straightedge? Can we measure or duplicate angles in some fashion? $\endgroup$ Jun 26, 2014 at 20:30
  • 1
    $\begingroup$ It wouldn't have cut more than one piece of cake at once, taking the natural meaning of simultaneously. I've edited to remove that adverb and make other clarifications. There's one remaining ambiguity, which I didn't want to resolve because I didn't know in which direction to resolve it: "the cuts may be done however you want" seems to directly contradict "to make it simple, let's say you have a straightedge and a compass". $\endgroup$ Jun 27, 2014 at 14:14
  • 2
    $\begingroup$ @PaulZ That’s not true: a straightedge and compass are sufficient to divide a circle into 7 pieces of equal area as long as you don’t try to do it with angular wedges. $\endgroup$ Jan 11, 2020 at 7:49

1 Answer 1

0
$\begingroup$

Proof that you need at most $p - 1$ cut:

It is known that using compass and straightedge, with a segment of length $a$ and $b$, $a \geq b$, one can construct $c = \sqrt{a^2+b^2}$ and $d = \sqrt{a^2-b^2}$. It is also possible to divide a segment into an arbitrary number of equal parts. Addiontially, the center of a circle can be determined. This is sufficient for us to construct the fair cuts.

Let $r_1,r_2,...,rn$ be the radii of the circles. Let $r^{*}$ be the radius of the circle whose area is equal to the area of a share, then $$r_* = \frac{1}{p}\sqrt{r_1^2+r_2^2+...+r_n^2}$$ which is clearly constructible. Now let's put the $n$ circles into the first $n$ shares, as the same time we also draw $p$ segments to keep the areas of the shares of length $x_1,x_2,...,x_p$ in check (for convinience we call them the shares' radii). Initially, $x_i = r_i$ for $i \leq n$ and $x_i = 0$ for $i > n$. We proceed to repeat the following steps

Find a largest share with radius $x_\max$ and a smallest share with radius $x_\min$. If $x_\max > r'$, proceed to cut and remove an annulus piece of area $S_{cut} = \pi x_\max^2 - \pi r_*^2 = \pi r_{cut}^2$ then move it to the smallest share and update their radii accordingly. Otherwise, halt. For an annulus with radii $a,b$, $a < b$, to cut a piece of area $S_{cut}$, we have

$$r'_{cut} = \sqrt{r_{cut}^2 + a^2}$$

After each operation, the number of share that has the radius equal to $r_*$ increases by at least $1$. Since there're only a finite number of shares, eventally the process halts. The possible scenarios are

  • One cannot find a piece large enough. That's impossible because the largest piece of a share is either the initial cake, or a piece that it receive from a previous step. However, in that case, the surplus area received is $S_{sur} = S_{cut} + S_\min - S_* < S_{cut}$ therefore the surplus that's needed to be cut off cannot be larger than the largest part (in terms of area).

  • $x_{\max} = r_*$. This only happens when all the shares are equal

Thus our process of cutting the cakes give the equal shares as desired. Since at each step at least $1$ equal share is produced, and only $p-1$ equal shares is needed, since the leftover is obviously also equal, only at most $p-1$ cuts are needed.

P/s: I do not know how to prove if you need at least $p-1$ cut for almost all sets of cakes. Someone who is well versed in number theory may be able to prove that.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .