Справедливый раздел

[Garryncha]

Это задачи из книги Я. Бизама, Д. Герцега "Многоцветная логика" (№№ 70-72), там же приведены их решения.
На мой взгляд, это интересные задачи, поэтому публикую их тут.
Я долго мучился, но так и не решил ни одной из них.:-))

Прежде всего заметим, что речь пойдёт о разделе на равные части (такой способ раздела справедлив не всегда).

Троим золотоискателям с Аляски, остановившимся в придорожной гостинице, требовалось разделить перед расставанием намытый ими золотой песок именно на 3 равные части: каждый из золотоискателей вложил в добычу золота ровно 1/3 общих затрат труда и поэтому не без основания претендовал на 1/3 золтого песка, считая, что такой раздел был бы справедливым.

Но каким образом разделить кучу песка на 3 равные части? Этого золотоискатели не знали. Весы имелись лишь на приёмном пункте, но до него было несколько дней пути. (Впрочем, тем, кто добрался бы до приёмного пункта, весы вряд ли понадобились бы, поскольку делить надо было бы уже не золотой песок, а доллары.) Делить золото "на глазок" никому не хотелось.

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

Но золотоискателей было не двое, а трое, вопрос о справедливом разделе золотого песка оставался неясным, и атмосфера постепенно начала накаляться. Наконец один из золотоискателей попытался найти выход из создавшегося неприятного положения.
— Джентельмены, обратился он к своим компаньонам, — чем, собственно говоря, так хорош справедливый раздел на двоих, когда один делит, а другой выбирает? Очевидно, тем, что каждому участнику раздела предоставляется возможность взять себе не меньше золотого песка, чем достанется другому. Тот, кто при таком способе раздела получит меньше золота, чем его партнёр, может винить только самого себя: если он делил, то ему следовало делить на равные части, а если он выбирал, то ему незачем было оставлять себе меньшую часть. Именно так и следует поступить с золотым песком.

— Верно говоришь, старина, — одобрил его выступление другой золотоискатель, — только я никак не возьму в толк, как же всё-таки нам надо поступить, чтобы каждый мог выбрать себе долю песка, не меньшую, чем у других?
Ответа на такой вопрос по существу не последовало: рецепта справедливого раздела на троих не знал никто.

Спросить совета, как надлежит действовать, чтобы соблюсти основное условие справедливого раздела (выделенное курсивом) — предоставить каждому возможность получить не менее 1/3 золотого песка (разумеется, если сам участник раздела не допустит какой-нибудь досадной оплошности) даже в том случае, если двоё партнёров вступят в тайный сговор и будут всячески стремится урезать долю третьего партнёра в свою пользу, — золотоискателям было не у кого.

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

Как разделить золотой песок?
(Способ раздела должен гарантировать, что каждому из золотоискателей достанется не менее 1/3 песка. Если всё же кому-нибудь достанется золотого песка больше, то причину несправедливости надлежит искать не в способе, которым делили песок.)

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

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

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

Comments

[Darta]

Может быть так: сначала двое первых вместе делят песок на 3 кучи. Приходит третий и выбирает себе одну. 2 остальные кучи смешивают и далее случай и разделом на 2х. Но в данном случае один из первых может вступить в сговор с третьим и сделать одну кучу больше. Не вполне уверена.

[Garryncha]

Darta, да, в таком случае 1-й или 2-й (тот, кто делит, а у другого-то, получается, пассивная роль) могут сговориться с 3-м.

[Darta]

Да... Должно быть какое-то последовательное деление на несколько куч и соединение... Мне так кажется. Надо думать.

[All Rights Ignored]

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

[Garryncha]

All Rights Ignored, а что потом? И почему этот способ раздела будет удовлетворять условиям?

[Darta]

All Rights Ignored, а потом, наверное, все смешивают и те двое опять делят по примеру на двоих. А вообще, - да, похоже на правду.

[Garryncha]

Darta, как раз если потом стандартная процедура делёжки на двоих, то это неправильное решение.
Допустим, 1-й честно делит пополам, а потом свою половину на 3 части по 1/6, а 2-й по сговору с 3-м делает две "очень маленькие" части и одну часть "почти 1/2", тогда 3-й заберёт 1/6 + "почти 1/2", а потом 2-й доберёт половину оставшегося, и у них вместе будет больше 2/3.

[All Rights Ignored]

Garryncha никакого "потом" нету. всё разделено на три части.

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

не понимаю за каким хером я это пишу, всё очевидно.

[Garryncha]

All Rights Ignored, сейчас понял, т.е. первые поделили всё пополам, а потом третий взял свои части, а им досталось то, что осталось.
Как будто всё правильно.:-) Делящий 1-й раз избегает сговора, если делает две кучи по 1/2, а потом в своей куче три части по 1/6 - и две из трёх частей его.
Выбирающий 1-й раз избегает сговора, выбирая большую кучу и деля её на три равные части.
Третий избегает сговора, т.к. в каждой из половин найдутся части, которые в сумме больше или равны 1/3, а он выбирает первым в итоге.
Поздравляю!:-)
А решите эту задачу для четырёх человек?

[All Rights Ignored]

Garryncha решу, но попозже. сейчас надо уйти (

[Garryncha]

All Rights Ignored, здорово!:-)

[Diami]

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

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

[Garryncha]

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

Если Коля согласился быть третьим, он уже не может хотеть ту кучу, которую возьмёт Вася, чтобы дальше делить.

[Diami]

Garryncha в итоге получается, что вася делит на две части,
а потом "свою" часть еще на три, и петя делит тоже на три.

А Коля в самом конце пришел и выбрал себе по кучке.
Да, это логично донельзя


А если четыре человека?
Все равно Коля должен делить, Петя выбирать.
А Вася и Галя должны в самом конце участвовать.

[Garryncha]

в итоге получается, что вася делит на две части,
а потом "свою" часть еще на три, и петя делит тоже на три.

А Коля в самом конце пришел и выбрал себе по кучке.
Да, это логично донельзя

Да, так и получается.:-)

А если четыре человека?
Все равно Коля должен делить, Петя выбирать.
А Вася и Галя должны в самом конце участвовать.

А я не знаю, как переделать это решение для 4-х человек, дерзайте.:-)

[All Rights Ignored]

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

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

[Garryncha]

All Rights Ignored, я не верю, что всё так просто обобщается.:-)
Задачку сейчас поищу и подам.:-)
В книге приведено другое решение для трёх и для четырёх, по-моему, тоже, и вот те решения как раз не обобщаются на случай n человек, для n там придуман свой способ. Так что, надо, надо убедиться в том, что это решение обобщается.:-)

[All Rights Ignored]

Garryncha может в момент скуки и распишу решение на 4-х...

хотя при делении больше чем на троих проще лишних завалить )) и шериф не помог бы... шериф один а тут больше троих и ЗОЛОТО! ))

[Garryncha]

All Rights Ignored, когда угодно пишите решение, это же добровольно.:-)

[Гость]

Сразу скажу, что это не мое решение (но мое объяснение решения). Успех решения задачи для двух старателей в том, что если первый разделил не поровну, то второй может ЗАСТАВИТЬ ПЕРВОГО взять меньшую часть. Фактически, ВТОРОЙ РЕШАЕТ КАКАЯ КУЧА ДОСТАНЕТСЯ ПЕРВОМУ. Если взглянуть на задачу о двух старателях под этим углом, сразу понятно как обобщить алгоритм "на троих" . Первый делит на три (как ему кажется) равные части. При этом он автоматически соглашается на любую из них (так как по его мнению они равны). Второй выбирает меньшую (на его взгляд) кучу из трех. ЭТА КУЧА ДОСТАНЕТСЯ ПЕРВОМУ. (Помним, что первый согласен на любую из трех и не может быть в претензии). Если третий согласен с со вторым, то эта куча (которую выбрали второй и третий) уходит к первому. Оставшееся золото второй и третий делят как в задаче о двух старателях. Если третий не соглсен со вторым, что данная куча меньшая, ТО ОН БЕРЕТ ЕЕ СЕБЕ. Очень важный момент. Если третьего подвел глазомер и куча все таки оказалась самой маленькой, то ему придется винить только себя. Если второй попытался схитрить и указать на не самую маленькую кучу, третий может его наказать, взяв кучу себе. Оставшиеся двое делят оставшееся золото как в задаче о двух старателях

[Garryncha]

Гость, извините, у меня уже энтузиазма нет решение проверять. Могу к той же книжке отослать, она есть в интернете, а в ней решение — можно сверить с ним. Или ещё кто здесь подскажет.

[Diami]

Гость, не подходит, Мб третий считает эту кучку не самой меньшей, а средней, в этом случае нечестно, если он ее заберет, ведь это будет с его точки зрения не треть, а Мб меньше.

[Гость]

Продать кучу и разделить на троих деньги

[Гость]

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

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

для четверых и более алгоритм аналогичный

[Гость]

вся эта тема для лохов = я всегда останусь в +, делю или нет )) 1.2.или 3-й

[Гость]

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