Problem of the Week 1089

Divvying the Pre-Sliced Cake

MacPoW Home ||  Forum PoWs ||  Teachers' Place ||  Student Center ||  Search MacPoW

Bob and Alice are given a rectangular sheet cake with volume equal to 1.

The cake is pre-sliced. Different slices may have different volumes, but the volume of each slice is some negative power of 2.

Prove that there is a way to divvy up the slices so that Bob and Alice both get exactly 1/2 of the cake.

(The number of slices may be finite or infinite.)

Source: Based on a lemma in Joel Spencer's paper, "Randomization, Derandomization and Antirandomization: Three Games."

© Copyright 2008 Andrew Beveridge and Stan Wagon. Reproduced with permission.