## Pie Cutting problem

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.

[…] a comment » Let me first restate the problem: You are expecting guests and you know their number is going to be either n or m. You want to cut a […]

Pie cutting problem: the proof « Drawing Blanks03/12/2010 at 6:12 am