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

[scholar_vit]

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

Comments

[scholar-vit.livejournal.com]

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

[aikr.livejournal.com]

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