[Aleks_CNN]

Обсуждение задачки « 100 олигархов»
Специально для НеКТо, ну, и для остальных товарищей тоже, конечно

В совет директоров компании входят 100 олигархов, которые отличаются логичностью мышления и крайней жадностью. Среди олигархов есть линейная иерархия от самого главного до самого младшего. Компания получила прибыль в 100 тугриков. Тугрики делятся следующим образом. Главный олигарх предлагает, как делить прибыль, потом каждый голосует "за" или "против". Если по крайней мере половина олигархов проголосует "за", они поделят тугрики так, как предложил главный. В противном случае главный олигарх исключается из совета директоров и лишается возможности получить прибыль, главным становится следующий по иерархии, а дележ продолжается по тому же принципу.

Вопрос: Как должен предложить разделить 100 тугриков главный олигарх, чтобы получить максимальную прибыль?

[Sgr]

Нужно как-то договорится с половиной олигархов (с 49, если Hero входит в эти 100).
"главным становится следующий по иерархии" - это не зря включено в условия задачи. Сейчас придумать ничего не могу, но 2-ого в иерархии нужно непременно побрить с тугриками. Как минимум не имеет смысла давать ему тугриков.

[pokerdenis]

во во я каждый день это слышу в оффлайне. только за финалку сядешь.- давай делить сраные тугрики!!!

[BlueberryM]

Вообще надо главному олигарху самоустраниться от дележки, иначе договориться все равно не возможно. Если именно цель получение максимального количества денег.
Задача на выживание, главный олигарх катает DoNы)))

[z_poker]

Никак. У первого олигарха шанс получить хоть какие-то деньги равен нулю.

[rugambler]

Сообщение от Aleks_CNN

Вопрос: Как должен предложить разделить 100 тугриков главный олигарх, чтобы получить максимальную прибыль?

Думаю, что ответ звучит как-то так:
взять 51 себе, остальные 49 разделить между олигархами со 2-ого по 50-го. Изначально и 2-й и остальные до 99-го понимают, что им тоже ничего не светит, т.к. последующие будут голосовать против них всегда, а значит надо соглашаться хотя бы на 1.

Update: Даже еще лучше, взять 99 себе, а оставшийся предложить разыграть между 2-м и 50-м (или даже между всеми, чтобы кворум был ).

P.S. Если можно делить тугрик на части, то можно по одному центу выдать, а себе забрать 99.5. Если же вылет из совета директоров несет какие-то дополнительные траблы, то просто все себе забрать. Должны подтвердить все, кроме последнего

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

[Guiscard]

Парни, это известная логическая задача недавно обсуждалась на ДТ. Почитайте. Даже тема в арбитраже была - аж бабки требовали по-моему.
А вообще-то, воспользуйтесь поисковиком, все уже давно решено.

P.S. Только обычно она про приратов - эта задача. Суть та же.

[TastyAA]

договориться с самой слабой половиной, которым вобще ничего не светило бы.

[RabbitRoger]

Какая олигарху разница с какой половиной договариваться?
Как раз таки наоборот, выходит что самой слабой половине и светит, а точнее его концовке. Ведь каждый раз когда олигарх выбывает, денег на душу становится больше. Соответственно есть смысл постоянно не соглашаться с главным (последующим) олигархом.
Однако, можно рассказать об этом другим олигархам, что если постоянно отказываться, то деньги получат только 2 олигарха из самой концовки. Другое дело, не пойдет ли каждый на обман, что бы предложить другим олигархам бОльшую сумму, ведь более старшего олигарха можно списать, и предложить всем остальным тоже самое, только денег уже будет больше.

Раздача действительно интересная, и зачем идти читать ответ на дт, если интереснее самому подумать. Кому надо, тот и в гугле ответ найдет.

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

PS: если кто будет писать ответ, вставляйте его пожалуйста в спойлер, ТС потом подпишется под спойлером, верный ответ или нет. (Ну или не ТС, а тот кто точно знает верный ответ)

[$$magnet$$]

верный ответ такой:

Скрытый текст:

при таких правилах дележки (при условии, что голосование тайное и возможность сговора исключена) главный олигарх может взять себе 51 тугрик, а остальные 49 раздать олигархам под нечетными номерами, т.е. 3, 5, 7 и т.д. заканчивая 99-ым. и ему за это ничего не будет.

нигде не подсматривал и не гуглил. свои размышления и выкладки готов привести, если кому приспичит. щас просто с телефона пишу - пальцы устают

[Skuratoff]

Как по мне, задача имеет множество решений.

Скрытый текст:

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

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

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

$$magnet$$, твое решение, конечно, тоже правильно, но почему ты считаешь, что именно олигархам под нечетными номерами?

[$$magnet$$]

Сообщение от Skuratoff

Как по мне, задача имеет множество решений.

Скрытый текст:

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

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

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

$$magnet$$, твое решение, конечно, тоже правильно, но почему ты считаешь, что именно олигархам под нечетными номерами?

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

[Vitovt]

$$magnet$$
Отпиши, пожалуйста, решение под спойлер.

[$$magnet$$]

Сообщение от Vitovt

$$magnet$$
Отпиши, пожалуйста, решение под спойлер.

Ок.

Скрытый текст:

Важные допущения:
- голос главного олигарха (естественно "за") участвует в голосовании.
- голосование тайное и между олигархами нет сговора.
Задачу, как это часто бывает, можно решать с конца. Соображения следующие:
1. Последний (100-ый) олигарх понимает, что если пошла цепная реакция и все сливают всех подряд предшествующих кандидатов, в результате чего они остаются вдвоем с предпоследним, то 99-ый абсолютно законно забирает себе все сто пряников и 100-ого даже не спросит.
2. 99-ый понимает, что если цепочка дойдет до 98-ого (т.е. останется трое), то 98-ой заберет себе 99 долей и предложит 100-ому 1 долю, что конечно же больше, чем 0, поэтому 100-ый согласится за отсутствием альтернатив.
3. при этом 98-ой понимает, что 99-ый будет всегда голосовать против предложения 98-ого, т.к. если 98-ой вылетает, смотрите п.1.
4. если остается 4 олигарха, то 97-ой может забрать себе 99 долей и одну отдать кому-то из троих. вопрос, кому и сколько? естественно, болльше одной доли в одни руки платить никому не имеет смысла, т.к. тогда не наберется требуемое количество голосов "за".
98-ому не имеет смысла давать ничего, т.к. он всегда голосует против 97-ого из тех же соображений, что 99 долей (в случае вылета 97-ого) - это круто больше, чем 1, поэтому есть смысл рискнуть и отказаться от одной доли ради шанса получить 99 (жадность, ЁМАНА!!!). остается выбрать между 99-ым и 100-ым. и выбор должен должен пасть на 99-ого, т.к. 99-ый понимает, что 98-ой точно голосует против предложения 97-ого, и соответственно, если он голосует против и 100-ый голосует против, то это уже три голоса против, т.е. 97-ого сливают и 98-ой не даст ему ни гроша. 100-ому также по сути не все равно как голосовать при 4-х участниках, т.к. у него все еще будет 100%-ый шанс (против 50% сейчас) получить свою 1 долю (а больше он ни при каком раскладе не получит), когда они останутся втроем. поэтому из двоих кандидатов на последнюю долю наиболее заинтересован в ней 99-ый.
5. если остается 5 олигархов, аналогично 96-ой берет себе 98 долей и по одной отдает 98-ому (98-ой голосует так, чтобы 96-ого не слили) и 100-ому. 97-ой из-за жадности (шанс получить 98 долей) всегда голосует против 96-ого, а 99-ый будет голосовать против, т.к. свою одну долю он железно получит, если 96-ой вылетит.
6. и так далее по цепочке до самого первого главного олигарха. исходя из вышеописанных идей о том, что каждый следующий за главным олигарх голосует против предложения главного, а следующий за ним голосует за предложение главного, получаем, что олигархи под четными номерами поддерживают предложения каждого четного главного олигарха, а олигархи под нечетными - нечетного главного олигарха, и это будет для них наибольший шанс получить свою одну долю. при этом, когда главный олигарх под четным номером, олигархи под нечетными номерами (как умные и жадные одновременно) должны голосовать против его предложения, т.к. это дает шанс гарантированно (против примерно 50%-ого шанса когда главный под четным номером) получить свою 1 долю (когда сольют очередного четного) и призрачно увеличивает их матожидание в виде шанса на получение больше чем одной доли, если очередь быть главным каким-то невероятным образом дойдет до них. аналогично, олигархи под четными номерами сливают главных под нечетными.
И в итоге получаем, что олигарх номер 1 может оставить себе 51 долю, заплатив по одной каждому из оставшихся 49-ти под четными номерами.

как-то так.

[Skuratoff]

Скрытый текст:

Сообщение от $$magnet$$

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

В условиях сказано, что они все одинаково логичны, поэтому никто из них не должен рассчитывать на то, что очередь до него каким-то невероятным образом дойдет. Объясню свою мысль на примере. Чтобы было нагляднее, предположим, что олигархов всего четверо. Допустим я последний, 4-ый по списку. Я понимаю, что все остальные олигархи такого же склада мышления, что и я. По твоей логике, я должен отказаться, если мне самый главный предложит тугрик. А смыл? Ну откажусь я, ну нас останется трое, ну и мне опять предложат этот сранный тугрик. Какой в этом смысл, зачем тянуть время, если очередь до меня все равно не дойдет?

[$$magnet$$]

Сообщение от Skuratoff

Скрытый текст:

В условиях сказано, что они все одинаково логичны, поэтому никто из них не должен рассчитывать на то, что очередь до него каким-то невероятным образом дойдет. Объясню свою мысль на примере. Чтобы было нагляднее, предположим, что олигархов всего четверо. Допустим я последний, 4-ый по списку. Я понимаю, что все остальные олигархи такого же склада мышления, что и я. По твоей логике, я должен отказаться, если мне самый главный предложит тугрик. А смыл? Ну откажусь я, ну нас останется трое, ну и мне опять предложат этот сранный тугрик. Какой в этом смысл, зачем тянуть время, если очередь до меня все равно не дойдет?

я же вроде объяснил, почему так.

Скрытый текст:

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

[Skuratoff]

Сообщение от $$magnet$$

я же вроде объяснил, почему так.

Скрытый текст:

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

Снова здорова. Ты все слишком усложняешь и поэтому запутался.

Скрытый текст:

Да ты просто поставь себя на место последнего. Вот ты сидишь такой вообще даже и не размышляешь по поводу того, как разделит тугрики 1-ый и как ему выгоднее это сделать. Просто ждешь дележки, окда? И вот главный предлагает тебе один тугрик. И ты тут такой сразу думаешь, ага, один тугрик, могу ли я большего ожидать? Да нет, не могу. Ну вот зачем тебе отказываться, зачем? Чтобы просто посидеть чуть подольше и уйти с тем же тугриком.

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

[$$magnet$$]

Сообщение от Skuratoff

Снова здорова. Ты все слишком усложняешь и поэтому запутался.

Скрытый текст:

Да ты просто поставь себя на место последнего. Вот ты сидишь такой вообще даже и не размышляешь по поводу того, как разделит тугрики 1-ый и как ему выгоднее это сделать. Просто ждешь дележки, окда? И вот главный предлагает тебе один тугрик. И ты тут такой сразу думаешь, ага, один тугрик, могу ли я большего ожидать? Да нет, не могу. Ну вот зачем тебе отказываться, зачем? Чтобы просто посидеть чуть подольше и уйти с тем же тугриком.

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

ну ты прикидываешься, што ле?

Скрытый текст:

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

[Skuratoff]

Сообщение от $$magnet$$

ну ты прикидываешься, што ле?

Скрытый текст:

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

По-моему, это ты прикидываешься.

Скрытый текст:

Я прекрасно понимаю, кто принимает решение, как делить. Но и соглашаются ведь олигархи не в слепую, они сначала смотрят, как главный делит прибыль. Я веду к тому, что если 1-ый предложит тугрик 4-ому, это тоже 100% вариант, также как и предложить этот тугрик 3-ему. Как ты этого не можешь понять? Какая может быть мотивация у олигархов отказаться от 1-го тугрика, только две (уже какой раз пишу): либо он ожидает, что ему кто-то предложит больше 1-го тугрика (это отпадает, это ты и сам писал), либо он ожидает, что до него дойдет очередь (если придерживаться условий задачи, это тоже отпадает для всех, кроме следующего сразу за главным). Теперь, чтобы не повторяться попытаюсь объяснить с другого конца. По твоей логике, если олигарх четный, то он должен предлагать тугрик олигархам под четными номерами, если - нечетный, то наоборот - под нечетными. На самом деле, ситуация никоим образом не меняется, например, для 53-го, будь то хоть 99 олигархов, хоть 98. Вот попробуй объясни, почему в первом случае главный может уверенно предлагать ему тугрик, а во втором случае это уже рискованно. Если до конца следовать твоей логике, то это в обоих случаях рискованно. 53-ий будет думать одинаково и там и там, точно как ты писал: "...у меня все еще будет 100%-ый шанс получить свою 1 долю", "... и призрачно увеличивает мое матожидание в виде шанса на получение больше чем одной доли, если очередь быть главным каким-то невероятным образом дойдет до меня". Получается в обоих случаях это риск (по твоей логике, естественно).

[N0EL]

магнет прав.