Как разделить добычу

[VadiMGP]

<!--QuoteBegin--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>Цитата </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->Ну в таком случае для N человек должно быть N кругов деления, и процесс точно сойдется.<!--QuoteEnd--></td></tr></table><div class='postcolor'><!--QuoteEEnd-->Ты можешь это обосновать? Я, скажу осторожнее - выглядит весьма правдоподобно предположение, что процесс сойдется. Но учитывая тот факт, что каждый раз происходит попарное уравнивание, нет гарантии, что мы не впадем в бесконечный цикл.
Единственное известное мне решение не основано на попарном уранивании, но может быть и так тоже можно. Я подумаю.

PS Я тут подумал, что, видимо, неточно сформулировал один момент в условии. Каждый разбойник в итоге должен быть уверен не в том, что у него не меньше, чем у любого другого, а в том, что у него не меньше, чем 1/N часть золота. Т.е. если разбойников, например, трое и первый считает, что получил 1/3, то каким бы образом 2-й и 3-й не поделили золото между собой, 1-й все равно доволен.

[Bastion]

2VadiMGP
<!--QuoteBegin--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>Цитата </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->Но учитывая тот факт, что каждый раз происходит попарное уравнивание, нет гарантии, что мы не впадем в бесконечный цикл. <!--QuoteEnd--></td></tr></table><div class='postcolor'><!--QuoteEEnd-->
ну итерационные процессы всегда нужно останавливать на каком-то этапе (достигнув определенной точности). Здесь больше расчет на психологию...
Но я понял, что есть более элегантное решение...

[YuG]

Есть решение!
Озарение пришло по дороге домой
Алгоритм такой:
Пусть разбойников семеро.
Первый чувак делит песок на равные части.
Затем остальные шесть по очереди подходят и выбирают шесть самых больших на их взгляд кучек.
Оставшаяся (наименьшая) часть остается первому (т.е. тому, кто делил).
Он выбывает.

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

Пять кучек перемешиваются и т.д.

Вероятность сговора исключена!
Все считают, что получили не меньше другого!!!

[t_vitaly]

2YuG
Тут скорее ситуация типа "все считают что получили МЕНЬШЕ других, но виноват САМ"

[Флинт]

2VadiMGP
2YuG
Блин, так нечестно! Я уже давно это решение придумал, но отмёл именно потому что условие было неверным - для изначального условия такой вариант не проходит, а для откорректированного - в самый раз.

[Bastion]

2YuG
Или я чего-то не понимаю или это решение не годится. Т.к. первый выбравший большую кучу может сказать последнему выбиравшему что тот для общества выбрал меньшую из оставшихся (даже если и не так)!

[VadiMGP]

2YuG
Очень близко к правильному решению! Но пока еще не совсем верно.

Допустим есть 3 разбойника. 1-й и 3-й - два идиота. )
1-й делит 40-40-20 %. 2-й забирает 40(он же не идиот), а 3-й - 20! 1-й получает свои 40. Но когда 2-й и 3-й поделят свое, то 2-й видит, что получил только 30%, что меньше 1/3!

Ну? Еще одно усилие?...
2Bastion
<!--QuoteBegin--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>Цитата </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->Но я понял, что есть более элегантное решение... <!--QuoteEnd--></td></tr></table><div class='postcolor'><!--QuoteEEnd-->Ну, элегантность, как и справедливость - понятие зыбкое, но, по крайней мере, есть точное решение.

[YuG]

2VadiMGP
ба-алин... (ц) Масяня
это же надо так уметь, так зарезать такой клёвый вариант!

лады, бум думать еще... было бы классно, если бы не было бы больше подсказок...

[Bes]

2YuG
Мда. Не хочу хвастаться и строить из себя умного, но твой вариант мне пришел в голову в первые 10 минут размышления над загадкой, но я его отмел по уже указанным VadiMGP причинам.

[Bastion]

офтоп
2Bes
<!--QuoteBegin--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>Цитата </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->
Мда. Не хочу хвастаться и строить из себя умного<!--QuoteEnd--></td></tr></table><div class='postcolor'><!--QuoteEEnd-->
Намекаешь, что хорошо экзамен сдал?

[Bes]

Я тут родил чего-то. Только вот с Даниковским алгоритмом мое решение не имеет ничего общего -- с этим разделением на равные кучки я сколько ни мучался, так ни до чего толкового и не додумался...
Мой вариант проще: кто-нибудь один набирает горсть золотого песка и медленно сыпет его на землю сквозь пальцы. В тот момент, когда кому-то из разбойников (в том числе и тому, кто делит) кажется, что количество высыпавшегося на землю песка уже = 1/N, этот разбойник громко орет: "Хватит!", после чего делящий разбойник мгновенно прекращает сыпать песок. Насыпавшаяся на землю кучка передается заоравшему. Остальные, надо полагать, довольны, так как не заорали и, следовательно, не считают, что получившаяся кучка достигла 1/N. Ну и так до конца, пока каждый не получит по устраивающей его кучке.
Я понимаю, что мой вариант не содержит в себе какого-то математического метода, о котором говорил VadiMGP. Признаю также, что существует определенный временной промежуток (кто-то заорал --> звук дошел до ушей делящего --> уши передали сигнал в мозг --> мозг обработал информацию и скомандовал руке перестать сыпать песок --> сигнал дошел до руки и песок перестал сыпаться), который может стать причиной конфликта, потому что за эту долю секунды количество высыпавшегося песка может, по мнению еще кого-то, превысить объем 1/N. Но все же, я думаю, это решение заслуживает того, чтобы быть здесь озвученным. (или обынтернеченным, как говорит Bamse )

P.S. При извлечении песка из аквариума ни одной рыбки не пострадало.
P.P.S. Поиски истинного решения продолжаются. (как уже не раз говорилось, желательно все-таки без подсказок)
P.P.P.S.2Bastion -- "отл"

[VadiMGP]

2Bes
Мысль интересная, но увы... Скоростью звука и скоростью передачи импульса по нейронам мы, разумеется, можем пренебречь. А вот что делать в ситуации, когда одновременно несколько человек кричат: "Хватит!" - неясно.<!--QuoteBegin--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>Цитата </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->PS При извлечении песка из аквариума ни одной рыбки не пострадало. <!--QuoteEnd--></td></tr></table><div class='postcolor'><!--QuoteEEnd-->
А при извлечении золотого песка ни одной золотой рыбки не пострадало?

[Dutchman]

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

[Флинт]

2Bes
Кстати, твой вариант не проходит ещё и потому, что тому, кто сыпет, может остаться слишком мало...

[VadiMGP]

2Dutchman Не понял, чем это отличается от варианта, который предложил YuG?
<!--QuoteBegin--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>Цитата </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->Первый чувак делит песок на равные части. Затем остальные шесть по очереди подходят и выбирают шесть самых больших на их взгляд кучек. Оставшаяся (наименьшая) часть остается первому (т.е. тому, кто делил). Он выбывает.<!--QuoteEnd--></td></tr></table><div class='postcolor'><!--QuoteEEnd-->
2Флинт
<!--QuoteBegin--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>Цитата </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->Кстати, твой вариант не проходит ещё и потому, что тому, кто сыпет, может остаться слишком мало...<!--QuoteEnd--></td></tr></table><div class='postcolor'><!--QuoteEEnd-->Нет, не думаю, поскольку Bes внес оговорку:
<!--QuoteBegin--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>Цитата </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->В тот момент, когда кому-то из разбойников (в том числе и тому, кто делит)... <!--QuoteEnd--></td></tr></table><div class='postcolor'><!--QuoteEEnd-->