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!

Continue reading