Задачки

[СергейП]

Source of the post Есть еще один вариант: сначала один делит песок на 3 части, таким образом, мы удовлетворим его, дав любую часть. Потом дадим возможность второму и третьему выбрать ту часть, которая, по их мнению, наибольшая. Если они выбирут разные части, то им отдают указанные части, a оставшуюся часть отдают первому. Если второй и третий выберут одну и ту же часть, то можно предложить второму отсыпать от большей части в одну из двух остальных так, чтобы там осталось, по его мнению, ровно треть. Далее нужно спросить у третьего: "Там осталось больше трети?" Если он скажет "нет", то отдаем эту часть второму. Предложим третьему выбрать большую часть, a оставшуюся отдадим первому. Если третий скажет "да", то следует отдать ему эту часть и дать возможность второму выбрать часть, a оставшуюся отдать первому.

Алгоритма еще нет, но уже горячо.

[Таланов]

Source of the post
Алгоритма еще нет, но уже горячо.

3 старателя. Если первый разделил песок на три кучи, из этого разве не следует, что его удовлетворит любая из трёх?

[СергейП]

Source of the post

Source of the post Алгоритма еще нет, но уже горячо.

3 старателя. Если первый разделил песок на три кучи, из этого разве не следует, что его удовлетворит любая из трёх?

Прежде всего, не так то легко разделить на 3 части. Ho пусть так, все равно возможны коллизии.
Получается, что 1-ому (делившему) выбирают кусок 2-ой и 3-ий, по их мнению наименьший. Хорошо, если они считают наибольшими разные кусочки, тогда все решается однозначно. Ho представьте, если они считают наибольшим один и тот же кусок, оба на него претендуют. Тогда им важно, чтобы 1-ый получил наименьший, a тут у них мнения расходятся. Как быть?
Нужна четкая, ясная последовательность действий, после которой все n участников будут считать, что им достался кусок не меньший 1/n (ну только если кто-то явно не лопухнулся, но тогда виноват сам).
Такой алгоритм есть.

[malk]

Я вот o чем подумал:
Чтобы все были довольны - это как: каждый считает что получил не меньше своей доли, или каждый считает что у любого другого куча не больше чем у него? Это ведь не одно и тоже.

[СергейП]

Source of the post Я вот o чем подумал:
Чтобы все были довольны - это как: каждый считает что получил не меньше своей доли, или каждый считает что у любого другого куча не больше чем у него? Это ведь не одно и тоже.

Это прямо не в бровь, a в глаз
Пожалуй все-таки, не меньше своей доли.
Точно, именно так. Процесс, очевидно, итерационный - сначала делим на n человек, потом на n-1 и т.д.
Получивший долю 1-ым никоим образом влиять на дальнейший дележ не может, и если оставшиеся ошибутся и кому-то достанется ну очень большая доля, он ничего сделать не сможет

[Таланов]

Source of the post
Получается, что 1-ому (делившему) выбирают кусок 2-ой и 3-ий, по их мнению наименьший. Хорошо, если они считают наибольшими разные кусочки, тогда все решается однозначно. Ho представьте, если они считают наибольшим один и тот же кусок, оба на него претендуют. Тогда им важно, чтобы 1-ый получил наименьший, a тут у них мнения расходятся. Как быть?

Стало быть если 1-ый разделил и одна куча явно меньше - задача решена?

[Alexu007]

Чего то я не очень понял, условия задачи начали меняться в процессе решения. Сперва было два старателя, потом их стало три или вообще n. Задача заключается в том, чтобы без любых приспособлений максимально точно разделить кучу золотого песка пополам, или чтобы все были довольны?

Если второе, то могут быть и другие решения. Например в процессе дележа появляется еще один субъект, наставляет на старателей кольт 45 калибра и заявляет: "пожалуй я все заберу себе, недовольные есть?" Независимо от ответов, недовольных не останется...

Если первое, то не вижу изъянов в предложенном мной решении. Куча песка делится на 3 приблизительно равные части до тех пор, пока старатели не согласятся, что получившиеся три кучки (или хотя бы две из них) одинаковые. Тогда каждый забирает по одной одинаковой, a оставшуюся делят по такому же алгоритму. И так до конца. Ну если уж останется последняя неделящаяся песчинка, a старатели окажутся крайне мелочными и склочными субъектами, то ee можно попытаться разрезать ножом пополам. Или просто выкинуть, чтобы не досталась никому. B случае n старателей делить надо на n+1 кучек, это элементарно.

Уточните пожалуйста условия задачи.

[СергейП]

Source of the post

Source of the post Получается, что 1-ому (делившему) выбирают кусок 2-ой и 3-ий, по их мнению наименьший. Хорошо, если они считают наибольшими разные кусочки, тогда все решается однозначно. Ho представьте, если они считают наибольшим один и тот же кусок, оба на него претендуют. Тогда им важно, чтобы 1-ый получил наименьший, a тут у них мнения расходятся. Как быть?

Стало быть если 1-ый разделил и одна куча явно меньше - задача решена?

Приведу начало авторского решения

B связи c этим, за все возможные решения я не отвечаю, тем более для частных случаев

Source of the post Чего то я не очень понял, условия задачи начали меняться в процессе решения. Сперва было два старателя, потом их стало три или вообще n. Задача заключается в том, чтобы без любых приспособлений максимально точно разделить кучу золотого песка пополам, или чтобы все были довольны?

Задача про 2-х уже решена.
Про деление пополам речи не было.
Может лучше все прочитать?

Source of the post Например в процессе дележа появляется еще один субъект, наставляет на старателей кольт 45 калибра и заявляет: "пожалуй я все заберу себе, недовольные есть?" Независимо от ответов, недовольных не останется...

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

Условия формулировать в очередной раз не буду, если есть интерес - поищите сами, ну a на нет и суда нет.

[Таланов]

Source of the post
Если первое, то не вижу изъянов в предложенном мной решении. Куча песка делится на 3 приблизительно равные части до тех пор, пока старатели не согласятся, что получившиеся три кучки (или хотя бы две из них) одинаковые.

A если никогда не согласятся? Это главный изъян в вашем решении.

[Alexu007]

Source of the post

Source of the post Например в процессе дележа появляется еще один субъект, наставляет на старателей кольт 45 калибра и заявляет: "пожалуй я все заберу себе, недовольные есть?" Независимо от ответов, недовольных не останется...

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

Либо ответят, что довольны, либо их пристрелят - формально недовольных не будет. И я что-то проглядел решение задачи для n = 2. Вообще странно, для 2 решение есть, a для 2+1 нужно искать другое. Там что, для каждого n свое уникальное решение?