Московская математическая олимпиада, 1987, 7 класс #7

[Red_Herring]

http://olympiads.mccme.ru/mmo/prasolov/mo/c-print.ps писал(а):

Али-Баба и 40 разбойников решили разделить клад из 1987 золотых монет следующим обра- зом: первый разбойник делит весь клад на две части, затем второй разбойник делит одну из частей на две части и т.д. После 40-го деления первый разбойник выбирает наибольшую из частей, затем второй разбойник выбирает наибольшую из оставшихся частей и т.д. Последняя, 41-я часть достается Али-Бабе. Для каждого из 40 разбойников определить, какое наибольшее количество монет он может себе обеспечить при таком дележе независимо от действий других разбойников.

Непонятно: если тот кто раньше делит, раньше выбирает, то как последние могут себе хоть что-то гарантировать? На сайте http://www.problems.ru эта задача отсутствует, да и сам сайт в этот момент не соединяется

[rockclimber]

Red_Herring в сообщении #958596 писал(а):

как последние могут себе хоть что-то гарантировать?

"Хоть что-то" гарантируется тем, что клад делится на 41 часть, по числу разбойников. Или какой смысл вы вкладываете в это понятие?

[Red_Herring]

Если тот, кто раньше делит раньше выбирает, то он делит 1986:1 и та 1 достанется Али-Бабе

[grizzly]

Red_Herring в сообщении #958596 писал(а):

как последние могут себе хоть что-то гарантировать?

Некоторые последние, ясное дело, ничего не могут. Получат они по одной монете, как пить дать. Но первые, очевидно, могут. Авторы задачи могли считать, что решение для первых $k$ разбойников достаточно интересно, чтобы компенсировать тривиальность для последних $40-k$. Ну и само $k$ тоже ещё нужно найти. (Решать не пробовал.)

Red_Herring в сообщении #958617 писал(а):

Если тот, кто раньше делит раньше выбирает, то он делит 1986:1 и та 1 достанется Али-Бабе

Да, первый так и должен делать, если не боится :)

[gris]

А что, вполне логично
Если разбойников не 40, а один, то он обеспечивает себе 1986 монет.
Если их два, то первый может себе обеспечить 993 монеты, а второй при такой стратегии первого тоже обеспечивает себе 993. Но если первому лишь бы второму нагадить,то второй может обеспечить себе только 662 монеты.
Интересно, в задаче предполагается, что каждый будет стремиться к максимальному для себя гонорару?
Предположим, что разбойника три и стратегии наилучшие. Первый может обеспечить 663 монеты, второй 662, третий 661.
Если же первый и второй в сговоре, то Али-бабе и третьему достанется только по 1 монете.

[grizzly]

gris в сообщении #958619 писал(а):

Если же первый и второй в сговоре

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

[gris]

То есть против остальных, но не за себя?
Слова "независимо от остальных" относятся к только к последующим делёжкам, а не к предыдущим? Тогда получится, что клад разделится примерно $70+69+68+...+30+29$.
Кроме шефа, конечно. Ему 1 монетка. Но вот что будет потом?

[Dyaus_Pitar]

Если разбойника 3 и больше, то первому выгодно отделить минимальную часть, которую получит Али - баба, второму- также выгодно отделить минимальную часть, которую получит предпоследний участник, т.е. первым 20 участникам выгодно отделять по одной монете, чтоб получить себе как можно больше. Т.е. они определяют для последних 20 ти минимально гарантированную долю в одну монету. Далее деление оставшейся части переходит в руки 20 ти разбойников, для которых их доля уже определена. Оставшиеся 19 участников получат минимум по одной монете и максимум, если деление произойдёт равномерно, а для первого определится гарантированный минимум, состоящий из $\frac{1987-21}{20}=98$

[Shadow]

Dyaus_Pitar в сообщении #958651 писал(а):

Оставшиеся 19 участников получат минимум по одной монете

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

[grizzly]

gris в сообщении #958643 писал(а):

То есть против остальных, но не за себя?

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

[Dyaus_Pitar]

Shadow в сообщении #958678 писал(а):

Dyaus_Pitar в сообщении #958651 писал(а):

Оставшиеся 19 участников получат минимум по одной монете

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

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

[Shadow]

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

gris в сообщении #958643 писал(а):

$70+69+68+...+30+29$.
Кроме шефа, конечно. Ему 1 монетка.

Скорее всего так и есть.

[lyuk]

Думаю, что все, кроме первых двух, могут гарантировать себе только 1 монету (все будут отделять по 1 монете).

Первый, думаю, -- 50.

Второй -- примерно 25-26.

[Red_Herring]

Спасибо, кажется картина начинает проясняться. Итак, отделяют 40 разбойников. Если я—разбойник, то я не контролирую 39 моих заклятых друзей, и если каждый из них отделит по 1 монетке, то будет 39 кучек по одной монетке, и я получу её, сиротинушку, исключая случай, когда я—первый или второй.

Если я—#1, и эти мерзавцы, движимые лозунгами насчет всеобщего равенства, разделят 1986 примерно поровну, то будут кучки по 49 и по 50 монет, и мне достанется 50.

Если я—#2, то после того как мы с #1 отделили, оставшиеся 38 подонков, движимые исключительно ненавистью ко мне, начнут делить 2 меньшие кучки примерно поровну, т.е. на 40 частей (всего). Т.е. мне надо минимизировать размер самой большой из 3х этих кучек, а #1 хочет его максимизировать, для чего он делит 1987=993+994, а я делю 994 пополам, и тогда мне гарантировано 994:40 = 25 (т.к. будут кучки по 25 монет). Но если я разделю 994=993+1, то будет кучка на 26 монет, как бы они не исхитрялись.

Проверьте, пожалуйста!

[grizzly]

Red_Herring в сообщении #958730 писал(а):

Если я—#1, и эти мерзавцы, движимые лозунгами насчет всеобщего равенства, разделят 1986 примерно поровну, то будут кучки по 49 и по 50 монет, и мне достанется 50.

Я полностью согласен с общим пониманием задачи, но интеллект первого приближённого мы явно недооценили (иначе бы давно ему не сносить головы). Если он поделит 1987 примерно поровну, то сможет гарантированно получить свои кровные 53 и Али-Бабу лично он не обидит (может кто другой).

Ну и про судьбу остальных тоже нужно лучше позаботиться :)

-- 08.01.2015, 20:46 --

Прошу извинить. С общим пониманием я поспешил согласиться. Но за #1 уверен, что я прав.

-- 08.01.2015, 21:00 --

Точнее, поспешил с сомнениями в согласии. Согласен.
Только #2 нужно повнимательнее проследить. Он, конечно же, останется не беднее первого (более умные всегда стараются не высовываться).

Задачка оказалась неожиданно интересной.