Помогите решить задачу

← →
Artem (2012-08-12 21:47) [0]

Алгоритмическая.

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

Теперь их трое. Предложить алгоритм "справедливого деления" для троих.
(Алгоритм, естественно, должен исключать возможность сговора двух участников против третьего.)

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

← →
Медвежонок Пятачок © (2012-08-12 21:57) [1]

Для троих:

Первый старатель делит золото на три кучи.
Двое остальных старателей отдают первому одну из них.
Затем две оставшиеся кучи смешиваются и делятся по алгоритму "для двоих"

← →
Медвежонок Пятачок © (2012-08-12 22:00) [2]

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

← →
sniknik © (2012-08-12 22:03) [3]

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

← →
Artem (2012-08-12 22:05) [4]

Медвежонок Пятачок © (12.08.12 21:57) [1]
Вот спасибо большое. Ваш должник...

← →
sniknik © (2012-08-12 22:09) [5]

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

← →
Давайте будем жрать! (2012-08-12 22:18) [6]

> делят на любое количество кучек, затем один отворачивается,
> а кто-то указывает на кучку и спрашивает его - "это кому?
> ".
Деление будет честным только если деливший лишён азарта. ;-)

← →
DVM © (2012-08-12 22:45) [7]

Среди золотоискателей евреи были?

← →
boriskb © (2012-08-13 00:17) [8]

> Среди золотоискателей евреи были?

:))
Вспомнилось -
Если бы занятия спортом были полезными, то на каждом турнике висело бы по три еврея.

← →
Dimka Maslov © (2012-08-13 11:13) [9]

Один из золотоискателей берёт кольт и через несколько выстрелов честно забирает всё золото себе.

← →
Думкин © (2012-08-13 11:15) [10]

> Один из золотоискателей берёт кольт и через несколько выстрелов
> честно забирает всё золото себе.

Это не дальновидно. Потом еще надо на большую землю выбираться. Без пары коров тяжко ему будет.

← →
Petr V. Abramov © (2012-08-13 11:21) [11]

> Первый старатель делит золото на три кучи.
> Двое остальных старателей отдают первому одну из них.
> Затем две оставшиеся кучи смешиваются и делятся по алгоритму
> "для двоих"

первый делит пополам, дальше по алгоритму для двоих :)

← →
Inovet © (2012-08-13 12:40) [12]

> [9] Dimka Maslov © (13.08.12 11:13)
> Один из золотоискателей берёт кольт

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

← →
БарЛог © (2012-08-13 12:59) [13]

> Думкин © (13.08.12 11:15) [10]
> Это не дальновидно. Потом еще надо на большую землю выбираться.

Достаточно под музыку ускакать в закат.

← →
Думкин © (2012-08-13 13:08) [14]

> БарЛог © (13.08.12 12:59) [13]

Это у них, там, за границей, в джунглях капитализма.

← →
AV © (2012-08-13 13:43) [15]

> Первый старатель делит золото на три кучи.
> Двое остальных старателей отдают первому одну из них.

Старатели - Сi
Кучки - Кi

Пусть
С1 поделил на К1 К2 К3
С2 говорит что К2 минимальна
С3 говорит что К3 минимальна
Какую кучку получит С1?

← →
AV © (2012-08-13 13:59) [16]

Так надо

repeat

:Start
1) С1 берет столько, сколько считает справедливым в кучку К0 и пытается стать ее владельцем.

2)
repeat
если кто-то из оставшихся считает, что это несправедливо, и там больше, то он отсыпает из K0 столько, на сколько считает что там больше. Таким образом, он становится новым владельцем К0.
until никто не оспаривает владельца К0.

3)
владелец К0 выбывает, множество С усекается на владелеца К0
goto start.

until множество С пустое :)

← →
AV © (2012-08-13 14:00) [17]

не, хватит так

:Start
1) С1 берет столько, сколько считает справедливым в кучку К0 и пытается стать ее владельцем.

2)
repeat
если кто-то из оставшихся считает, что это несправедливо, и там больше, то он отсыпает из K0 столько, на сколько считает что там больше. Таким образом, он становится новым владельцем К0.
until никто не оспаривает владельца К0.

3)
владелец К0 выбывает, множество С усекается на владелеца К0
goto start.

← →
AV © (2012-08-13 14:09) [18]

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

по логике оно и так так будет, но могут затянуть до бесконечности, убавляя по песчинке :)

← →
БарЛог © (2012-08-13 14:12) [19]

AV © (13.08.12 14:09) [18]

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

← →
AV © (2012-08-13 14:16) [20]

итого, если по простому

Любой берет сколько хочет. Если кто-то согласен на меньшее, он берет меньше, если никто не согласен на еще меньше.

← →
AV © (2012-08-13 14:17) [21]

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

А если группа из 2n человек считает по n голосов в пользу каждой кучки?

← →
БарЛог © (2012-08-13 14:25) [22]

AV © (13.08.12 14:17) [21]

+ Нечётное число людей пополам не поделится :)
Затупил.

← →
AV © (2012-08-13 14:26) [23]

> > Можно пополам разбивать кучки (и людей) на каждой итерации.
>
> > И решать группой, какая кучка на группу достанется.
>
> А если группа из 2n человек считает по n голосов в пользу
> каждой кучки?
> <Цитата>
>
>

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

Считаю, что решение

> Любой берет сколько хочет. Если кто-то согласен на меньшее,
> он берет меньше, если никто не согласен на еще меньше.

самое справедливое для каждого.

← →
Artem (2012-08-13 18:22) [24]

Значит всё-таки не правильно решена задача, как же она всё таки решается???

← →
Медвежонок Пятачок © (2012-08-13 18:38) [25]

Пусть
С1 поделил на К1 К2 К3
С2 говорит что К2 минимальна
С3 говорит что К3 минимальна
Какую кучку получит С1?

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

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

← →
Медвежонок Пятачок © (2012-08-13 18:58) [26]

В общем универсальный алгоритм такой:

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

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

← →
Медвежонок Пятачок © (2012-08-13 19:06) [27]

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

← →
Компромисс © (2012-08-13 19:08) [28]

Медвежонок Пятачок © (13.08.12 18:58) [26]

Не сработает. 3 человека. Первым раскладывает A, вторым B. A договорился с B кинуть C, раскладывает 2 огромные кучи и одну малюсенькую. B выбирает малюсенькую. В итоге A получает огромную кучу, которой потом делится с B

про сговоры есть оговорка в условии.
никто против никого не дружит

← →
Artem (2012-08-13 20:24) [30]

← →
Компромисс (забыл пароль) (2012-08-13 21:04) [31]

Медвежонок Пятачок © (13.08.12 19:09) [29]

Напротив, сказано, чтобы алгоритм защищал от сговоров. Во всяком случае, так я понимаю "Алгоритм, естественно, должен исключать возможность сговора двух участников против третьего",
Происходит качественный переход ИМХО: как задачу трех тел невозможно решить в общем случае, несмотря на тривиальность задачи для двух тел, так и здесь: при троих уже нет уверенности хоть в чем-нибудь, даже в том, что каждый заитересован получить не меньше трети. Двое всегда обманут одного, демократия рулит :)

http://eruditor.ru/f/?z=12

все верно, только все наоборот.

в задаче сказано про алгоритм, исключающий возможность сговора.
он и приведен.

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

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

Происходит качественный переход ИМХО:

если он и происходит, то совсем не такой.
ситуация: двое решают кинуть третьего.

вопрос: нахрена им какой-то там алгоритм (который якобы существует) (и следуя которому они еще и обломаются кинуть этого третьего !)?

они просто поделят все золото между собой и все!

> Медвежонок Пятачок © (13.08.12 18:58) [26]
> В общем универсальный алгоритм такой: весь остаток золота
> делится на кучи по числу оставшихся старателей.тот, кто
> делил - выбирает свою долю последним.после чего все остальные
> снова сваливают "свои" доли в общую кучу и повторяют все
> сначала.если возникает спор по очередности выбора доли среди
> тех, кто не делил, то самый нетерпеливый становится делящим
> на следующей итерации

Здесь небольшой косячок - как определяется очередность выбора? Каждый захочет выбрать кучку первым. И снова появятся разногласия. А золотоискатели - народ суровый. Тайга глухая. Ночи темные. Мало ли чо..

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

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

да, так сходимость быстрее

все "кучки" сдаются государству :)
там честно поделят - хоть на N, хоть на всю страну

Здесь небольшой косячок - как определяется очередность выбора?

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

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

Да, верно, это я недогнал сначала. И в принципе, предложил то же самое.

← →
Компромисс (забыл пароль) (2012-08-14 19:29) [40]

> palva © (13.08.12 21:09) [32]
> http://eruditor.ru/f/?z=12

Спасибо. Никакого качественного перехода, зря я философствовать начал...

Помогите решить задачу Найти похожие ветки