The mincing problem

How many cuts it take to mince a clove of garlic into one million pieces?

A professional chef notes that the usual method will do: First, she slices the garlic one-thousand times along its length and one-thousand times across its width.  This gives

\[ 1000\times 1000 = 1\,000\,000\]

tiny little garlic pieces with only two-thousand cuts. (Our characters remain intentionally two-dimensional—a three-dimensional chef would rotate the garlic to slice along its height, mincing the garlic into one-million pieces with only three-hundred cuts of her knife.)

A naïve chef claims a better way. “First,” he says, “I slice the garlic in two. Then, I cut each of those pieces in half with a single slice.” He continues along, carefully rearranging the garlic so that each run of his blade divides every piece in two again.

“See?” he points. “Each of my slices doubles the number of garlic bits.”

“Two! Four! Eight!” he shouts. “With only twenty slices, I’ll mince it to a million minuscule morsels.”

Then there’s us: sloppy, lazy cooks. Unlike the professional chef, we can’t reliably cut a clove of garlic into one-hundred thin slices without risking our fingers. And, we note wryly, it’s only a matter of time before the cocksure chef discovers a problem with his approach: the final cut requires half a million fragments of garlic arranged into a perfect line!

Instead of risking our fingers or sanity, we’re going to use a technique known to professionals and amateurs alike: we will chop the garlic at random, over and over, until we generate one million pieces. How many chops does our simple approach require?

The answer: Our rustic chop will mince almost as quickly as the professional’s honed technique. Put mathematically, the number of cells in our random chop also grows quadratically with the number of slices we make. With \(n\) slices, our technique produces \(n + n(n-1)/ 4\pi\) bits of garlic when the garlic is a circle. Taking \(n=3540\) yields, on average, just over one million pieces of garlic. Neat!

Mathematical model

Let’s assume that our garlic \(G\subset \mathbb{R}^2\) is convex with perimeter \(P\) and area \(A\). We will model our random chopping process as random chords across our garlic, and then counting the number of pieces that this random process creates. These models are known in the mathematical literature as “hyperplane tessellations,” and they have a rich theory associated with them.

Before we resolve the thorny question of “what do you mean by random chord“, let’s take a foray into the basic geometric problem. Suppose we draw the \(n-1\) lines across our garlic.  When the \(n\)th line is drawn across the garlic, it will create one new cell for every cell that it crosses on its way across the garlic. This observation forms the core of the analysis below.

Random Chords

What, precisely do we mean by “random line” or “random chord”? This question lies at the heart of Bertrand’s Paradox, where several seemingly reasonable interpretations of “random chord” result in very different distributions of lines. The most common resolution of this paradox involves invariance: Generates lines so that the location and orientation of the garlic doesn’t matter—the distribution of the resulting intersections are precisely the same.

Invariant line processes are well-studied in the academic literature. From here on out, we will assume that all of our random lines are drawn from this unique probability measure. The measure has some very nice properties. In particular, the probability that a random line that intersects our garlic also intersects a convex subset of the garlic—denoted by \(K\)—is invariant to the location of the subset. To be precise, we have the following fact.

Fact 1. Let \(K’ \subset K\) be convex. Then the probability that a random line that intersects \(K\) also intersects \(K’\) is equal to \(p(K’) / p(K)\), where \(p(\cdot)\) denotes the perimeter of the set.

Analyzing the Model

With this, we can get in to some computations. Let \(M(i)\) denote the random variable that counts the number of cells of garlic after the \(i\)th chop, \(N(i) := M(i) – M(i-1)\) be the number of new cells of garlic added by the \(i\)th chop, and \(L_i\) be the line generated by the \(i\)th chop. Then using linearity of expectation and the conditioning property, we find

\[\mathbb{E}[M(n)]  = 1 + \sum_{i=1}^n \mathbb{E} [ N(i) ] =  1 + \sum_{i=1}^n \mathbb{E}[\mathbb{E}[ N(i) \mid L_1, \dotsc, L_{i-2}, L_{i-1}]].\]

Each fixed arrangement of lines \(L_1, \dotsc, L_{i-2}, L_{i-1}\) generates a cell complex \(\{C_1, \dotsc, C_{R-1}, C_R\}\), where the number \(R\) is a function of the lines. With this notation, the inner expectation takes the form

\[\mathbb{E}[N(i)  \mid L_1, \dotsc, L_{n-2}, L_{n-1}] = \sum_{j=1}^R \mathbb{P}\{L_n \text{ intersects } C_j \}= \frac{1}{p(K)} \sum_{j=1}^R p(C_j), \]

where the second equality is Fact 1. The right-hand side is the total perimeter of all cells inside of the garlic. This is equal to the perimeter of the garlic plus twice the length \(\ell\) of every line in the garlic:

\[\frac{1}{p(K)} \sum_{j=1}^R p(C_j) = 1 + \frac{2}{p(K)} \sum_{k=1}^{i-1} \ell(L_k).\]

Combining the three equations above and using the fact that the lines are identically distributed, we find that

\[\mathbb{E}[M(n)] = n + \frac{2}{p(K)}\sum_{i=1}^n  \sum_{k=1}^{i-1}\mathbb{E}[\ell(L_i)] = n + \frac{\mathbb{E}[\ell(L_1)]}{p(K)} n(n-1). \]

Thus, the average number of lines grows quadratically, and the only thing that remains to compute is the average length of the chord \(\ell(L_1)\). This is given by [SW, Theorem 8.4.1]:

\[\mathbb{E}[\ell(L_1)] = \frac{v(K)}{p(K)},\]

where \(v(K)\) is the volume of the garlic \(K\). Putting this all together, we find

\[\mathbb{E}[M(n)] = n + n (n-1) \frac{v(K)}{p^2(K)}.\]

The ration \(v(K)/p^2(K)\) is maximized when \(K\) is a circle, where \(v(K)/p^2(K) = 1 / 4\pi\). In this case

\[\mathbb{E}[M(n)] = n + \frac{n(n-1)}{4\pi}.\]

2 thoughts on “The mincing problem

Leave a Reply

Your email address will not be published. Required fields are marked *