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;^[1] a simplified proof was given in 1976 by A. Pinkus.^[2]

The theorem

Given an integer k, define a partition of the interval [0,1] as a sequence of numbers which divide the interval to $k+1$ subintervals:

0=z_{0}<z_{1}<\dotsb <z_{k}<z_{k+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 k continuously integrable functions:

g_{1},\dotsc ,g_{k}\colon [0,1]\longrightarrow {\mathbb {R}}

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

\sum _{i=1}^{k+1}\delta _{i}\!\int _{z_{i-1}}^{z_{i}}g_{j}(z)\,dz=0{\text{ for }}1\leq j\leq k.

(in other words: for each of the k 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^[3] in 1987.

Suppose the interval [0,1] 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. The Hobby-Rice theorem implies that this can be done with k cuts.

References

↑ Hobby, C. R.; Rice, J. R. (1965). "A moment problem in L₁ approximation". Proceedings of the American Mathematical Society. American Mathematical Society. 16 (4): 665–670. doi:10.2307/2033900. JSTOR 2033900.
↑ Pinkus, Allan (1976). "A simple proof of the Hobby-Rice theorem". Proceedings of the American Mathematical Society. American Mathematical Society. 60 (1): 82–84. doi:10.2307/2041117. JSTOR 2041117.
↑ Alon, Noga (1987). "Splitting Necklaces". Advances in Mathematics. 63 (3): 247–253. doi:10.1016/0001-8708(87)90055-7.

This article is issued from Wikipedia - version of the 5/24/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.