В детстве из-за маленькой разницы в возрасте мы с сестрой очень много дрались, только дай повод. И один из поводов - это один сникерс на двоих. Отец поступал мудро: говорил одному из нас делить сникерс, а другой выбирал. Мы были заинтересованы, чтобы сникерс был поделен поровну.
P/S доходило, что мы делили сникерс с помощью линейки.
Модификация на троих
https://geektimes.ru/post/282030/
Если Алиса, Боб и Чарли (A, B, C) хотят разделить торт, алгоритм начинается с того, что Чарли делит торт на три куска, которые для него выглядят равноценными. Алиса и Боб выбирают куски, нравящиеся им. Если они выберут разные куски – вуаля, каждый получает то, что хотел.
Если Алиса и Боб выберут один кусок, тогда Боб отрезает небольшую часть от этого куска так, чтобы кусок стал равноценен, с его точки зрения, другому куску торта – тому, который бы Боб выбрал во вторую очередь. Отрезанный остаточек откладывается. Теперь Алиса должна выбрать лучший для себя кусок из оставшихся трёх, а затем выбирает Боб – с условием, что он возьмёт обрезанный им кусок, если Алиса его не выберет. Чарли получает третий кусок.
В результате никто никому не завидует. Алиса выбирала первой. Боб получил один из двух одинаково ценных для него кусков. Чарли получил один из трёх изначальных кусков, которые он резал сам.
Остаётся лишь небольшой отрезанный остаточек. Но его можно разделить, не начиная алгоритм сначала и не попадая в бесконечный цикл обрезаний и выборов, поскольку Чарли в любом случае удовлетворён своим куском – и даже если бы тот, кому достался обрезанный кусок, получил бы в довесок к нему весь остаточек целиком, для Чарли это не выглядело бы нечестным, потому что обрезанный кусок и остаточек в сумме дадут кусок торта, эквивалентный его куску – ведь он изначально сам эти куски и нарезал.
Теперь, если, к примеру, Алисе достался обрезанный кусок, то Боб режет обрезки на три части, эквивалентные с его точки зрения, Алиса из этих кусков выбирает один себе, затем выбирает Чарли, затем Боб. Все счастливы: Алиса выбирала первой, Чарли получает кусок лучше, чем у Боба (и ему всё равно, сколько взяла Алиса), а с точки зрения Боба все три куска равноценны.
Соберётесь вчетвером, и всего за 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096 шагов тортик будет справедливо разделён. Как раз аппетит нагуляете :)
Папа , Мама , Сын и Дочь хотят разделить торт
1)Папа делит торт на две равные для него части
2)Мама выбирает себе одну ( оба довольны )
3)Папа и Мама делят свою половину торта на три равных для них части
4)Сын выбирает по одной части (все довольны)
5)Папа , Мама , Сын делят свою половину торта на четыре равных для них части
6)Дочь выбирает по одной части (все довольны)
всего 6 ходов
для n людей 2*(n-1) ходов
Скорее всего они решили похожую задачу , как разделить добычу между n людей , чтобы каждому досталось не меньше 1/n добычи по их мнению . А в статье говориться как поделить , чтобы у всех было поровну по их мнению
Есть метод попроще чем дополнительно нарезать и думать что делать с остатком. Я его с детства помню на примере мешка с зерном:
Я рассыпаю зерно на три кучи, на мой взгляд, поровну и отхожу в сторону. Мне подойдет любая из куч. Пусть затем Петр укажет наименьшую, по его мнению, кучу зерна. Если Николай также посчитает, что зерна в этой куче меньше трети, то отдайте ее мне, а остаток зерна делите между собой известным уже способом. Если же Николай решит, что в указанной куче не меньше трети зерна, пусть возьмет ее себе. Петр возьмет наибольшую, по его мнению, кучу, а оставшаяся достанется мне.
Тут проблема в том, что после отпадания одного из участников, двое других могут так криво поделить, что у одного допустим будет куча в 20%, а у другого в 46%
Ну и по мнению отпавшего, получившиеся кучи не будут равными для всех участников.
Рассыпал бы зерно на две равные кучи и предложил бы Петру выбрать любую, а оставшуюся взял бы себе. Оба мы были бы довольны.
