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

edit

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

 

Define a signed partition as a partition in which each subinterval   has an associated sign  :

 

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

 

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

 

(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

edit

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 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.[4] The Hobby–Rice theorem implies that this can be done with n cuts.

References

edit
  1. ^ Hobby, C. R.; Rice, J. R. (1965). "A moment problem in L1 approximation". Proceedings of the American Mathematical Society. 16 (4). American Mathematical Society: 665–670. doi:10.2307/2033900. JSTOR 2033900.
  2. ^ Pinkus, Allan (1976). "A simple proof of the Hobby–Rice theorem". Proceedings of the American Mathematical Society. 60 (1). American Mathematical Society: 82–84. doi:10.2307/2041117. JSTOR 2041117.
  3. ^ Alon, Noga (1987). "Splitting Necklaces". Advances in Mathematics. 63 (3): 247–253. doi:10.1016/0001-8708(87)90055-7.
  4. ^ F.W. Simmons and F.E. Su (2003). "Consensus-halving via theorems of Borsuk-Ulam and Tucker" (PDF). Mathematical Social Sciences. 45: 15–25. doi:10.1016/S0165-4896(02)00087-2. hdl:10419/94656.