Введение 2
2 Постановка задачи и основные результаты 3
3 Конфигурационные пространства 5
4 Дискретная теория Морса 8
5 Одномерный случай 9
6 Без ограничений на функции размещения 11
7 Количественное ограничение 12
8 Доказательство основных результатов 15
Список литературы
Классическая задача справедливого деления торта формулируется следующим образом. Дан отрезок [0,1] — торт, и к игроков, которые некоторым образом делят этот отрезок на к частей и распределяют между собой. Тогда разрезанию торта соответствует набор х = (х1, х2,..., хк-1) е Rk-1чисел х;, таких что 0 = х06 х16 х2 6 ... 6 хк_16 хк = 1.
Таким образом, каждому разрезанию (х15..., хк_1) соответствуют к отрезков [х;, х;+1], где 0 6 i 6 к - 1, которые и раздаются игрокам. Для каждого разрезания известны предпочтения игроков — а именно, какие отрезки в данном разрезании лучшие с точки зрения каждого игрока. Спрашивается, можно ли найти такое разрезание торта и распределение кусков, чтобы каждый игрок получил тот кусок, который с его точки зрения не хуже любого другого.
Известно, что ответ на этот вопрос зависит от того, какие накладываются условия на предпочтения. Если предпочтения покрывающие, замкнутые,1и каждый игрок предпочитает только невырожденные куски (то есть куски ненулевой длины), то деление без зависти существует для любого количества игроков — это теорема Гейла, см. [3]. Условие на невырожденные куски можно ослабить, в этом случае существование деления без зависти будет зависеть от к — см. [1] и [4].
В данной работе в качестве торта выступает не отрезок [0,1], а квадрат [0,1]2, который разрезается п - 1 вертикальными и т - 1 горизонтальными разрезами на пт прямоугольных кусков. Эти куски, в свою очередь, раздаются к игрокам. Отметим, что в этой постановке игроки могут получать любое количество кусков (не ровно один как в классической задаче). Спрашивается, при каких условиях на п, т, к и предпочтения игроков существует деление без зависти.
В параграфе2 формализуется описанная выше задача и описываются условия на предпочтения, которые требуется в доказываемых результатах. В параграфе3описывается строение конфигурационных пространств, возникающих в новой задаче. Ключевую роль для последующих доказательств играют теорема3.1 и её следствие 3.2, а также представление конфигурационных пространств с помощью числовых таблиц, следующее из этих теорем. В параграфе4 приводятся без доказательств основные теоремы дискретной теории Морса, которые используются в параграфах 5,6 и 7 для изучения топологических свойств конфигурационных пространств.
Наконец, в параграфе8 формулируются и доказываются основные результаты. А именно, в теореме8.1 приводится контрпример, показывающий, что при достаточно большом количестве игроков деления без зависти может не существовать, а теорема 8.2 и следующие за ней следствия описывают, в каких случаях деление без зависти существует.
формальные определения будут даны в следующем параграфе
