29
$\begingroup$

Perhaps a math degree and cooking don't go hand in hand, but hopefully they do.

I have been thinking about this problem for some time when in the kitchen without making any real progress: How does one cut onions in a mathematically efficient way?

For simplicity, let's assume that an onion is perfectly spherical with radius $r$, consisting of $n$ layers of thickness $d = \frac{r}{n}$. Each cut consists of a plane $p_i$ orthogonal to the $xy$-plane (the cutting board) intersecting some (or all) parts of the onion, arranged in some way, dividing them.

The goal is to, with a sequence of cuts $\{p_i\}_{i=1}^{N}$, get the onion to consist of a set of pieces (most likely irregular in shape) so that they all have diameter at most $M$. By diameter of a piece, we mean the longest possible distance between two points on the piece.

How should the cuts $p_1, p_2, p_3, \dots, p_N$ of the onion be made so that this criterion is fulfilled (all the pieces are small enough) and $N$ is as small as possible?

In other words, we don't consider time to be an issue, just the smallest number of cuts. You may rearrange the pieces in any which way between cuts as long as you specify which part goes where.

I think it's fair to assume $d < M$, because otherwise the pieces need to be very small and one would just use a blender. Of course, the model isn't perfect, since we have an infinitely long knife on an infinitely large cutting board, but since I never seem to run out of room on it, I think that's OK.


Yes, this question is just as "serious" as it sounds, but I would very much appreciate your thoughts on this. I welcome everything from ideas on how to approach the problem and sketches of an optimal strategy (I'm a Master student in computational science) to a full-blown perfect algorithm.

This could become a great conversation starter.

$\endgroup$
5
  • 15
    $\begingroup$ Mathematically, the most efficient way to cut onions is to get someone else to do it. You're welcome. $\endgroup$
    – Timbuc
    Jun 10 '14 at 17:03
  • $\begingroup$ Could you clarify "of which none has a side longer than $M$" please? What exactly do you mean by "side"? $\endgroup$
    – MGA
    Jun 10 '14 at 18:16
  • 2
    $\begingroup$ It might be more sound to say "of which none has diameter more than $M$". $\endgroup$
    – user21467
    Jun 10 '14 at 18:19
  • 1
    $\begingroup$ This looks at least as hard as the Kepler conjecture, which took almost 400 years to prove. $\endgroup$
    – TonyK
    Jun 10 '14 at 18:27
  • $\begingroup$ Thank you @StevenTaschuk that sounds better. I've edited. $\endgroup$
    – naslundx
    Jun 10 '14 at 19:11
2
+50
$\begingroup$

If we can rearrange the pieces any which way between cuts, as the question states, then we might as well arrange them in a line before each cut, so that the cut intersects every piece of the onion. By choosing each piece's translation perpendicular to the cut, we can guarantee that it is divided into two pieces of equal area. By choosing the piece's orientation, we can also ensure that none of the pieces get too long and skinny, so the diameter of a piece of area $a$ is bounded above by $c\sqrt a$, where $c$ is a universal constant.

Then it is sufficient to get the area of each piece below $M^2/c^2$. The original area of the largest piece is $4\pi r^2$, and each cut reduces it by half, so we can succeed in $\log_2(r^2/M^2)$ cuts plus a constant.

The converse argument shows that $\log_2(r^2/M^2)$ cuts plus a constant are indeed necessary.

$\endgroup$
0
1
$\begingroup$

With parallel cuts along planes spaced by 1/2cm in each of the three spatial dimensions. First, cut the peeled onion down the middle. Second, put one half on a flat surface and, from the (top) end opposite the root, make several cuts parallel to the surface most of the way into the onion (leaving a bit near the root to hold it together). Third, from the top make several parallel vertical cuts perpendicular to the previous cuts. Fourth, from the 'top' finish dicing the onion by making several parallel vertical cuts perpendicular to the previous two sets of cuts. Fifth, do the same with the other half.

$\endgroup$
5
  • 1
    $\begingroup$ Is this just a "random" suggestion, or do you know anything about how good it is in terms of efficiency? $\endgroup$
    – naslundx
    Jun 21 '14 at 18:48
  • 2
    $\begingroup$ I was taught this method by a Transylvanian German woman many years ago - it works. $\endgroup$
    – user117644
    Jun 21 '14 at 19:54
  • 3
    $\begingroup$ This is the standard way to cut an onion taught to cooks. There is very little chance that it answers the question... $\endgroup$ Jul 3 '14 at 8:28
  • $\begingroup$ I disagree, you are making parallel cuts in all three planes while holding it together. Or does 'mathematically efficient' mean something different to 'efficient'? $\endgroup$
    – user117644
    Jul 5 '14 at 7:05
  • $\begingroup$ @mistermarko: "Efficiency" is always relative to an effort metric. In this case, "number of cuts" is the metric. It's not the best "real world" metric, which would probably include things like "have to handle very few individual pieces", "does not require much time", "does not require cutting in a manner suggestive of the Banach-Tarski paradox", et al... $\endgroup$ Jul 10 '14 at 1:54
0
$\begingroup$

Suppositions

  • Onion is a sphere with radius $r$, where $r > 0$
  • Onion has $n$ layers, where $n > 0$
  • Each layer is of thickness $h = \frac{r}{n}$
  • Each cut consists of a plane $p_i$ orthogonal to the $xy$-plane
  • When a cut happens the pieces of onion are still and arranged in any fashion.

Solution Must

  • Leave each piece with diameter less than M, where M > h
  • Do it in the least number of cuts

Note, I'm using the variable h instead of d because d is often used to denote diameter and it was confusing me.

Lets also assume the following

  • In every layer, including the core, a cut is necessary in order to reduce the diameter to less than M. Or else we just leave that layer alone and we continue applying the algorithm.

  • I will never peel/move a layer from another layer before cutting. In example, if I cut the onion in half I wont pop-out the inner onions or rotate them around or anything. This is just to keep it simple.

Basically, we want to be able to fit each piece of onion inside a sphere of radius M. You know what fits inside of a sphere of radius M? A cube whose longest diagonal, c, satisfies the following condition $M \geq c\sqrt{3}$

In order to reduce the diameter < $M$ of all the pieces we need to reduce all dimensions of the onion (x,y,z). A single cut wont reduce the diameter of all the pieces of onion.

If we were to cut an onion in half, each half still has the same diameter, as defined. If we cut again both half's into quarters then we still have not reduced the diameter as each quarter still has a diameter equal to the original diameter. Now if we do a third cut of each wedge in half then we reduced diameter to $\sqrt{(2*\frac{r}{2})^2}$ for the outermost layer. (And even better for inner layers)

Now, imagine setting the $\frac{1}{8}$ onion on its point and looking at it straight down. Now do 3 cuts that are $\frac{2\pi}{3}$ radians apart into three pieces, similar to how a Mercedes emblem is shaped. Then you will have reduced the diameter of each quarter again (symmetrically) by some factor that I don't want to calculate at the moment. If the diameter is greater than $M$ then you can repeat by setting each remaining wedge on its point and cutting it in the same manner.

The math gets a little messy at this point, but by repeatedly doing this process then you can consistently reduce the diameter with three cuts until the diameter is smaller than $M$.

Point being that, (I believe) in order to reduce the diameter in the way its defined in this problem you will need three cuts, one for each dimension. The algorithm described will always reduce the diameter every three cuts and result in symmetric pieces.

*Note: Every time you're doing these three cuts, you can stack the wedges on top of each other to cut them all at the same time.

$\endgroup$
2
  • $\begingroup$ What you've written seems correct, although I don't quite fully understand the "never peel/move a layer..."-part. I will await your full answer. $\endgroup$
    – naslundx
    Jul 8 '14 at 17:16
  • $\begingroup$ I sloppily finished what I was getting at by doing a lot of handwaving. Apologies for the delay! $\endgroup$ Jul 26 '14 at 10:07

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.