Решение задачи 312

Условие:

Четверо пиратов: капитан, старшина, матрос и юнга (звания идут в порядке убывания значимости) нашли клад со 100 золотыми монетами. Им нужно разделить эти 100 монет между собой. Этот процесс происходит следующим образом: сначала капитан выбирает, как нужно разделить монеты среди четверых моряков (каждому достается целое число монет) и происходит голосование в котором участвуют все. Если большинство голосов против такого разделения, то капитана убивают, иначе, пираты получают соответствующее количество монет. Если капитана убили, то свой вариант предлагает старшина и опять происходит голосование. Так происходит и далее. Какое наибольшее количество монет может гарантировать себе капитан, если все пираты действуют наиболее оптимальным образом? Дополнительное условие: если невозможно увеличить собственную выгоду, то пират действует так, чтобы поддержать моряка меньшей значимости. Например: при всех прочих равных, юнга будет действовать в интересах матроса, а не старшины.

Решение:

Шаг 1

Давайте сначала представим, что пиратов всего двое. Первый - старший по значимости, второй - младший. Очевидно, что первый пират предлагает распределение (100,0) и забирает все 100 монет себе, поскольку второй не может создать большинство "голосов против" одним голосом из двух.

Шаг 2

Теперь допустим, что пиратов всего трое. Опять есть первый (самый старший) второй и третий. Второй знает, что может забрать себе все 100 монет, если первого убьют. Давайте предположим, что первый выбрал распределение (100,0,0). Тогда очевидно, что второй голосует против и третий тоже (в принципе третий не выиграет ничего, даже если первого убьют, но как сказано в условии, он действует в интересах второго, потому что он ниже рангом). Значит 100 монет первый выиграть не может. Приведем пример стратегии, когда он может выиграть 99 монет. Для этого он должен предложить распределение (99,0,1). В этом случае второй голосует против, а третий голосует за, т.к. иначе он не выигрывает ничего.

Шаг 3

Теперь у нас есть 4 моряка: первый (самый старший), второй, третий и четвертый. Понятно, что если первый предложит распределение (100,0,0,0), то все проголосуют против и его убьют. Покажем, что он может выиграть 99 монет. Для этого он должен предложить распределение (99,0,1,0). Заметим, что второй будет голосовать против, т.к. в случае смерти первого у него есть тактика (как мы уже показали) взять себе 99 монет. В ту же очередь, чтобы не допустить того, чтобы остаться ни с чем (шаг 2), третий будет голосовать за (в этом случае он выигрывает хотя бы одну монету). Таким образом, большинство "голосов против" не будет достигнуто и первый (т.е. капитан) может забрать себе 99 монет.

Ответ: 99.