Drawing Blanks

Premature Optimization is a Prerequisite for Success

Pie cutting problem: the proof

leave 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 so that the pieces can be equally distributed among the guests in either case. What is the minimal number of pieces?

And let me remind you that the pieces don’t have to be equal. For m=2, n= 3 we don‘t need to cut into 6 equal pieces. It is sufficient to cut into 4:

pie2x3

In the picture I cut a line segment instead of a pie. And I used a very straightforward algorithm: first I cut into 2 equal pieces (the blue cut), and then into 3 (the red cuts). Obviuosly, if m and n are relatively prime, this method will result in m+n-1 pieces. And if they are not, some cuts will coincide. Here is the cutting for m=6, n=9:

pie6x9

The two magenta cuts are those that coincided. In the general case, the number of coincident cuts will be equal to the greatest common divisor of m and n minus 1. I’m not going to prove this, this is trivial.

So our simple and straightforward cutting method will always yield m+n-GCD(m,n) pieces. I claim that this number is the minimum, i.e. the conditions of the problem cannot be satisfied with a smaller number of pieces.

Proof.

First, one simple fact about graphs:

In any connected graph, the number of edges is not less than the number vertices minus 1. (In a tree it equals to the the number vertices minus 1).

In any graph, the number of edges is not less than the number of vertices minus the number of connected components.

What do graphs have to do with this problem? I’m going to use graphs to represent the distribution of the pieces of the pie among the guests. The n guests will be represented by n blue dots, the m guests – by m red dots. The lines will represent the pieces. A line originating from a dot represents the fact that this particular guest gets this particular piece. Each line will connect a red dot to a blue dot showing which guest gets this piece in the case when the blue guests show up and in the case when the red guests show up.

Confused? Yeah, this is some heavy abstraction. Here is the picture for m=2, n=3 and the cutting into 6 equal pieces:

graph2x3x6

See, each red guy gets 2 pieces, each blue guy gets 3. And for the cutting {1/3, 1/6, 1/6, 1/3} the distribution will be:

graph2x3x4

And if m=2, n=4, and we cut into 4 equal pieces, the graph will have 2 connected components:

graph2x4x4

Now we have all clues that we need in order to conduct the proof

Consider any graph that satisfies the condition of the problem. I.e. we managed to cut the pie (no matter into how many pieces) and distribute the pieces equally among the n and m guests, and our graph represents this distribution.

Consider any connected component of this graph. Let it contain n’ red dots and m’ blue dots. Then the total amount of the pie represented by its edges will be equal to n’/n (since each red guest gets 1/n) and at the same time m’/m (since each blue guest gets 1/m).

So n’/n = m’/m

If m and n are relatively prime this equality can only hold if n’=n and m’=m, so this connected component is really the whole graph. In this case the number of edges is no less than the number of vertices minus one, that  is m+n-1.

Let the greatest common divisor of m and n be GCD(m,n)=d.

Then n’ must be divisible by n/d (and m’ must be divisible by m/d).

So n’ cannot be less than n/d. Thus n’/n cannot be less than 1/d. But n’/n is the amount of the pie contained in one connected component of the graph. Which means, any connected component contains at least 1/d of the pie. So the number of connected components cannot exceed d. And the number of edges of the graph cannot be less than m+n-d. QED.

I’d be curious to see generalization of this problem for any number of expected guest counts. This problem may have applications in computing (queuing theory), if we view the CPU as the pie, and pieces as threads. Then cutting the pie could represent optimization of the number of server processes and sizes of thread pools based on projected usage patterns.

About these ads

Written by bbzippo

03/12/2010 at 6:12 am

Posted in math

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: