Делёж по справедливости

[AlexeyP]

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

Однако ситуация становится критической, если золотоискателей трое и делить надо на три кучки. А весов по-прежнему нет.

Пишите способы справедливого раздела для случаев 3-х (а лучше - N) золотискателей!

 

[Michael]

Первый делит на N кучек.
Второй отдает ему одну из них, и делит остальное на N-1.
Tретий выхватывает кольт и с криками "Ваши рекурсии меня ещё школе достали" открывает пальбу.
Сдаюсь

 

[Богиня Прозерпина]

я бы пристрелила третьего. "третий -лишний". а потом и второго

 

[Alexd]

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

 

[Rzay]

Какое однообразие в ответах.

 

[Эльдар]

Единственное, что приходит в голову это делить на двоих до тех пор, пока не получится количество одинаковых частей частей, делящихся на 3 без остатка...
но 2,4,8,16,32,64,128,256,512,1024 не делятся на 3

 

[Aelia]

Алексей, а правильный ответ вообще существует? И единственный ли он?

 

[Michael]

Aelia, я же, вроде бы, ответил

 

[Michael]

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

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

Можно придумать ещё вариаций. По идее, всё это должно рекурсивно распространяться и на N, но, простите, лень думать

 

[Michael]

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

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

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

 

[Aelia]

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

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

 

[Michael]

Те двое, которые не нее претендуют.

 

[Michael]

Этот способ, конечно, достаточно тяжел, так как предполагает О(N^2) делений кучек, но интуитивно мне он представляется статисчески более справедливым чем предложенный мной сразу ([snapback]268543[/snapback]), хоть тот и О(N). Хотя, скорее всего, это и не так (задумался).