Загадка про пятерых пиратов

Brat Levon · Чт окт 25, 2001 5:20 pm

Пять пиратов делят между собой 1000 долларов по следующей процедуре.
1. Они кинули жребий и рассчитались на 1-й - 5-й.
2. По очереди, начиная с первого, пираты предлагают варианты раздела. Если за предложеный вариант голосует большинство (если всего пиратов нечетное число, то голос предлагающего учитывается, а если четное, то нет), то вариант принимается. Если большинства нет, то предлагавшего пирата убивают, и свой вариант предлагает следующий.
3. Все пираты очень умные и умеют просчитывать ходы вперед.
4. Все пираты очень жадные, и стараются получить как можно больше денег при разделе.
5. Пираты также кровожадные, то-есть из двух вариантов, в которых пират получает одинаковое количество денег, пират выберет то, где погибает больше людей.

Какое максимальное количество денег может получить первый пират? Какое предложение он должен сделать для этого?

Пожалуйста, не торопитесь публиковать решение, пишите сначала только ответ.

Drom · Сообщение **Drom** » Чт окт 25, 2001 5:32 pm

997 ?

RrM · Сообщение **RrM** » Чт окт 25, 2001 6:56 pm

http://www.privet.com/ubbcgi/ultimatebb.cgi?ubb=get_topic&f=15&t=000005&p=6

Только ее так и не решили, насколько я помню... Там слишком много задач одновременно решали.

Melkor · Пт окт 26, 2001 8:15 am

У меня тоже 997 выходит, но я исходил из предположения, что, несмотря на кровожадность, пират между своей смертью и жизнью с 0 долларов все же выберет второе.

Ну, а предложение 997 0 1 2 0 (или 997 0 1 0 2)

[ 26-10-2001: Message edited by: Melkor ]

-ЭР- · Пт окт 26, 2001 7:32 pm

<BLOCKQUOTE>quote:<HR>Originally posted by Melkor:
У меня тоже 997 выходит
[ 26-10-2001: Message edited by: Melkor ]<HR></BLOCKQUOTE>

Если первый предложит 997, то сильно вряд ли его поддержат остальные. Никто из остальных 997 добровольно первому не отдаст. По-моему задачка нетривиальная (если я ничего не пропустил) и я бы предложил попробовать решить ее для трех пиратов.

moleg · Пт окт 26, 2001 7:54 pm

Остался один пират - 0 0 0 0 1000
Осталось 2 пирата - 0 0 0 0 1000
Осталось 3 пирата - 0 0 999 1 0
Осталось 4 пирата - 0 997 0 2 1
Осталось 5 пиратов - 996 0 1 3 0 или 997 0 1 0 2

Максимум - 997 и расклад 997 0 1 0 2

OlgaR · Сб окт 27, 2001 1:42 am

Цитирую с сайта www.techinterview.org (длинно и по-английски) (в свете следующей реплики привожу условие и разъяснение)

Five pirates have 100 gold coins. They have to divide up the loot. In order of seniority (suppose pirate 5 is most senior, pirate 1 is least senior), the most senior pirate proposes a distribution of the loot. They vote and if at least 50% accept the proposal, the loot is divided as proposed. Otherwise the most senior pirate is executed, and they start over again with the next senior pirate. What solution does the most senior pirate propose? Assume they are very intelligent and extremely greedy (and that they would prefer not to die).

(to be clear on what 50% means, 3 pirates must vote for the proposal when there are 5 for it to pass. 2 if there are 4. 2 if there are 3. etc... )

...now for the real solution. Pirate 5 being the most senior knows that he needs to get 2 other people to vote for his solution in order for him not to be executed. So who can he get to vote for him, and why would they choose to vote for him? If you start thinking that pirate 4 will never vote for him, because he would rather have 5 die and then be in charge and take it all for himself, you are on the right track. But it gets more complicated.

Let's consider if there were only 1 pirate. Obviously he would take it all for himself and no one would complain.

If there were 2 pirates, pirate 2 being the most senior, he would just vote for himself and that would be 50% of the vote, so he's obviously going to keep all the money for himself.

If there were 3 pirates, pirate 3 has to convince at least one other person to join in his plan. So who can he convince and how? Here is the leap that needs to be made to solve this problem. Pirate 3 realizes that if his plan is not adopted he will be executed and they will be left with 2 pirates. He already knows what happens when there are 2 pirates as we just figured out. Pirate 2 takes all the money himself and gives nothing to pirate 1. So pirate 3 proposes that he will take 99 gold coins and give 1 coin to pirate 1. Pirate 1 says, well, 1 is better than none, and since i know if i don't vote for pirate 3, i get nothing, i should vote for this plan.

Now we know what happens when there are 3 pirates. So what happens with 4? Well pirate 4 has to convince 1 other person to join in his plan. He knows if he walks the plank then pirate 3 will get 99 coins and pirate 1 will get 1 coin. Pirate 4 could propose giving pirate 1 two coins, and surely pirate 1 would vote for him, since 2 is better than 1. But as greedy as he is, pirate 4 would rather not part with 2 whole coins. He realizes that if he gets executed, then pirate 3's scenario happens and pirate 2 gets the shaft in that scenario (he gets zero coins). So pirate 4 proposes that he will give 1 coin to pirate 2, and pirate 2 seeing that 1 is better than 0 will obviously vote for this plan.

A common objection is that pirate 2 is not guaranteed to vote for this plan since he might hope for the case when there are only 2 pirates and then he gets all the booty. But that is why I said that the pirates are extremely intelligent. Pirate 2 realizes that pirate 3 is smart enough to make the optimal proposal, so he realizes that there will never be 2 pirates left, because 3 doesn't want to die and we just showed that 3 has a winning proposal.

So lets sum up at this point

Pirate 1 2 3 4 5
5. ? ? ? ? ?
4. 0 1 0 99 -
3. 1 0 99 - -
2. 0 100 - - -
1.100

Once you see the pattern it becomes very clear. You have to realize that when a pirate's plan does not succeed then that means you are in the same situation with one less pirate.
1. Pirate 1 needs 0 other people to vote for him. so he votes for himself and takes all the money. 2. Pirate 2 needs 0 other people to vote for him. So he votes for himself and takes all the money. Pirate 1 gets 0. 3. Pirate 3 needs 1 other person to vote for him. He gives 1 coin to pirate 1 for his vote - if we are reduced to 2 pirates, pirate 1 gets 0 so pirate 1 knows 1 is better than none. Pirate 3 takes 99. Pirate 2 gets 0. 4. Pirate 4 needs 1 other person to vote for him. He gives 1 coin to pirate 2 - if we reduce to 3 pirates, pirate 2 gets 0 so pirate 2 knows 1 is better than none. pirate 4 takes 99. Pirate 3 gets 0. Pirate 1 gets 0. 5. Pirate 5 needs 2 other people to vote for him. It's clear now that the 2 people he needs to convince are the 2 who get shafted in the 4 pirate scenario - pirate 3 and pirate 1. So he can give them each 1 coin (which is better than 0 - what they would get otherwise) and keep 98 for himself.

Pirate 1 2 3 4 5
5. 1 0 1 0 98

What happens if there are 15 pirates? Pirate 15 needs 7 other people to vote for him, so he recruits pirates 13,11,9,7,5,3, and 1 with 1 coin each and keeps 93 coins himself. Those pirates will all vote for him because they know that they get 0 coins if he dies and pirate 14 is in charge.

[ 27-10-2001: Message edited by: OlgaR ]

-ЭР- · Сб окт 27, 2001 2:56 am

<BLOCKQUOTE>quote:<HR>Originally posted by moleg:
Максимум - 997 и расклад 997 0 1 0 2[/QB]<HR></BLOCKQUOTE>

Да, дал маху я. Как человек исключительно миролюбивый, совершенно пропустил, что у них чуть что не так - сразу " к стенке". [img:37e336e36f]images/smiles/icon_smile.gif[/img:37e336e36f] А когда сформулировал задачку как она мне показалась, то понял, что она совсем другая. Но, по-моему не менее занятная, чем оригинал. Итак, в отличие от оригинальной задачи дядьки друг друга не убивают, а начинают заново, если не сложилось большинство.

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

P.S. Решении процитрованное OlgaR' похоже, для другой задачи. Так для четырех игроков утвержение "pirate 4 has to convince 1 other person to join in his plan" не похоже на правду, так как по условию для четного количества игроков голос предлагающего не учитывается, т.е. "четвертый" должен уговорить двух.

[ 26-10-2001: Message edited by: -ЭР- ]

[ 26-10-2001: Message edited by: -ЭР- ]

Melkor · Сб окт 27, 2001 8:12 am

<BLOCKQUOTE>quote:<HR>Originally posted by moleg:
Остался один пират - 0 0 0 0 1000
Осталось 2 пирата - 0 0 0 0 1000
Осталось 3 пирата - 0 0 999 1 0


А здесь у меня было 0 0 1000 0 0, т.к., если второй пират не поддержит третьего, то будет убит первым, и, следовательно, он предпочтет жизнь без денег смерти. Не знаю, оправдано ли это

Осталось 4 пирата - 0 997 0 2 1
Осталось 5 пиратов - 996 0 1 3 0 или 997 0 1 0 2
Соответственно
4 - 0 998 0 1 1
5 - 997 0 1 2 0 (или 0 2)
<HR></BLOCKQUOTE>

moleg · Сб окт 27, 2001 5:24 pm

Originally posted by Melkor:
[i:3ee2fcdad2]А здесь у меня было 0 0 1000 0 0, т.к., если второй пират не поддержит третьего, то будет убит первым, и, следовательно, он предпочтет жизнь без денег смерти. Не знаю, оправдано ли это[/i:3ee2fcdad2]

По условию:
[i:3ee2fcdad2]5. Пираты также кровожадные, то-есть из двух вариантов, в которых пират получает одинаковое количество денег, пират выберет то, где погибает больше людей.[/i:3ee2fcdad2]

Стало быть при нуле второй пират вынужден проголосовать против.

Melkor · Вс окт 28, 2001 8:04 am

<BLOCKQUOTE>quote:<HR>Originally posted by moleg:
Originally posted by Melkor:
[i:5fb59cad88]А здесь у меня было 0 0 1000 0 0, т.к., если второй пират не поддержит третьего, то будет убит первым, и, следовательно, он предпочтет жизнь без денег смерти. Не знаю, оправдано ли это[/i:5fb59cad88]

По условию:
[i:5fb59cad88]5. Пираты также кровожадные, то-есть из двух вариантов, в которых пират получает одинаковое количество денег, пират выберет то, где погибает больше людей.[/i:5fb59cad88]

Стало быть при нуле второй пират вынужден проголосовать против.<HR></BLOCKQUOTE>

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

moleg · Вс окт 28, 2001 1:29 pm

Melkor, мы поняли друг друга - мир, дружба, жувачка [img:f38fd2f278]images/smiles/icon_biggrin.gif[/img:f38fd2f278]

Melkor · Вс окт 28, 2001 1:51 pm

<BLOCKQUOTE>quote:<HR>Originally posted by moleg:
Melkor, мы поняли друг друга - мир, дружба, жувачка [img:afc5f3810d]images/smiles/icon_biggrin.gif[/img:afc5f3810d]<HR></BLOCKQUOTE>

Да я, вобщем-то, не из желания поспорить написал это. Просто меня вопрос, как поведет себя кровожадный пират, если на кону - его, а не чья-то, жизнь, интересовал с самого начала. С точки зрения психологии [img:afc5f3810d]images/smiles/icon_smile.gif[/img:afc5f3810d]