# Drawing Blanks

Premature Optimization is a Prerequisite for Success

## Pie Cutting problem

with one comment

You are expecting guests and you know their number is going to be either n or m. You want to cut a pie so that the pieces can be equally divided among guests in either case. What is the minimal number of pieces?

Note that the pieces don’t have to be equal. E.g. for n=2, m=3 you don’t have to cut the pie into 6 pieces. You can cut into 4: 1/3, 1/3, 1/6, 1/6.

For n=4, m=7 you can cut into 16 pieces: 4 * 1/7 + 12 * 1/28. But you can do better and use only 10 pieces: 4*1/7 + 2*1/14 + 2*1/28 + 2*3/28

There is a very simple and straightforward algorithm that results in a small number of pieces. But it wasn’t easy for me to prove that there is no better algorithm. It took me almost a week to find a proof, but I’m happy because it’s very beautiful.

In this post I’m only going to give the answer and an algorithm. I will publish the proof of optimality later.

ok, it’s really simple. You first cut into n equal pieces. And then cut it into m equal pieces. There will be exactly GCD(n,m)-1 coincident cuts. So the total number of pieces will be m+n-GCD(m,n)

It’s intuitively obvious that there can’t be fewer pieces, but how do we prove that?

BTW, a friend of mine had suggested this analogy: http://en.wikipedia.org/wiki/Vernier_scale but it wasn’t relevant to my proof.