Проект основателей компании «Ваш репетитор»
ERUDITOR.RU

12. Дележ добычи

Двое разбойников после удачного ограбления делят добычу — золотой песок. Весов и других приспособлений у них нет. Друг другу они не доверяют. Как разделить добычу между двумя разбойниками, чтобы никто из них не считал себя обделённым?
2006-11-23

Обсуждение


Задачи :: Дележ добычи
↓↓ 0 ↑↑   eruditor.ru (92 / 197)   26 янв 2007 17:40   »»


Один делит на две части, а второй выбирает
↓↓ 0 ↑↑   Germes (12 / 8)   05 мар 2007 11:09   «« #2 »»   Ответить


Germes - Гениально!!!
↓↓ 0 ↑↑   Allana (-1 / 7)   09 мар 2007 22:15   «« #3 »»   Ответить


А что если их трое?
↓↓ 0 ↑↑   eruditor (86 / 438)   09 мар 2007 23:43   «« #4 »»   Ответить


Один делит на две части, а второй выбирает и делит на две части, а третий выбирает!
↓↓ 0 ↑↑   Super (0 / 19)   19 мар 2007 08:43   «« #5 »»   Ответить


Что второй делит на 2 части?
↓↓ 0 ↑↑   KASKADER (4 / 19)   19 мар 2007 23:06   «« #6 »»   Ответить


Если их трое и т.д.
Сначала один делит на две части, второй выбирает одну вторую. Потом оба делят свои доли каждый на три части. Третий выбирает у каждого из остальных их одну третью. Такое же решение для произвольного K+1. Когда среди K-народу разделено, каждый из них делит на K+1 частей, а K+1-й выбирает у каждого по одной части.
↓↓ 0 ↑↑   DimaB (0 / 1)   20 мар 2007 18:00   «« #7 »»   Ответить


Увы, в общем случае алгоритм не сработает.
Дело в том, что третий имеет право захотеть взять 2 порции только у одного из двух, разделивших золото на 6 частей.
↓↓ 0 ↑↑   Валерий (10 / 25)   15 фев 2017 21:27   «« #48 »»   Ответить


Зачем так сложно???
Их K человек. Тогда первый делит на К частей, а остальные по очереди выбирают. Если первый не дурак, то все кучи будут разными!
↓↓ 0 ↑↑   Paha (0 / 62)   10 май 2007 16:35   «« #8 »»   Ответить


Пардон, равными
↓↓ 0 ↑↑   Paha (0 / 62)   10 май 2007 16:35   «« #9 »»   Ответить


Мдаааа
Я думаю надо опустить его(золото) в воду и вычислить.
↓↓ 0 ↑↑   MOO123 (0 / 7)   16 май 2007 15:07   «« #10 »»   Ответить


И что?
измерительных инструментов нет никаких. Что вы собираетесь вычислять?
↓↓ 0 ↑↑   eruditor (86 / 438)   16 май 2007 19:13   «« #11 »»   Ответить


Криминал.
В таких соблазнительных ситуациях,верное решение приходит самому сильному и жадному.Итог такой,всё достанится самому коварному из трёх разбойников.
↓↓ 0 ↑↑   Землянин (0 / 5)   18 май 2007 14:49   «« #12 »»   Ответить


Криминал.
В таких соблазнительных ситуациях,верное решение приходит самому сильному и жадному.Итог такой,всё достанится самому коварному из трёх разбойников.
↓↓ 0 ↑↑   Землянин (0 / 5)   18 май 2007 14:52   «« #13 »»   Ответить


"Как разделить добычу между двумя разбойниками, чтобы никто из них не считал себя обделённым?"
а откуда взялся третий разбойник-то, я так и не понял!!!:)))))))
↓↓ 0 ↑↑   puissance (0 / 5)   29 май 2007 22:48   «« #14 »»   Ответить


А если так.
Интригу внёс эрудит(кириллица).
↓↓ 0 ↑↑   Землянин (0 / 5)   30 май 2007 18:57   «« #15 »»   Ответить


Germesu
наверное ты тот, который делит??? :-)
↓↓ 0 ↑↑   Biatris (0 / 20)   31 май 2007 17:10   «« #16 »»   Ответить


Криминалу
Ты суппер
↓↓ 0 ↑↑   Biatris (0 / 20)   31 май 2007 17:13   «« #17 »»   Ответить


Думаю так.
Точно до миллиметра не поделить никак, но можно найти сосуд и приблизительно разделить на пополам.
↓↓ 0 ↑↑   Biatris (0 / 20)   31 май 2007 17:17   «« #18 »»   Ответить


!!!
Первый делит на две части, Второй делит эти две части еще раз по полам. Получается четыре. Третий делит четвертую часть на три ровных, и добовляет к каждой куче.
↓↓ 0 ↑↑   MOO123 (0 / 7)   10 июн 2007 23:11   «« #19 »»   Ответить


Если разбойников трое, то ...
первый разбойник на глаз отделяет 1/3. Далее он предлагает ее кому-то из оставшихся разбойников. Если никто не хочет ее брать, он берет ее сам. Второй и третий делят остальное золото по уже известному сценарию, т.е. один делит, а второй выбирает.
↓↓ 0 ↑↑   Zero (33 / 335)   13 июн 2007 12:41   «« #20 »»   Ответить


А если оба хотят..? Не так всё..
1-ый берет треть и предлагает, если оба считают её самой большой, то делят 2-й делит её попалам и предлагает выбрать 3-ему. (каждый считает что делит ровно). Затем оставшееся 1-й делит на 2 части и предлагает выбать:
1 если оба сойдутся в выборе, то 1-й забирает часть, а 2-й или 3-й делит пополам и предлагает выбрать другу.
2 если не сойдутся, то 1-й забирает то что они поделили в самом начале, а этим отдает кто что желает.
↓↓ 0 ↑↑   Negative (0 / 8)   13 июн 2007 22:54   «« #21 »»   Ответить


Самое простое.
Первый делит на две части, второй выбирает одну из двух.
↓↓ 0 ↑↑   7777777 (0 / 130)   16 июн 2007 19:22   «« #22 »»   Ответить


Вы уже повторяетесь... Прочитайте первые посты!
↓↓ 0 ↑↑   Fender (0 / 15)   17 июн 2007 00:43   «« #23 »»   Ответить


что имеется под словами "других приспособлений нет"?
Мы можем делить песок некой емкостью, скажем "ложкой"?
↓↓ 0 ↑↑   igar (10 / 119)   25 июн 2007 20:44   «« #24 »»   Ответить


igar, ты что кретин?
↓↓ 0 ↑↑   Fender (0 / 15)   09 июл 2007 02:17   «« #25 »»   Ответить


1. Не нужно было думать 2 недели, чтоб задать вопрос, достойный кретина.
2. Вопрос адресовался умному человеку.
3. На сайте действительно можно обращаться к друг к другу: "кретин".
↓↓ 0 ↑↑   igar (10 / 119)   09 июл 2007 09:36   «« #26 »»   Ответить


вариант
Как разделить добычу между двумя разбойниками, чтобы никто из них не считал себя обделённым?
ответ был: Один делит на две части, а второй выбирает
↓↓ 0 ↑↑   KuZneC (0 / 5)   17 июл 2007 07:05   «« #27 »»   Ответить


Это понятно...
Гораздо интереснее, как разделить между тремя, чтоб каждый не считал себя обделенным..
↓↓ 0 ↑↑   igar (10 / 119)   17 июл 2007 11:56   «« #28 »»   Ответить


2 igar
1) Почитай первые посты, может найдешь ответ на свой вопрос...
2) >>>На сайте действительно можно обращаться к друг к другу: "кретин".
Порадовал...
↓↓ 0 ↑↑   Fender (0 / 15)   09 авг 2007 00:56   «« #29 »»   Ответить


"Жидкостные" (спиртовые) весы
Празднуя удачу разбойники заходят в ближайший кабак. Заказывают себе спиртное (на выбор).
Стаканы одинаковые, количество спиртного в каждом - тоже.
Далее они высыпают добытый золотой песок в стаканы так, чтобы уровень жидкости в обоих стаканах оставался равным.
После этой нехитрой процедуры, которая позволяет им честно поделить нечестно нажитое золото, спиртное используется по своему прямому назначению.
↓↓ 0 ↑↑   МАВР (5 / 19)   28 ноя 2007 09:06   «« #30 »»   Ответить


Для произвольного числа людей
Один из участников равномерно отсыпает золотой песок из общей кучи в отдельную, до тех пор, пока кто-нибудь (включая и его) не скажет СТОП. Первый кто скажет "СТОП" забирает себе отсыпанную часть. После этого он уходит и оставшаяся часть песка делится таким же образом между оставшимися людьми.
Обоснование:
Тот, кто сказал СТОП, уверен, что отсыпанная часть уже содержит песка не меньше, чем если бы ему досталось при точном дележе. Остальные (кто не сказал СТОП) уверены, соответственно, что отсыпанная часть содержит меньше песка, чем полагается каждому из них при точном дележе. А значит для них песка осталось не меньше, чем положено было остаться.
Процесс продолжается. В результате все довольны.
↓↓ 0 ↑↑   LerTush (0 / 21)   06 май 2008 16:26   «« #31 »»   Ответить


А если СТОП скажут несколько человек?
↓↓ 0 ↑↑   Валерий (10 / 25)   15 фев 2017 21:30   «« #49 »»   Ответить


2 LerTush
А что если никто не скажет "СТОП"?..
↓↓ 0 ↑↑   eruditor (86 / 438)   06 май 2008 20:36   «« #32 »»   Ответить


Для удобства, обозначим количество людей через k.
Если действовать из предположения, что каждый заинтересован в "большем выигрыше", такой ситуации не может быть. Если не вводить в рассмотрение формальную модель теории игр, словами это можно выразить так: чем больше песка отсыпает "ведущий", тем выше вероятность выкрика "стоп". Когда будет высыпан весь песок, выкрик произойдет с вероятностью 1.

"Размахивания руками":

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

Формально это звучит так: оптимальные стратегии игроков - говорить стоп, когда отсыпана ровно k-ая часть песка. (Затем их функция выгоды начинает убывать). Это можно доказать формально.
↓↓ 0 ↑↑   LerTush (0 / 21)   07 май 2008 14:46   «« #33 »»   Ответить


Оптимальные стратегии — звучит научно. Сомнительно, что наши игроки — разбойники изучали теорию игр. Скорее всего, когда будет высыпана справедливая порция песка, толпа кинется за этой порцией. Ведь "никому не выгодно пропускать момент, когда уже ..." :).
↓↓ 0 ↑↑   Валерий (10 / 25)   15 фев 2017 21:39   «« #50 »»   Ответить


В задаче не сказано, что все игроки играют по правильной стратегии.
↓↓ 0 ↑↑   eruditor (86 / 438)   18 май 2008 18:55   «« #34 »»   Ответить


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

Более того, если уж ответить-таки на конкретный вопрос:

Исходя из метода решения, если никто не говорит СТОП, значит никто не уверен, что его доля уже отсыпана. Ситуация, когда отсыпан весь песок, но все молчат (т.е. никто не уверен, что его доля отсыпана) - очевидно, абсурдна. Но если отвергнуть все естественные формальные предположения, типа: "Каждый стремится к максимизации выигрыша и минимизации проигрыша", "Разбойники договариваются и принимают правила", в конце концов, "Разбойники в достаточной мере разумны, чтобы совершать осмысленные действия (говорить стоп)" и прочие - доказать это нельзя. Но и сама задача становится бессмысленной и неинтересной ).

А кто выложил эту задачу? Может быть есть более интересное и оправданное решение? Времени прошло достаточно много, думаю всем было бы интересно услышать другие возможные подходы.
↓↓ 0 ↑↑   LerTush (0 / 21)   19 май 2008 22:22   «« #35 »»   Ответить


Разбойники поровну делили... где вы это видели?
Предлагаю поднять вот какой вопрос, так как это разбойники, то пусть они уверенны, что поровну поделить может тока он(разбойник), а все остальные делят криво, но он разбойник, из n кучек золота(разделенных другим) всегда найдёт самую большую, мол глаз-алмаз! Как надо делить, чтоб наибольшая часть разбойников считала, что ему досталось Больше золота!(остальные должны получить не менее, чем они считают им полагается)
↓↓ 0 ↑↑   Seryoga (0 / 8)   21 май 2008 22:02   «« #36 »»   Ответить


Первый делит на 3 кучи. Второй, выбирает меньшую, на его взгляд, отдает первому, оставшиеся 2 кучи смешивает, делит по ново. Третий выбирает из двух новых.
↓↓ 0 ↑↑   Наталья (0 / 1)   10 янв 2009 23:27   «« #37 »»   Ответить


А если меньшая на взгляд второго является большей на взгляд третьего?
↓↓ 0 ↑↑   Валерий (10 / 25)   15 фев 2017 21:42   «« #51 »»   Ответить


гы гы
почему бы не забрать у них весь песок? в итоге всем достанется ровно ничего, соответственно поровну.
↓↓ 0 ↑↑   kentakl9 (0 / 6)   25 фев 2009 18:12   «« #38 »»   Ответить


Germes, ты прав - мы всегда так с братом делим.(Не считая случаев когда просим: "О великий вождь Чингачгук, рассуди нас!").
LerTush, Отличный вариант.
↓↓ 0 ↑↑   Василий (4 / 38)   05 май 2009 14:12   «« #39 »»   Ответить


В дополнение к сказанному Землянином
Тогда можно вообще всем разбойникам покончить жизнь самоубийством, тогда тоже "никто из них не будет считать себя обделённым" (из условий). Никто вообще ничего считать не будет.
↓↓ 0 ↑↑   Василий (4 / 38)   31 май 2009 13:06   «« #40 »»   Ответить


Реальность!
Все методы деления хороши конечно, но только в теории. На практике как бы они не делили они (или хотя бы один из них) всё равно будут чувствовать себя обделённым потому, что будет сомневаться: "А правильный ли выбор я сделал?". Поэтому абсолютное решение этой задачи в такой формулировке может быть только одно. Один из них убивает другого и забирает всё себе! И заметьте ни убитый, ни живой не будут чувствовать себя обделёнными. :-))))
↓↓ 0 ↑↑   hadevit (0 / 7)   20 дек 2009 16:10   «« #41 »»   Ответить


Все о том же...
В принцеме, как первый вариант, но модифицировано... Первый делит на две кучки, второй выбирает одну, затем каждый делит свою кучку еще на две кучки, разбойники выбирают одну кучку у соперника. Тем самым каждый поучавствовал в дележке, и в выборе...
↓↓ 0 ↑↑   greyn (0 / 2)   10 дек 2010 08:56   «« #42 »»   Ответить


А правильного решения задачи, никто и не привёл...
"Один делит - другой выбирает" - всё ещё несправедливо. Никто из разбойников не захочет делить, зная что не сможет поделить точно, а значит - выбирающий получит больше. (А представьте, если ещё и руки у них дрожат? Тогда уж совсем очевидно, не подойдёт)
Таким образом, что бы каждому было справедливо, нужно:
1) Первый делит
2) Второй выбирает "свою" половинку
3) Второй делит обе половинки
4) Первый выбирает от каждой половинки (от своей и от половинки второго) по четверти.
Тогда получится, что каждый из них по разу поделит и по разу выберет. Это и будет справедливо.
↓↓ 0 ↑↑   SergeyASh (4 / 36)   12 дек 2010 23:51   «« #43 »»   Ответить


По существу этот подход тоже использует принцип "один делит, другой выбирает".
↓↓ 0 ↑↑   Валерий (10 / 25)   15 фев 2017 21:53   «« #52 »»   Ответить


По старинке
Делят вместе на то количество кучек, по количеству размойником, и поскольку выбрать могут все один мешок, полагаясь как говорилось выше на "глаз-алмаз" предлагаю метод жеребьевки, тут уж кому какой достанется, и вроде как по честному
↓↓ 0 ↑↑   Lasto4ka (0 / 8)   23 мар 2011 15:10   «« #44 »»   Ответить


Вижу для себя два решения:

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

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


2. Может у них нет весов, или других измерительных инструментов, но банальные кружки или ложки у них не могут не найтись. Ими и измерять, выбрав одну из них и насыпав в неё золота без горки, ровно до краёв. И утрамбовывать с помощью чего-то твёрдого. Причём, черпать должны по очереди и сыпать каждый себе. Если в конце золота останется меньше мерила, то использовать мерило поменьше, или делить по песчинкам. Если одному хватило золота на полное мерило, а другому — нет, забрать у первого полное мерило золота и дальше делить по песчинкам или взять мерило поменьше.



Есть ещё третье, несерьёзное: растворить золото в царской водке и отлить каждому поровну получившейся золотой бодяги :)
↓↓ 0 ↑↑   Гидон (0 / 19)   05 апр 2016 11:59   «« #45 »»   Ответить


Нужно субъективно перевешивать друг другу по килограмму, шляпе, сапогу, любому одинаковому мерилу. Остаток субъективно так же поделить. Тут вопрос в восприятии веса, а не точной оценки получается. ))
↓↓ 0 ↑↑   Евгений (0 / 18)   22 апр 2016 06:23   «« #46 »»   Ответить


пусть отсыпают друг другу если после раздела всех устраивает то ок если нет обмен кучами
↓↓ 0 ↑↑   Юрий (0 / 5)   16 окт 2016 19:09   «« #47 »»   Ответить


2 SergeiASh (#43)

В этом более сложном варианте обязанность деления просто перекочевала ко второму игроку, а право выбора — к первому. Первый вообще может выполнять деление как угодно. Например, в одной "половинке" 2%, а во второй-98%.
↓↓ 0 ↑↑   Валерий (10 / 25)   15 фев 2017 21:59   «« #53   Ответить



Ваше имя
Email
Текст ответа
© 2006-2017   Авторы