Ответ в задачке про пиратов

[scholar_vit]

Пожалуй, мне следовало заскринить комментарии в задаче про пиратов: bazar_wokzal и rioman почти мгновенно её решили. Ответ такой: пираты делятся на две партии, с четным раногом и с нечетным. Капитан дает по одной монете своим однопартийцам, а остальные берет себе. Этот вариант для них выгоден, так как в противном случае первый помощник сделает то же самое со своими однопартийцами. Доказательство - несложная индукция по n.

Comments

[aikr.livejournal.com]

И между прочим, это неправильный ответ. Правильный такой: капитан берёт все деньги себе, и все (кроме старпома) за это голосуют.

Доказательство:

Начнём с ситуации, когда пиратов ровно два. Капитан берёт все деньги себе и голосует за это: 50% голосов (из имеющихся двух) ему обеспечено. Отсюда видно, что при n=2 последний пират гарантированно ничего не получает.

Переходим к ситуации, когда пиратов трое. Капитан предлагает все деньги отдать ему. Второй пират, естественно, возражает. А третий пират, последний по рангу? Он знает, что если поддержать старпома, то капитан будет «списан за борт», и ситуация будет сведена к предыдущей. Но ведь мы уже выяснили, что при n=2 последний пират ничего не получает! То есть кого бы он ни поддержал, он остаётся без денег. Поэтому он голосует за предложение капитана: по деньгам ничего не изменится, зато на одного боевого товарища останется больше. Отсюда видно, что при n=3 два последних пирата гарантированно ничего не получают.

Переходим к n=4. Ну, вы поняли, да? Второй по рангу и хотел бы свести ситуацию к n=3, но два последних пирата знают, что денег им так и так не обломится, так хоть капитана бы сохранить, дело-то не последнее. И опять все деньги без остатка достаются капитану.

Дальнейшее очевидно: при любом n сводить ситуацию к n-1 невыгодно последним n-2 пиратам и тем более невыгодно первому. Только бедный старпом хотел бы избавиться от капитана, но кто ж ему даст...

[scholar-vit.livejournal.com]

http://scholar-vit.livejournal.com/202425.html?thread=7122105#t7122105

[aikr.livejournal.com]

Ага, понятно. Просто в том варианте, в котором я встречал эту задачу раньше, есть дополнительное условие: если по деньгам нет разницы, пират голосует за тот вариант, который позволяет оставить максимальное количество пиратов в живых. Надо мне было обратить внимание, что здесь этого условия нет.