Мудрый папа⁠⁠

В детстве из-за маленькой разницы в возрасте мы с сестрой очень много дрались, только дай повод. И один из поводов - это один сникерс на двоих. Отец поступал мудро: говорил одному из нас делить сникерс, а другой выбирал. Мы были заинтересованы, чтобы сникерс был поделен поровну.

P/S доходило, что мы делили сникерс с помощью линейки.

195

warscape

6 лет назад

Модификация на троих

https://geektimes.ru/post/282030/

Если Алиса, Боб и Чарли (A, B, C) хотят разделить торт, алгоритм начинается с того, что Чарли делит торт на три куска, которые для него выглядят равноценными. Алиса и Боб выбирают куски, нравящиеся им. Если они выберут разные куски – вуаля, каждый получает то, что хотел.

Если Алиса и Боб выберут один кусок, тогда Боб отрезает небольшую часть от этого куска так, чтобы кусок стал равноценен, с его точки зрения, другому куску торта – тому, который бы Боб выбрал во вторую очередь. Отрезанный остаточек откладывается. Теперь Алиса должна выбрать лучший для себя кусок из оставшихся трёх, а затем выбирает Боб – с условием, что он возьмёт обрезанный им кусок, если Алиса его не выберет. Чарли получает третий кусок.

В результате никто никому не завидует. Алиса выбирала первой. Боб получил один из двух одинаково ценных для него кусков. Чарли получил один из трёх изначальных кусков, которые он резал сам.

Остаётся лишь небольшой отрезанный остаточек. Но его можно разделить, не начиная алгоритм сначала и не попадая в бесконечный цикл обрезаний и выборов, поскольку Чарли в любом случае удовлетворён своим куском – и даже если бы тот, кому достался обрезанный кусок, получил бы в довесок к нему весь остаточек целиком, для Чарли это не выглядело бы нечестным, потому что обрезанный кусок и остаточек в сумме дадут кусок торта, эквивалентный его куску – ведь он изначально сам эти куски и нарезал.

Теперь, если, к примеру, Алисе достался обрезанный кусок, то Боб режет обрезки на три части, эквивалентные с его точки зрения, Алиса из этих кусков выбирает один себе, затем выбирает Чарли, затем Боб. Все счастливы: Алиса выбирала первой, Чарли получает кусок лучше, чем у Боба (и ему всё равно, сколько взяла Алиса), а с точки зрения Боба все три куска равноценны.

раскрыть ветку