| "Дележ сокровища" ID:31234 |
Сб, 9 июня 2007 22:46 [#] [») |
|
|
При прочтении одной темы в разделе одностоловых турниров, мне вспомнилась одна игра. Чтобы сильно не оффтопить, выложу ее здесь. Если баян, отпишитесь плз, если нет, попробуйте решить 
100 пиратов делят сокровище в 100 золотых слитков. Дележ происходит так
1) Каждый пират имеет свой ранг. От самого высшего (капитана) до низшего (юнги). Пусть, к примеру, в числах это от 1 до 100. Одинаковых рангов нет.
2) Самый высший по рангу пират предлагает свой вариант дележа. Если хотя бы половина оставшихся (включая того, кто делит) пиратов поддержит этот дележ, то дележ принимается. Если же больше половины пиратов будет против, то тому, кто делит отрубают голову и следующий по рангу осуществляет попытку дележа опять.
То есть, к примеру, если пиратов двое, то высший по рангу просто забирает себе все, и дележ проходит, т.к. половина(он сам) за.
Существует ли дележ, при котором дележ капитана пройдет? Или же ему отрубят голову, а кто-то следующий сможет поделить? Кто?
Сразу оговорюсь, понятия жадности по отношению к соседу в этой игре нет - каждый пират имея выбор из двух альтернатив:
а)он получает 1 слиток, его сосед - миллион слитков
б)он получает 0, но и сосед получает 0,
выберет а). То есть, каждый максимизирует свой выигрыш.
Если кто решит, ответ плз белым напишите.
|
|
|
| Re: "Дележ сокровища" ID:31244 ответ на 31234 |
Вт, 12 июня 2007 16:34 («] [#] [») |
|
|
Если я правильно понял условия задачи, решение тут.
<font color="white">
Обозначим пиратов п1, п2, ..., п100 в соответствии с рангом.
Решаем с конца.
Если пиратов осталось двое (п2 и п1), то п2 забирает все 100 слитков, п1 - 0 слитков.
Если пиратов осталось трое, п3 для того, чтобы делёж прошёл, нужна поддержка одного пирата, для этого ему достаточно дать 1 слиток п1 (слитки ведь нельзя делить на части?). Так как п1 понимает, что отказавшись от этого дележа он не получит ничего, он поддержит его. Остальные 99 слитков п3 забирает себе.
Когда пиратов 4, п4 нужна поддержка одного, его делёж: п2 - 1, п4 - 99, п2 поддерживает.
В общем случае при 2N пиратах п2N даёт по 1 слитку всем пиратам чётного ранга, остальное забирает себе; при 2N+1 пиратах п2N+1 даёт по 1 слитку всем пиратам нечётного ранга, остальное забирает себе.
Для N=1 доказано, индукционный переход доказывается аналогично.
Таким образом, в случае 100 пиратов капитан заберёт себе 51 слиток и даст по 1 слитку пиратам п2, п4, ..., п98, и этот делёж пройдёт. </font>
|
|
|
| Re: "Дележ сокровища" ID:31245 ответ на 31234 |
Вт, 12 июня 2007 20:26 («] [#] |
|
|
|
SunnyRay, все верно
|
|
|
