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;{{cite journal| last=Hobby|first=C. R.|authorlink=John R. Rice (professor)|author2=Rice, J. R.|title=A moment problem in L₁ approximation|journal=Proceedings of the American Mathematical Society|volume=16|pages=665–670| doi=10.2307/2033900| jstor=2033900| issue=4| publisher=American Mathematical Society| year=1965}} a simplified proof was given in 1976 by A. Pinkus.{{cite journal|last=Pinkus|first=Allan|title=A simple proof of the Hobby–Rice theorem|journal=Proceedings of the American Mathematical Society|volume=60|year=1976|pages=82–84|doi=10.2307/2041117|jstor=2041117|issue=1|publisher=American Mathematical Society|doi-access=free}}

The theorem

Define a partition of the interval [0,1] as a division of the interval into $n+1$ subintervals by as an increasing sequence of $n$ numbers:

: $0=z_0 < \underbrace{z_1 < \dotsb < z_n} < z_{n+1} = 1$

Define a signed partition as a partition in which each subinterval $i$ has an associated sign $\delta_i$ :

: $\delta_1,\dotsc,\delta_{k+1}\in\left\{+1,-1\right\}$

The Hobby–Rice theorem says that for every n continuously integrable functions:

: $g_1,\dotsc,g_n\colon[0,1]\longrightarrow\mathbb{R}$

there exists a signed partition of [0,1] such that:

: $\sum_{i=1}^{n+1}\delta_i\!\int_{z_{i-1}}^{z_i} g_j(z)\,dz=0\text{ for }1\leq j\leq n.$

(in other words: for each of the n functions, its integral over the positive subintervals equals its integral over the negative subintervals).

Application to fair division

The theorem was used by Noga Alon in the context of necklace splitting{{cite journal| last=Alon| first=Noga| title=Splitting Necklaces| journal=Advances in Mathematics| year=1987| volume=63| pages=247–253| doi=10.1016/0001-8708(87)90055-7| issue=3| doi-access=free}} in 1987.

Suppose the interval [0,1] is a cake. There are n partners and each of the n functions is a value-density function of one partner. We want to divide the cake into 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.{{cite journal | author = F.W. Simmons and F.E. Su | title = Consensus-halving via theorems of Borsuk-Ulam and Tucker | journal = Mathematical Social Sciences | volume = 45 | pages = 15–25 | year = 2003 | doi = 10.1016/S0165-4896(02)00087-2 | hdl = 10419/94656 | url = http://www.math.hmc.edu/~su/papers.dir/tucker.pdf }} The Hobby–Rice theorem implies that this can be done with n cuts.

References

Category:Theorems in measure theory

Category:Fair division

Category:Combinatorics on words

Category:Theorems in mathematical analysis