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.

About these ads

Written by bbzippo

03/04/2010 at 3:18 am

Posted in math

One Response

Subscribe to comments with RSS.

  1. [...] 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 [...]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: