Английская Википедия:Hobby–Rice theorem
Шаблон:Short description 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
Define a partition of the interval [0,1] as a division of the interval into <math>n+1</math> subintervals by as an increasing sequence of <math>n</math> numbers:
- <math>0=z_0 < \underbrace{z_1 < \dotsb < z_n} < z_{n+1} = 1</math>
Define a signed partition as a partition in which each subinterval <math>i</math> has an associated sign <math>\delta_i</math>:
- <math>\delta_1,\dotsc,\delta_{k+1}\in\left\{+1,-1\right\}</math>
The Hobby–Rice theorem says that for every n continuously integrable functions:
- <math>g_1,\dotsc,g_n\colon[0,1]\longrightarrow\mathbb{R}</math>
there exists a signed partition of [0,1] such that:
- <math>\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.</math>
(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[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