Problem of the Week 1089
Divvying the Pre-Sliced Cake
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
(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.