# Drawing Blanks

Premature Optimization is a Prerequisite for Success

## Pie cutting problem: the proof

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:

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:

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:

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:

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

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.

Written by bbzippo

03/12/2010 at 6:12 am

Posted in math