Cool Folders ® :: Форум Игротека :: Справедливый делёж (логическая задача)

Справедливый делёж (логическая задача)

Автор: Большой Грызь
Дата : 08-07-02, Пнд, 04:32:39

Знаете ли вы, как справедливо разделить что-то (например, золотой песок) между двумя людьми?
Этот способ известен: надо дать одному из них разделить этот золотой песок на две кучки по своему усмотрению, а второму - выбрать любую из них.

А как справедливо разделить золотой песок, если число участников дележа - 3, 4 или для общего случая - N человек?

-----------------------------
Quod erat demonstrandum!

Справедливый делёж (логическая задача)

№ 2

Автор: 369
Дата : 08-07-02, Пнд, 14:04:25

Всех участников дележа

, а золотой ключик, т.е., песок отдать Грызю на новый сервер!!

(И пусть скажет, что это не справедливо!

)

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Улыбайтесь, это всех раздражает

Справедливый делёж (логическая задача)

№ 3

Автор: Hanibal
Дата : 08-07-02, Пнд, 14:20:41

Знаем

Для 3-х есть два решения (не включая универсальное, предложенное 369).

Справедливый делёж (логическая задача)

№ 4

Автор: Большой Грызь
Дата : 08-07-02, Пнд, 14:40:01

Ханибал, а для N?

-----------------------------
Quod erat demonstrandum!

Справедливый делёж (логическая задача)

№ 5

Автор: Hanibal
Дата : 08-07-02, Пнд, 15:08:05

Для n знаю алгоритм деления "по справедливости". То есть приглянувшейся части

Справедливый делёж (логическая задача)

№ 6

Автор: Большой Грызь
Дата : 08-07-02, Пнд, 15:09:55

Ясно

тады ждем остальных

-----------------------------
Quod erat demonstrandum!

Справедливый делёж (логическая задача)

№ 7

Автор: Усталый путник
Дата : 08-07-02, Пнд, 17:49:51

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

Справедливый делёж (логическая задача)

№ 8

Автор: Hanibal
Дата : 08-07-02, Пнд, 18:40:59

Уважаемый Усталый путник .

К Вашему ответу на загадку Большого Грызя просто напрашивается..

"... через 2 часа никого из делящих не осталось в живых... они перерезали друг друга

И вернулся Тамерлан ... и изрёк прищурив свой правый косой глаз : -Есть у меня решение и для 369N cановников и военноначальников.."

Всемирная история . Банк "ИмпериалЪ".
Отделение афульского "Гипернетто".

Справедливый делёж (логическая задача)

№ 9

Автор: Большой Грызь
Дата : 08-07-02, Пнд, 18:46:18

Люди, я серьезно

Отгадают - стебитесь, сколько хотите.

-----------------------------
Quod erat demonstrandum!

Справедливый делёж (логическая задача)

№ 10

Автор: Паша
Дата : 12-07-02, Птн, 03:02:09

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

Справедливый делёж (логическая задача)

№ 11

Автор: Большой Грызь
Дата : 12-07-02, Птн, 04:37:13

Подробнее , пожалуйста

-----------------------------
Quod erat demonstrandum!

Справедливый делёж (логическая задача)

№ 12

Автор: Паша
Дата : 12-07-02, Птн, 06:07:54

Грызь, куда уж подробнее?
Каждый рандомально берёт номер от 1 до К, потом последний отделяет свою долю, предпоследний выбирает, кто из них двоих её берёт, тот из них, кто остался без доли становиться последним среди оставшихся. Дальше по индукции...

Справедливый делёж (логическая задача)

№ 13

Автор: Большой Грызь
Дата : 12-07-02, Птн, 06:13:17

Не проходит номер.
Допустим я выбрал номер 1. Почему моя доля должна зависеть от выбора двух последних? Допустим, К и К-1 договорились за кулисами, после чего К выбрал (утрирую) половину всего песка. К-1, естественно, решил, что эту долю берет он и все шито-крыто. К и К-1 нагрели всех на половину всего золотого песка и все по правилам дележа.
Задача ж ведь, чтобы НИ У КОГО не возникло претензий НИ К КОМУ.

Или я чего-то не понял в твоем объяснении?

-----------------------------
Quod erat demonstrandum!

Справедливый делёж (логическая задача)

№ 14

Автор: Паша
Дата : 12-07-02, Птн, 06:56:53

Имелось в виду отсутствие закулисных переговоров...

Справедливый делёж (логическая задача)

№ 15

Автор: Паша
Дата : 12-07-02, Птн, 07:04:48

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

Справедливый делёж (логическая задача)

№ 16

Автор: Большой Грызь
Дата : 12-07-02, Птн, 07:23:03

Почему же

Дело вот в чем. Объясню на примере троих.
Итак, первый отрезает свою долю и делает это довольно точно.. то бишь скажем 33%. Второй отрезает тоже вроде точно.. Но лишь с его точки зрения.. Но с точки зрения первого он отрезал 40%. Следовательно кучки будут: 33%, 40% и 27% и последний выберет, естественно 40%. Допустим даже, что ошибка второго не принесла ему прибыли ибо самую большую кучку по твоей схеме выберет 3-й. Затем 2-й выберет 33% и первому достанется самая маленькая кучка. Но почему, спрашивается, 1-й должен зависеть от выбора 2-ого? А, значит, 1-й не согласится с тем, как отрезал долю второй. И спорить они будут до посинения ибо каких-то приборов, которые смогут доказать точность деления нет.

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

Ежели участник Х выбирает себе долю до участника У, то этот У уже не имеет возможности выбирать из ВСЕГО пространства выбора, а, значит, он зависит от того участника, который отделял ту долю, которую выбрал Х. И он может не согласится с таким делением.

Наглядный пример я привел в начале постинга.

-----------------------------
Quod erat demonstrandum!

Справедливый делёж (логическая задача)

№ 17

Автор: eliuha
Дата : 12-07-02, Птн, 12:58:06

public init ()
{
int raz=0;
int n=getNoOfPeople()
float treasure;
float kusok;
treasure=x;
kusok= treasure/n;
}
action () {
while (int raz<n-1){
float i= kusok/(n-1);
chuvak[raz].getKusockek();
raz++;
}

Нет кайфа без лайфа
Хоть фейсом об тейбл.

Справедливый делёж (логическая задача)

№ 18

Автор: Большой Грызь
Дата : 18-07-02, Чтв, 05:21:25

Забросили задачку-то

Говорить ответ или подождать?

-----------------------------
Quod erat demonstrandum!

Справедливый делёж (логическая задача)

№ 19

Автор: Daniel
Дата : 18-07-02, Чтв, 16:30:38

Говори

Справедливый делёж (логическая задача)

№ 20

Автор: Паша
Дата : 21-07-02, Вск, 12:53:53

Попробуем так:
Первый отрезает себе кусок, потом все высказываются на тему, согласны ли они, чтобы он этот кусок забрал. Первый несогласившийся, становится первым, только он теперь отрезает не от большого куска, а от того, который он не отдал предыдущему. На этом этапе бывшие первые и уже согласившиеся в опросе не учавствуют. Таким образом за конечное количество итераций несогласные заканчиваются и кто-то один остаётся со своим куском, который все одобрили. После чего процесс повторяется...

Справедливый делёж (логическая задача)

№ 21

Автор: Большой Грызь
Дата : 21-07-02, Вск, 14:41:44

Подробнее, пожалуйста. Не совсем понял "несогласившийся, становится первым, только он теперь отрезает не от большого куска, а от того, который он не отдал предыдущему"

-----------------------------
Quod erat demonstrandum!

Справедливый делёж (логическая задача)

№ 22

Автор: Паша
Дата : 21-07-02, Вск, 15:23:52

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

Справедливый делёж (логическая задача)

№ 23

Автор: Большой Грызь
Дата : 21-07-02, Вск, 16:38:24

Всё равно не въехал

Распиши алгоритм по пунктам. Как, какой, сколько и кто куски отделяет.

-----------------------------
Quod erat demonstrandum!

Справедливый делёж (логическая задача)

№ 24

Автор: Паша
Дата : 22-07-02, Пнд, 07:16:09

Есть большая куча. К ней подходит первый и берёт свою долю. Будем его называть "потенциальный обладатель доли". Потом подходит второй и говорит, согласен ли он, чтобы первый эту долю себе взял. Тут есть два варианта. Если он согласен, то подходит следующий и высказывает своё мнение о выбранной доле. Если второй несогласен, то бывший "потенциальный обладатель доли" отходит в сторону и на данном этапе становится сторонним зрителем. Второй, который не согласился, становится "потенциальным обладателем доли", но при условии, что доля, которую он хочет взять себе, должна быть <=, чем доля, которую хотел себе взять предыдущий "потенциальный обладатель доли".
Таким образом, когда процесс пробежит всех участников, последний "потенциальный обладатель доли" превращается в "истинного обладателя доли" и выбывает из игры со своей долей. После чего этап делёжки повторяется с меньшим количеством участников...

Справедливый делёж (логическая задача)

№ 25

Автор: Большой Грызь
Дата : 22-07-02, Пнд, 07:37:35

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

Что такое "<="?
Первый выбрал кучку, второй согласился, третий согласился, четвертый - не согласился - стал потенциальным обладателем это самой кучки и процесс продолжился дальше? то есть свое согласие-несогласие высказывают пятый, шестой и так далее?
Так? Тогда что значит это "<="?

-----------------------------
Quod erat demonstrandum!

Справедливый делёж (логическая задача)

№ 26

Автор: Паша
Дата : 22-07-02, Пнд, 13:05:58

Это значит, что несогласный, ставший "потенциальным обладателем кучки" может сделать её меньше или оставить такой же. То есть "<=" означает "меньше или равно".

Справедливый делёж (логическая задача)

№ 27

Автор: Большой Грызь
Дата : 22-07-02, Пнд, 13:36:53

Ситуация: первый и последний закулисно договариваются между собой. Первый хапает сразу.. ну скажем 99% от общей кучи. Второй естественно не соглашается и берет эту кучу себе. Точно также не соглашается третий. Таким образом доходит очередь до последнего, который хапает все 99%.

Такая ситуация вроде бы возможна при твоем ответе.

-----------------------------
Quod erat demonstrandum!

Справедливый делёж (логическая задача)

№ 28

Автор: Паша
Дата : 22-07-02, Пнд, 13:47:37

Грызь, невозможно, так как второй сразу же урежет эту часть до нормального размера. Начни разбор с конца. Если есть человек, номер которого не важен, который способен правильно отрезать себе ровный кусок, то чтобы не делали остальные, он уйдёт с таким или бОльшим куском.

Справедливый делёж (логическая задача)

№ 29

Автор: Willy
Дата : 23-07-02, Втр, 05:17:23

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

Справедливый делёж (логическая задача)

№ 30

Автор: Большой Грызь
Дата : 23-07-02, Втр, 09:31:36

Вилли, не скажи-не скажи

Я привёл чёткое определение того, что считается справедливым дележом. В рамках данной темы по крайней мере.

Паша, я потом поищу дырки в твоем решение. Может их и нет - не спорю. Но поищу.
А пока что приведу ответ. Решение на самом деле очень простое - по индукции.
Индукция такова:
1) Для 2 человек я показал, как можно разделить без претензий.
2) Допустим, что N человек разделили между собой и не имеют претензий друг к другу. Пусть теперь каждый из них разделит свою долю на (N+1) частей настолько поровну, насколько они смогут это сделать, а (N+1)-й человек возьмет у каждого из них по доле по своему выбору. Таким образом каждый получит по 1/(N+1). У первых N претензий к (N+1)-ому нет - они делили свои доли как можно более поровну сами. У (N+1)-ого тоже нет претензий - он выбирал из ВСЕХ долей.

-----------------------------
Quod erat demonstrandum!

Справедливый делёж (логическая задача)

№ 31

Автор: Паша
Дата : 23-07-02, Втр, 16:23:51

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

Справедливый делёж (логическая задача)

№ 32

Автор: Большой Грызь
Дата : 23-07-02, Втр, 17:59:58

Паша, к сожалению я набрел в интернете уже на решение этой задачи.

-----------------------------
Quod erat demonstrandum!

Справедливый делёж (логическая задача)

№ 33

Автор: Vii
Дата : 20-08-03, Срд, 17:06:30

Я уверен, что можно найти и другие способы...

А как Вам такой?
1. Один (назовем его "делитель"

делит добро на N кучек.
2. Каждый по очереди, кроме делителя, берет ту кучку из еще невыбранных, которая ему больше нравится.
3. Делитель забирает то, что осталось, и идет в пивную пропивать свою долю.
4. Если кто-то (назовем его "недовольным" ) считает, что ему досталась кучка меньше кого-то из предыдущих, то он громко выссказывет свое недовольство.
5. В этом случае все добро (кроме того, что уже находится в пивной и успешно пропивается) сваливается в кучу, а недовольный становится делителем. Только теперь нужно делить на N-1 частей.

Справедливый делёж (логическая задача)

№ 34

Автор: Паша
Дата : 23-08-03, Сбт, 12:51:27

На мой взгляд, тоже годится...