CUTTING HIGH DIMENSIONAL CAKES

Wolfgang Kühn and Zuzana Kühn

Consider the problem of partitioning a cake such that each piece has a certain measure. Typically, an algorithm solving such a problem (for example, the algorithm of Banach and Knaster for fair division in [2]) uses hyperplanes to cut the cake. Continuity arguments require that these hyperplanes do not carry positive measure.

In [1], Jones proves (Corollary 1) that, for dimension m = 3, the direction set of all hyperplanes of positive measure has Lebesgue measure zero on the unit sphere. However, the result holds in any dimension. Because Jones’ proof cannot be extended to m > 3, we communicate an elegant proof which is even shorter than the one given in [1].

Let μ be a finite measure defined on (Ω ⊆ R^{m}, B), where B is the Borel σalgebra in R^{m}. Recall that a k-flat is a k-dimensional affine subspace of R^{m}. For 0 ≤ k ≤ m, let Λ_{k} be the set of all k-flats of μ-positive measure which do not itself contain any sub-flat of μ-positive measure. Let S^{m−1} be the unit sphere in R^{m}.

Theorem. Let μ be a finite atomless measure on (Ω, B) and define the direction set

V = {y ∈ S^{m−1} : y is perpendicular to some hyperplane with μ-positive measure}.

If η is Lebesgue measure on S^{m−1}, then η(V) = 0.

Proof. If h is a k-flat, let h^{⊥} denote the subspace of dimension (m − k) orthogonal to h. Because each y ∈ V belongs to h^{⊥} ∩ S^{m−1} for some 0 ≤ k < m and some h ∈ Λ_{k},

η(V) ≤ η ( ⋃_{k=0}^{m−1} ⋃_{h∈Λ_{k}} h^{⊥} ∩ S^{m−1}) ≤ ∑_{k=0}^{m−1} ∑_{h∈Λ_{k}} η(h^{⊥} ∩ S^{m−1}),

where we used sub-additivity and the fact that the sets Λ_{k} are countable by the theorem in [1]. For each 0 ≤ k < m and h ∈ Λ_{k}, the set h^{⊥} ∩ S^{m−1} is a (m − 1 − k)- dimensional sub-manifold of S^{m−1}, and therefore has η-measure zero for k > 0. For k = 0, observe that μ is atomless, which implies that Λ_{0} is empty. We conclude that all terms in the sum above are either zero or void, proving the assertion. □

References

1. M.L. Jones, A note on a cake cutting algorithm of Banach and Knaster, Amer. Math. Monthly 104 (1997), no. 4, 353-355.

2. H. Steinhaus, Sur la division progmatique, Econometrika (Supplement) 17 (1949), 315-319.

Typeset by AMS-TEX