Есть задача — разделить некое целое между несколькими претендентами и чтобы при этом каждый остался доволен. Причём разделить в реальных бытовых условиях — пирог, например — с линейкой и циркулем вокруг него не сильно удобно бегать, да и целое бывает неоднородным.
Первый делит, второй выбирает. Соответственно, первый старается поделить поровнее, чтобы впоследствии порадоваться любой доставшейся доле.
Почему не остаётся недовольных? Потому что каждый обладает всей полнотой выбора, при этом — о чудо — не притесняя соседей. Почти 200% свободы :-) С решением внешнего судьи — выбранного человека или судьбы при жеребьёвке — всегда могут несогласиться (хотя бы внутренне), здесь же каждый участвует в вершении своей судьбы потому что что-то делает, а не только принимает чужой вердикт.
Альтернативные решения и подобные задачи приветствуются.
а) N1 делит пирог на три части как может; и снова покидает сцену.
б) N2 и N3 выбирают себе по куску. Если их выбор разнится, на этом делёж и заканчивается — N1 забирает что осталось.
в) (Если оба претендуют на один и тот же кусок.) Теперь надо избавиться от какого-то куска, чтобы осталось их два — скинуть один номеру первому.
г) Итак, осталось два куска и два претендента. Задача сводится к дележу «на двоих» два раза. Один кусок режет N1, выбирает N2. Со вторым куском наоборот:
В худшем случае пирог режется на 5 частей.
От сговора между двумя из трёх участников этот алгоритм не спасает. Ну и при дальнейшем увеличении количества народа, ком организационных трудностей будет разрастаться в прогрессии. Интересно, возможно ли улучшить эти моменты…
На двоих
Первый делит, второй выбирает. Соответственно, первый старается поделить поровнее, чтобы впоследствии порадоваться любой доставшейся доле.
Философская идея
Почему не остаётся недовольных? Потому что каждый обладает всей полнотой выбора, при этом — о чудо — не притесняя соседей. Почти 200% свободы :-) С решением внешнего судьи — выбранного человека или судьбы при жеребьёвке — всегда могут несогласиться (хотя бы внутренне), здесь же каждый участвует в вершении своей судьбы потому что что-то делает, а не только принимает чужой вердикт.
Альтернативные решения и подобные задачи приветствуются.
На троих (уже посложнее)
а) N1 делит пирог на три части как может; и снова покидает сцену.
б) N2 и N3 выбирают себе по куску. Если их выбор разнится, на этом делёж и заканчивается — N1 забирает что осталось.
в) (Если оба претендуют на один и тот же кусок.) Теперь надо избавиться от какого-то куска, чтобы осталось их два — скинуть один номеру первому.
Просто дать первому выбрать свой кусок нельзя, чтобы удержать его от соблазна порезать пирог заведомо неровно и завладеть самой большой, по итогу, долей:
Выбирать что достанётся N1, как и в дележе «на двоих», должны N2 и N3. Каждый из них теперь выбирает кусок для N1. В случае единого мнения, N1 кушает свой кусок; иначе, он выбирает из двух ему предложенных и опять удаляется откушивать свою долю.
г) Итак, осталось два куска и два претендента. Задача сводится к дележу «на двоих» два раза. Один кусок режет N1, выбирает N2. Со вторым куском наоборот:
В худшем случае пирог режется на 5 частей.
Further reading
От сговора между двумя из трёх участников этот алгоритм не спасает. Ну и при дальнейшем увеличении количества народа, ком организационных трудностей будет разрастаться в прогрессии. Интересно, возможно ли улучшить эти моменты…
