Теорема Хобби — Райса

Теорема Хобби — Райса впервые появилась и была доказана в 1965 г. при рассмотрении вопросов оптимальной аппроксимации функций в лабеговом пространстве $L_{1}$. Более простое доказательство теоремы было дано Пинкусом в 1976 году. Также используется в задачах справедливого дележа.

Теорема (адаптированная версия)

Разобьем отрезок [0,1] последовательностью чисел $\{z_{i}\}$ на $k+1$ подынтервалов:

$0=z_{0}<z_{1}<\dotsb <z_{k}<z_{k+1}=1$

Определим знаковое разбиение как разбиение, в котором каждый подынтервал $i$ имеет ассоциированный знак $\delta _{i}$:

$\delta _{1},\dotsc ,\delta _{k+1}\in \left\{+1,-1\right\}$

Теорема Хобби — Райса утверждает, что для любых k непрерывно интегрируемых функций:

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

существует знаковое разбиение отрезка [0,1], такое что:

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

(другими словами, для каждой из k функций её интеграл по положительным подынтервалам равен её интегралу по отрицательным подынтервалам).

Теорема в оригинальной постановке

Пусть существует $n$ действительных функций $\left\{\varphi (x)\right\}_{i=1}^{n}$ в лабеговом пространстве $L_{1}([0,1],\mu )$, где $\mu$ есть конечная безатомная мера на $[0,1]$ . Тогда существуют $\{z_{i}\}_{i=1}^{r}$, $r\leq n$, $0=z_{0}<z_{1}<\ldots <z_{r}<z_{r+1}=1$ такие, что

$\sum _{j=1}^{r+1}(-1)^{j}\int _{z_{j-1}}^{z_{j}}\varphi _{i}(x)d\mu (x)=0\qquad i=1,\ldots ,n$.

Обобщенная теорема Хобби-Райса

Н. Алон в 1987г. при решении задачи о разрезании ожерелья сформулировал и доказал обобщенную теорему Хобби-Райса.

Пусть на единичном отрезке задано $t$ непрерывных вероятностных мер $\mu _{1},\mu _{2},\ldots ,\mu _{t}$. Тогда возможно разрезать единичный интервал в $(k-1)\cdot t$ местах и сформировать из $(k-1)\cdot t+1$ получившихся кусков $k$ семейств $F_{1},F_{2},\ldots ,F_{k}$, таких что $\mu _{i}(\cup F_{j})={1 \over k}$ для всех $1\leq i\leq t,\ 1\leq j\leq k$.

В случае $k=2$ получаем теорему Хобби-Райса.

Использование в задачах о справедливом дележе

Пусть отрезок [0,1] будет тортом. Имеется k участников и каждая из k функций является функцией плотности значений для одного участника. Нам нужно разделить торт на две части так, что все участники соглашаются, что части имеют одинаковые величины. Эта задача справедливого дележа иногда называется задачей согласованного разрезания пополам . Из теоремы Хобби — Райса следует, что это можно сделать с помощью k разрезов.