Hobby–Rice theorem


In mathematics, and in particular the necklace splitting problem, the Hobby–Rice theorem is a result that is useful in establishing the existence of certain solutions. It was proved in 1965 by Charles R. Hobby and John R. Rice; a simplified proof was given in 1976 by A. Pinkus.

The theorem

Given an integer k, define a partition of the interval as a sequence of numbers which divide the interval to subintervals:
Define a signed partition as a partition in which each subinterval has an associated sign :
The Hobby-Rice theorem says that for every k continuously integrable functions:
there exists a signed partition of such that:
.

Application to fair division

The theorem was used by Noga Alon in the context of necklace splitting in 1987.
Suppose the interval is a cake. There are k partners and each of the k functions is a value-density function of one partner. We want to divide the cake to two parts such that all partners agree that the parts have the same value. This fair-division challenge is sometimes referred to as the consensus-halving problem. The Hobby-Rice theorem implies that this can be done with k cuts.