Задача дележа земли Хилла — Бека

Если территория D односвязна, используется следующий алгоритм:

1. Находим отображение Римана h, которое отображает D в единичный круг, так что для всех стран значение любой окружности с центром в начале координат равно 0 и значение любого радиуса из начала координат равно 0 (существование такого отображения h доказывается доводами подсчёта).
2. Просим каждую страну нарисовать на единичном круге отображения h(D) диск с центром в начале координат (центр диска h(D)) и значением ${\displaystyle {\tfrac {1}{n}}}$. Это возможно сделать благодаря тому, что все окружности с центрами в начале координат имеют значение 0.
3. Находим диск D₁ с наименьшим радиусом r₁.

Есть два случая.

4. Если D₁ нарисован только одной страной, скажем C_i, то отдаём диск стране C_i. Его значение для других стран строго меньше ${\displaystyle {\tfrac {1}{n}}}$, так что мы можем отдать стране C_i небольшой дополнительный кусок, прилегающий к распределённому диску.

Чтобы это сделать нарисуем сектор, соединяющий D₁ с границей круга D. Пусть каждая страна (отличная от C_i) отрезает от этого сектора так, что значение объединения диска и сектора вместе не превосходят ${\displaystyle {\tfrac {1}{n}}}$. Это возможно благодаря условию, что значения всех радиусов из начала координат равны 0. Отдадим стране C_i объединение D₁ и усечённого сектора.

Оставшаяся территория односвязна и имеет значение по меньшей мере ${\displaystyle {\tfrac {n-1}{n}}}$ для оставшихся ${\displaystyle n-1}$ стран, так что делёж можно продолжить рекурсивно с шага 1.

Если часть D₁ была запрошена k>1 странами, то требуются некоторые более изощрённые аукционы, чтобы найти страну, которой мы можем отдать диск и связывающий сектор.

5. Выберем произвольную страну-победителя и назовём её объявителем, C₁. Пусть она добавит сектор, соединяющий D₁ с её текущей территорией и позволим другим странам отрезать от этого сектора, так что:

• Для любой проигравшей страны значение D₁ плюс отрезанный сектор не превосходят по значимости ${\displaystyle {\tfrac {1}{n}}}$ (это возможно, поскольку значение D₁ для них меньше ${\displaystyle {\tfrac {1}{n}}}$).
• Для любой выигравшей страны значение усечённого сектора меньше ${\displaystyle {\tfrac {1}{n}}}$.

6. Пусть каждая из победивших стран предложит новый радиус r (меньший, чем их начальное предложение), так что значение отрезанной части сектора плюс диск радиуса r оценивается ровно в ${\displaystyle {\tfrac {1}{n}}}$. Выберем наименьший такой диск D₂. Снова имеются два случая:

Если C₁ является одной из стран, подавшей заявку на D₂, то просто отдаём ей область D₂ (которая слегка меньше первоначальной заявки D₁) и соединяющий сектор. C₁ соглашается, что значение равно ${\displaystyle {\tfrac {1}{n}}}$, а другие страны согласны, что значение не превосходит ${\displaystyle {\tfrac {1}{n}}}$, так что мы можем продолжить рекурсивно с шага 1.

В противном случае C₁ соглашается, что полное значение D₂ и соединяющего сектора меньше, чем ${\displaystyle {\tfrac {1}{n}}}$. Все проигравшие должны также согласиться с этим, поскольку D₂ меньше, чем D₁. Таким образом, C₁ и все другие страны, которые согласны с этим, удаляются из множества победителей.

7. Среди оставшихся победителей выберем нового заявителя C₂. Пусть он добавит другой сектор, соединяющий D₂ с текущей территорией, и позволим другим странам усечь этот сектор как на шаге 5.

Заметим, что теперь территория D₂ связана с двумя территориями — C₁ и C₂. Это проблема, поскольку это делает оставшуюся территорию несвязной. Чтобы решить эту проблему, C₂ позволяется выбрать другой сектор, длина которого меньше 1, так что он не нарушает связность[2]. Этот третий сектор снова обрезается всеми странами, как на шаге 5. В ответ от C₂ требуется отдать некоторую часть сектора, соединяющего D₂ с C₁, значение которой равно значению полученного третьего сектора.

Предложенное страной C₂ разрезание теперь содержит следующие части: D₂, сектор длиной 1, соединяющий D₂ с C₂, и два коротких сектора, которые не достигают границы D. Значение этой конструкции для C₂ равно ${\displaystyle {\tfrac {1}{n}}}$, для проигравших значение меньше чем ${\displaystyle {\tfrac {1}{n}}}$, а значение для других победителей не превосходит ${\displaystyle {\tfrac {1}{n}}}$.

Этот процесс продолжается с оставшимися победителями, пока не останется единственный победитель.

Если территория D k-связна с конечным k, делёж может быть осуществлён по индукции по k.

Если ${\displaystyle k=1,}$ D связно и может быть поделено с помощью протокола из предыдущей секции.

В противном случае ${\displaystyle (k>1)}$, обозначим внешнюю границу D как B₁, а внутренние границы как ${\displaystyle B_{2},\dots ,B_{k}}$.

Находим линию L, связывающую внешнюю границу B₁ с внутренней границей B_k, такую, что для всех стран значение этой линии L равно 0. Это сделать можно ввиду следующего аргумента. Имеется несчётное число попарно непересекающихся линий, связывающих B₁ и B_k, содержащихся в D. Но их мера в D конечна, так что число линий с положительной мерой должно быть счётно, а тогда есть линия с нулевой мерой.

Множество ${\displaystyle D\setminus L}$ является ${\displaystyle (k-1)}$-связным. Разобъём его рекурсивно, затем назначим L произвольно любой стране, с которой эта область граничит. Это не нарушает справедливости дележа, поскольку значение L для всех стран равно 0.