Тема: Задача о честном делении и делении без зависти квадратного торта
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
📋 Содержание
2 Постановка задачи и основные результаты 3
3 Конфигурационные пространства 5
4 Дискретная теория Морса 8
5 Одномерный случай 9
6 Без ограничений на функции размещения 11
7 Количественное ограничение 12
8 Доказательство основных результатов 15
Список литературы
📖 Введение
Таким образом, каждому разрезанию (х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 и следующие за ней следствия описывают, в каких случаях деление без зависти существует.
формальные определения будут даны в следующем параграфе