Problem of the Week 1089

Divvying the Pre-Sliced Cake

MacPOW Home || Math Forum POWs || Search MacPOW

As pointed out by Jerry Grossman (or rather, by his wife): a greedy algorithm will produce a correct partition for both the finite and infinite cases. Just go through the pieces one at a time in order of non-increasing size. Take them as long as they don't put you over 1/2. It is not hard to show that this greedy procedure will get you exactly 1/2.

For the finite case there is another attractive solution using a recursive algorithm. Consider a slice of the smallest size. If this size is 1/2, we're done. Otherwise there must be at least 2 slices of this smallest size (as the total sum is 1). Consider this pair of smallest slices as one larger slice (whose size is also a negative integer power of 2). Repeating this process, we are guaranteed to have two conglomerate slices of size 1/2.

As for generalizations, Dave Ehren pointed out that if the largest piece has size (1/2)^k, then you can use the greedy procedure to produce a partition into 2^k equal slices. So for large k, you could throw quite a party.

Even more generally, Peter Saltzman points out that there is nothing special about 1/2. If every slice is a negative integer power of 1/n, then we can use our greedy procedure to produce n equal slices.

[Back to Problem 1089]

© Copyright 2008 Stan Wagon. Reproduced with permission.