Прикольная задача с РСДН

← →
Igorek (2003-12-18 13:09) [0]

"5 пиратов делят добычу - 1000 золотых (богатенькие буратинки, честное слово! стыдно!)

Делят "по понятиям", которые просты, как деревянная нога.
Сначала самый старший и уважаемый пират раздает каждому его долю.
Если большинство коллег° согласно, на том и останавливаются.
Если нет - пират перестает быть самым старым и уважаемым, и уходит покормить рыбок°°.

° Если мнения разделились поровну, то решающий голос - у самого старшего и уважаемого пирата. Естественно, в свою пользу.

°° Пираты очень, очень не любят уходить кормить рыбок. Только если их попросят большинство коллег.

Пираты флота Ея Королевского Величества - люди в высшей степени образованные, хотя и беспринципные.
Поэтому все они прекрасно считают на много ходов вперед, почти как Каспаров.

Как будет разделена добыча?"

(с) Кодт модератор

← →
Rouse_ (2003-12-18 13:21) [1]

600 и по сто остальным
500 и по 125 остальным
400 и по 150 остальным
...
Каждому по 200 ;)

Дальше продолжать?

А вообщето достаточно разделить добычу между собой и двумя другими поровну, и не пойдет он кормить рыбок ;)

← →
nikkie (2003-12-18 13:24) [2]

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

то старший пират берет себе 995 золотых, а оставшиеся 5 распределяет одним из 3 способов (по старшинству)
0 - 1 - 2 - 2
0 - 1 - 3 - 1
0 - 0 - 3 - 2

← →
Igorek (2003-12-18 13:38) [3]

А главное ответ - супер! (Если я правильно решил)

← →
nikkie (2003-12-18 13:41) [4]

>Igorek
ну так давай свой ответ (без решения пока).

← →
Кабан (2003-12-18 13:58) [5]

нафига давать ответ без решения. дайте решить, интересная задача

← →
Кабан (2003-12-18 14:02) [6]

Мое решение (по старшинству): 998 - 0 - 1 - 0 - 1

← →
DAC (2003-12-18 14:07) [7]

по убыванию возраста, начиная с себя 498-1-501-0-0

← →
Кабан (2003-12-18 14:10) [8]

мнения разделились :)

← →
Reindeer Moss Eater (2003-12-18 14:26) [9]

Старший возьмет себе 0
Двум другим даст по 500.
Еще двум тоже по нулям.

← →
Reindeer Moss Eater (2003-12-18 14:28) [10]

Иначе он умрет.

← →
Agent13 (2003-12-18 14:29) [11]

Правильный ответ: см. Кабан (18.12.03 14:02) [6]
Я видел похожую задачу с решением, только там было 10 пиратов и 100 золотых, но сути дела это не меняет.

← →
nikkie (2003-12-18 14:32) [12]

почитав ветку на рсдн, понял, что у меня в последнем шаге рассуждения ошибка. правильный ответ 997-0-1-0-2. на рсдн есть решение близкое к этому, только опять на последнем шаге ошибка...

← →
DAC (2003-12-18 14:35) [13]

> nikkie © (18.12.03 14:32) [12]

согласен 997-0-1-0-2

← →
nikkie (2003-12-18 14:42) [14]

блин... до чего же неудобный форум на рсдн.

← →
Igorek (2003-12-18 14:43) [15]

Мое решение - старший забирает все себе. Народ голосует 2 на 2. Те, кто голосует "за" понимают, что больше все равно не получат и нефиг комманду уменьшать.
Могу доказать.
:-)))

← →
Кабан (2003-12-18 14:43) [16]

Ну раз все сошлись на варианте 997-0-1-0-2, можно опубликовать решение задачи:

Формализуем несколько условий, скрытых в тексте:

1. Каждый пират стремится максимизировать свою долю добычи.
2. Каждый пират готов отказаться от добычи, если понимает,
что в противном случае он отправится кормить рыбок.
3. Каждый пират с удовольствием посмотрит, как его товарищь
кормит рыбок, если знает что его доля из-за этого не
уменьшится.

Решение:

1. Допустим осталось два пирата, тогда самый старший и
уважаемый пират оставит все деньги себе.

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

3. Допустим осталось 4 пирата.
Тогда сымый старший из них может поделит деньги по
старшенству след. способом: 0 - 1 - 0 - 999 и при равенстве
голосов выиграть спор. Он не может поделить монеты:
1-0-0-999, поскольку, тогда младший пират не согласится, т.к.
захочет посмотреть как старший кормит рыбок.

4. Вернемся к первоначальному дележу. Что мы имеем:
а) Младший пират готов согласится на 1 золотой, иначе рискует
ничего не получить.
б) Третий также знает, что не получит ничего, если пиратов
останется четверо.

Теперь, старший может разделить монеты:
1 - 0 - 1 - 0 - 998 за проголосуют 1, 3, 5

← →
Reindeer Moss Eater (2003-12-18 14:45) [17]

Первое решение о дележе монет принимает старший пират.
Его задача - иметь не меньше 2 согласных с его решением. Иначе он умирает.
Как этого достичь?

Поделить на троих?
Но тогда двое других с деньгами могут поддержать двоих других без денег для того, что бы утопить старшего пирата и делить еще и его деньги.
Старший пират вынужден дать поровну двум пиратам, и ничего не оставить себе, что бы у двух счастливых обладателей золота не появился соблазн продолжать делить дальше.

← →
nikkie (2003-12-18 14:51) [18]

>Кабан
>1. Допустим осталось два пирата, тогда самый старший и
> уважаемый пират оставит все деньги себе.
ошибка! решение принимает младший пират, который мочит старшего и забирает все деньги себе.

кстати, я решал поняв выражение "кормить рыбок" буквально. т.е. никого не убивают. если уж убивают, надо определить во сколько золотых пираты ценят свою жизнь. я получается решал при цене 0 золотых за жизнь. условие, что никто не хочет умирать означает, что цена >= 1000 золотых. интересно, что будет, если они ценят жизнь в 1 золотой...

← →
Кабан (2003-12-18 14:55) [19]

>>ошибка! решение принимает младший пират, который мочит
>>старшего и забирает все деньги себе.

Это как??????

Для тех кто в танке, повторяю условие задачи:

"Если мнения разделились поровну, то решающий голос - у самого старшего и уважаемого пирата. Естественно, в свою пользу."

← →
nikkie (2003-12-18 14:58) [20]

>Для тех кто в танке, повторяю условие задачи:
для тех, кто на бронепоезде объясняю. голос 1 пирата не может разделиться поровну. соответственно предпоследнему пирату ничего решать не придется, все решено без него :))
>Если большинство коллег° согласно, на том и останавливаются.

← →
DiamondShark (2003-12-18 14:58) [21]

Старший загребает всё.

← →
Кабан (2003-12-18 15:03) [22]

а есть ли уверенность, что фраза
"если большинство коллег согласно"
означает, что самый старший и уважаемый пират не учавствует в голосовании

← →
nikkie (2003-12-18 15:08) [23]

уверенности нет. твое понимание тоже возможно. тогда решение правильное. только так неинтересно - очень легко распространить на N пиратов. попробуй решить с моим пониманием.

← →
Кабан (2003-12-18 15:10) [24]

ну логика не сильно меняется, решение все равно надо проводить сверху вниз

← →
Vint (2003-12-18 15:14) [25]

глупая задачка :(
если исходить из того, что каждый пират стремится к максимальной выгоде, то:

старший не может взять себе долю т.е.
0-500-500-0-0

при любом другом раскладе его убивают и после соответственно поучается 500-500-0-0

пират получивший 500 не будет поддерживать нулевых т.к. получит тогда меньше, т.е. 333

← →
Igorek (2003-12-18 15:19) [26]

Исходим из такого уточнения: если пирату достанется больше если выкинуть старшего, то он голосует "против".

← →
nikkie (2003-12-18 15:30) [27]

>Кабан
>ну логика не сильно меняется
не сильно. цифирьки меняются. и при 7 пиратах уже не однозначно раскладывается.

>Igorek
уточнил, называется...

← →
Vint (2003-12-18 15:30) [28]

>Igorek © (18.12.03 15:19) [26]

это ни чего не меняет!
ведь не известно кто станет старшим пиратом?

← →
nikkie (2003-12-18 15:39) [29]

>ведь не известно кто станет старшим пиратом?
пираты не в один день родились. старший биологически.

← →
Vint (2003-12-18 15:58) [30]

>nikkie © (18.12.03 15:39) [29]

а если двое там двойняшки?
два брата-пирата :)

← →
Igorek (2003-12-18 22:09) [31]

Ну так что так быстро закончилось обсуждение? Неужели никому не интересно почему старший себе все забирает?

← →
OlDemon (2003-12-19 06:55) [32]

Дык чего тут еще мусолить?? Кабан привел правильное и логичное решение. Хорошая задачка.

← →
Vlad Oshin (2003-12-19 10:46) [33]

Мое решение (по старшинству): 998 - 0 - 1 - 0 - 1

не понял, честно говоря
все 4 будут против такого дележа и замочат старшего

← →
Igorek (2003-12-19 11:57) [34]

> OlDemon © (19.12.03 06:55) [32]
> Дык чего тут еще мусолить?? Кабан привел правильное и логичное
> решение. Хорошая задачка.

Ну-ну.

Вот мое решение:
Пронумеруем стадии голосования от 5 до 1 (номер = колл пиратов)
Определим как будет голосовать пират на любой стадии:
если ему предложено меньше, чем он получит на следующей стадии (если выкинуть старшего) то "против" иначе "за". Они же беспринципные (см. условие) и не голосуют "против" только для того что-бы увидеть как товарищ кормит рыбок.
Делит пират так, что бы набрать большинство или равное колличество голосов при макс. выгоде

Теперь пойдем от 1 стадии до 5:

стадия:дележ :голоса коллег
1 : 1000 :
2 : 0/1000 :+
3 : 1000/0/0 :+-
4 : 1000/0/0/0 :-++
5 : 1000/0/0/0/0 :-+++

Кто оспорит?

← →
Vint (2003-12-19 12:14) [35]

>Igorek © (19.12.03 11:57) [34]

ну что ты паришся с этой ерундой... :)
если често ничего не понял из твоего столбика...
или что, каждый раз старший забирает все, что ли?

← →
Vlad Oshin (2003-12-19 12:14) [36]

на каком основании не убъют главного, если он хотя бы возьмет больше половины?

← →
Vlad Oshin (2003-12-19 12:17) [37]

> пираты не в один день родились. старший биологически.

где сказано, что так передается старшинство?
и где сказано, что оно вообще передается?

← →
Bless (2003-12-19 13:12) [38]

Если старшинство определяется по возрасту или каким-то иным способом, по которому все заранее знают, кто будет следующим старшим, то Кабан [16] прав.
У меня тоже вышло 998-0-1-0-1.

Могу аргументировать, если захотите. Хотя в [16] все достаточно аргументировано, если подумать немного.

← →
Vint (2003-12-19 13:33) [39]

>Bless (19.12.03 13:12) [38]

даааа...
ну и что же мешает замочить им старшего и разделить на четверых например?

← →
Bless (2003-12-19 13:53) [40]

>у и что же мешает замочить им старшего и разделить на четверых
>например?

998-0-1-0-1 - это по порядку убывания старшинства.
Пронумеруем их для удобства. 1-самый старший,....5 - самый младший.
Замочить старшего 2-му и 4-му ничего не мешает.
А вот 3 и 5 мочить его не будут. Потому что если их останется 4, то добычу поделят не поровну, а так:
...-999-0-1-0. Соответственно 2,4 - за, 3,5 - против.
Ты спросишь, а почему это 4-ый согласится на 1 монету? Да потому что, если он не согласится, то завалят старшего, их останется трое и будет такой дележ ...-...-999-0-1, и он останется с носом.
Тут у тебя может возникнуть вопрос:

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

← →
Vint (2003-12-19 14:12) [41]

Потому что если их останется 4, то добычу поделят не поровну, а так:
...-999-0-1-0.
это из чего следует, что не поровну? старший - самоубийца что ли?

делить можно только так:
0-500-500-0-0 все!

при любом другом раскладе они или получают меньше, или умирает главарь, что имхо не выгодно!

← →
Bless (2003-12-19 14:15) [42]

>>...-999-0-1-0.
>это из чего следует, что не поровну? старший - самоубийца что ли?

Невнимательно читал. Это следует из того, что 4-ому будет достаточно и 1 монеты, потому что если их останется 3, он не получит вообще ничего. А 1>ничего.

← →
han_malign (2003-12-19 14:23) [43]

Из классики
1. Решение о выдаче черной метки принмается без участия "Главного".
2. "Главным" становится самый опытный.
3. Опытный "Главный" vs. "юнга" - "кормит рыб" "юнга".

На этих предпосылка введем терминологию и аксиоматику по старшинству - Старший(главарь), Полусредний(помошник), Средний(боцман), Полумладший(кок), Младший(юнга) - тот кто в начале списка - текущий Главный, он-же Делящий, он-же Рыбий завтрак, остальные - Кворум...

У меня вышло, что, поскольку при любом раскладе Кворум будет не доволен(поровну - старшие Кворума не довольны, кому больше - все остальные) - то все деньги, в любом случае, получит четвертый по старшинству(Полумладший) - "Кок"...
Если, действително, все пираты оч-умные, и старшие понимают, что на следущей дележке кормить рыб пойдут они(а на последней младший) - то в прежнем составе...

Расписывать влом...

← →
Bless (2003-12-19 14:24) [44]

Соответственно 4-ый голосует "за" и старший с 2-мя голосами против 2-х выигрывает

← →
han_malign (2003-12-19 14:34) [45]

Главный, Недовольный,Довольный

0- 500-500- 0- 0 / 0-501- 499- 0- 0
0- 500-500- 0 / 0-501- 499- 0
0- 500- 0-500 / 0-501- 0- 499
0- 0- 500-500 / 0- 0-501- 499
0- меньше 1000-любое

← →
Vint (2003-12-19 14:36) [46]

>Bless (19.12.03 14:15) [42]
Невнимательно читал. Это следует из того, что 4-ому будет достаточно и 1 монеты, потому что если их останется 3, он не получит вообще ничего. А 1>ничего.

это кто сказал? где логика то?
почему он не получит ничего?
допустим я нулевый и сейчас ничего не получил, и я ему говорю что он получит 333 монеты?

или мне нельзя так говорить? я должен делить так как ты решил что ли? :)))

почитай еше раз Igorek © (18.12.03 13:09) что ли!

← →
Vlad Oshin (2003-12-19 14:43) [47]

Если ясен порядок смены главного, тогда все понятно

← →
Bless (2003-12-19 14:59) [48]

>это кто сказал? где логика то?
>почему он не получит ничего?

Дочитай мой пост [40] до конца ВНИМАТЕЛЬНО.
Он ничего не получит, потому что когда их остается трое,
то будет расклад
...-...-999-!0!-1.
1 2 3 4 5
Я исхожу из того, что тот кто делит, хочет остаться в живых и взять себе побольше.
А 0 там будет хотя бы потому, что 3-ий добъется приемлимого себе результата ничего не давая 4-му, достаточно дать 5-му.
А если он даст 1-у монету 4-му, а не даст 5-му, то и 4-ый и 5-ый проголосуют против него. 5- потому что ему ничего не дали.
4 - потому что убрав старшего(3-го) он на правах нового старшего заберет все себе.

Я ответил на твой вопрос?

← →
Igorek (2003-12-19 15:00) [49]

> Определим как будет голосовать пират на любой стадии:
> если ему предложено меньше, чем он получит на следующей
> стадии (если выкинуть старшего) то "против" иначе "за".
> Они же беспринципные (см. условие) и не голосуют "против"
> только для того что-бы увидеть как товарищ кормит рыбок.
Обьясняю попу-лярно ;-)

Пронумеруем пиратов по старшинству от 1 до 5 (1 самый старший).

Пусть 5 пират остался один. Ясно что он забирает 1000.
> 1 : 1000 :

Пусть их два (4 и 5): тогда 4 должен все отдать 5-му или тот проголосует "против" и 4 пойдет за борт
> 2 : 0/1000 :+

Пусть их три (3,4,5): 3 берет все себе; 4 голосует "за", поскольку все равно получит 0 когда их станет двое; 5 голосует "против", надеясь получить 1000 когда их станет двое; равное колл. - 3 голосует за себя
> 3 : 1000/0/0 :+-

Пусть их четверо (2,3,4,5): 2 берет все себе; 3 голосует против (когда их будет трое он получит все); 4 и 5 голосуют "за", так как все равно ничего не получат когда их станет трое
> 4 : 1000/0/0/0 :-++

Аналогично, когда их пятеро: 2 - "против" (надеясь получить все когда их станет четверо); 3,4,5 - "за" (все равно нифига не получат когда их станет четверо)
> 5 : 1000/0/0/0/0 :-+++

Где изьян в логике???

З.Ы. Ессно сговор исключен.

← →
Bless (2003-12-19 15:09) [50]

Igorek © (19.12.03 15:00) [49]>
>Где изьян в логике???

Нигде. Если исходить из того, что тот кто делит, не голосует. Но в условии этого не сказано.

← →
Кабан (2003-12-19 15:13) [51]

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

← →
Vint (2003-12-19 15:18) [52]

>Bless (19.12.03 14:59) [48]

Он ничего не получит, потому что когда их остается трое,
то будет расклад
...-...-999-!0!-1.
1 2 3 4 5
Я исхожу из того, что тот кто делит, хочет остаться в живых и взять себе побольше.

а из чего исходит 4 не прелагая убить 3 и поделить с 5 эту 1000 по 500 монет? выигрывают то в этом случае оба? ты не подумал?

← →
Bless (2003-12-19 15:18) [53]

Упс. Я как-то прохлопал, что у тебя делящий тоже голосует.
Тогда вот тебе хотя бы такой изъян.

>Пусть их два (4 и 5): тогда 4 должен все отдать 5-му или тот
>проголосует "против" и 4 пойдет за борт

У 4-го решающий голос. Поэтому он за борт не пойдет. А следовательно, заберет все себе.

← →
Bless (2003-12-19 15:23) [54]

Vint © (19.12.03 15:18) [52]
>а из чего исходит 4 не прелагая убить 3 и поделить с 5 эту 1000
>по 500 монет? выигрывают то в этом случае оба? ты не подумал?

Подумал. Но если допустить возможность "договориться", то задача не имеет смысла, потому что возможен любой вариант. Например, четверо предложат старшему поделить 0-250-250-250-250, а они взамен не выбросят его за борт. Или любой другой. Поэтому я исхожу из предположения, что сговора нет

← →
Vint (2003-12-19 15:32) [55]

>Bless (19.12.03 15:23) [54]

это не сговор а логика!
а сговор это заведомый обман одного из пиратов, естейственно эти случаи не рассматриваются...

← →
chs2r (2003-12-19 15:34) [56]

> Пусть их три (3,4,5): 3 берет все себе; 4 голосует "за",
> поскольку все равно получит 0 когда их станет двое;

вот изъян
почему ты уверен что 4 голосует ЗА ему все равно, может и против

← →
Vint (2003-12-19 15:37) [57]

0-250-250-250-250
не рассматривается т.к. надо исходить по условию задачи из макимально возможного куша!

а так можно просто всем раздать по 200 монет и никто не оспорит это решение.

но если исходить из того, чтобы доля имела максимум из возможного и при этом все были живы, то только так:
0-500-500-0-0

← →
Igorek (2003-12-19 15:42) [58]

> Bless (19.12.03 15:09) [50]
> Igorek © (19.12.03 15:00) [49]>
> >Где изьян в логике???
>
> Нигде. Если исходить из того, что тот кто делит, не голосует.
> Но в условии этого не сказано.

Из условия:
> Если большинство коллег° согласно, на том и останавливаются.

Сам же себе пират не коллега. :-)))

> Кабан (19.12.03 15:13) [51]
> кроме того, используется предположение, что если пират ничего
> не получит, он голосует за, что спорно, т.к. пираты хотя
> и образованные, но очень беспринципные люди

А почему мы должны предполагать, что он будет голосовать "против"? Может он тогда монетку будет бросать? Формализовать "беспринципность" тут трудно. Согласен, неоднозначность в условии.

Кстати при моем решении не играет роли что значит "кормить рыбок" - за борт или просто устранить пирата от дальнейших голосований и он идет рыбкам хлеб крошить. Впрочем если пират остается в живих, то где гарантия, что он просто не пропускает голосование, а в следующем принимает участие как младший (или как старший); так еще больше неоднозначностей, так что лучше предположить, что он идет за борт.

← →
Кабан (2003-12-19 15:48) [59]

"Кормить рыб" - это устойчивое выражение, никакой двухзначности сдесь нет.

выражение "Если большинство коллег согласно, на том и останавливаются" двухсмысленно
вот допустим мы с вами коллеги по работе, я вам коллега и вы мне, поэтому оно вовсе не означает, что старший не учавствует в голосовании

← →
BLess (2003-12-19 15:50) [60]

>это не сговор а логика!

Ну, ну.
>а сговор это заведомый обман одного из пиратов

А это тогда что

>а из чего исходит 4 не прелагая убить 3 и поделить с 5 эту 1000
>по 500 монет? выигрывают то в этом случае оба?

С чего это вдруг 4 будет делиться с 5-ым, если они не сговаривались

>надо исходить по условию задачи из макимально возможного куша!

Вот именно. А ты сам себе противоречишь. Какой 4-му тогда резон делиться с 5-ым, если можно забрать все себе.

← →
Igorek (2003-12-19 15:50) [61]

> Кабан (19.12.03 15:48) [59]
>
> выражение "Если большинство коллег согласно, на том и останавливаются"
> двухсмысленно
> вот допустим мы с вами коллеги по работе, я вам коллега
> и вы мне, поэтому оно вовсе не означает, что старший не
> учавствует в голосовании

Имеется ввиду коллег старшего. Тоже надо было написать. Ладно пора завязывать.

← →
Vint (2003-12-19 16:01) [62]

Какой 4-му тогда резон делиться с 5-ым, если можно забрать все себе.

такой, что сейчас у него 0! а будет 500!

где тут сговор то? сдесь логика!

вот если бы он сказал: "давай замочим 3 я возьму 900, а тебе дам 100, ведь сто это больше чем 1?" вот это сговор! и логики тут никакой...

← →
SergP (2003-12-19 16:08) [63]

> Vlad Oshin © (19.12.03 10:46) [33]
> Мое решение (по старшинству): 998 - 0 - 1 - 0 - 1
>
> не понял, честно говоря
> все 4 будут против такого дележа и замочат старшего

Все против не будут. Двое из остальных четырех будут за. Иначе если делить будет следующий, то они ваще них.. не получат. (

← →
BLess (2003-12-19 16:15) [64]

>такой, что сейчас у него 0! а будет 500!
>где тут сговор то? сдесь логика!

Ну конечно! Логика железная! А какой логикой руководствуется 5-ый, поддержав 4-го против 3-го? Ведь если они ни о чем не договаривались, то 4-ый, оставшись наедине с 5-ым, заберет себе все, а не 500. Ну и надо оно 5-му?

← →
Vint (2003-12-19 16:22) [65]

так именно потому, что 5 это не надо, 4 и отдаст ему 500 монет! что бы стало надо! :)
именно по этому 3 должен себе оставить 0 а все отдать 5 что бы 4 его не мог ни чем заинтерисовать, а сам 3 останиться жив!

ладно все ушел домой!
приятных всем выходных :)

Прикольная задача с РСДН - 5 пиратов Найти похожие ветки