| 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>
|
|
|