Re: дележка торта
От: UgN  
Дата: 16.01.03 15:04
Оценка: 29 (2)
Здравствуйте, bkat, Вы писали:

B>Еще одна занимательная задачка...


B>Многие наверное знают следующую задачу.

B>Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть.
B>Найти способ честно поделить торт так, чтобы никому не было обидно.

Ну, значит, так.

Спорят они, спорят... И тут прихожу Я,

Беру нож и режу торт на два неравных куска.
1.Спрашиваю: "Я честно поделил, никого не обидел?"
Если отвед "Да" -- задача решена.
Иначе
2. Съедаю меньший кусок.
3. Больший кусок делю на две неравные части.
( Если делить больше нельзя, бросаю исключение и сматываюсь )
4. Goto 1.
Re: дележка торта
От: MichaelP  
Дата: 16.01.03 15:27
Оценка: 18 (1)
Здравствуйте, bkat, Вы писали:

B>Знает ли кто решение этой задачи в общем случае:

B>1 торт, N едоков;
B>K тортов, N едоков;

1. Первый намечает один "справедливый" кусок
2. По кругу опрашиваются все осnальные: Не считают ли они "справедливым" уменьшить его
3. Если кто-то согласен уменьшить он намечает свой разрез и далее опрос продолжается исходя из размеров "нового" куска.
4. Когда круг замкнется на первом. Кусок получает тот кто наметил последний разрез.
5. Далее тоже самое для N-1
Re[3]: дележка торта
От: Lexey Россия  
Дата: 16.01.03 14:15
Оценка: 5 (1)
Здравствуйте, bkat, Вы писали:

B>Здравствуйте, Lexey, Вы писали:


B>>>Знает ли кто решение этой задачи в общем случае:

B>>>1 торт, N едоков;

L>>Один делит, а кусок берет последним.


B>А делит только один?


Ага. Поскольку ему не хочется оказаться в проигрыше, ему придется делить все поровну.
"Будь достоин победы" (c) 8th Wizard's rule.
дележка торта
От: bkat  
Дата: 16.01.03 13:41
Оценка:
Еще одна занимательная задачка...

Многие наверное знают следующую задачу.
Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть.
Найти способ честно поделить торт так, чтобы никому не было обидно.

Знает ли кто решение этой задачи в общем случае:
1 торт, N едоков;
K тортов, N едоков;

16.01.03 22:27: Перенесено из 'Алгоритмы'
Re: дележка торта
От: Lexey Россия  
Дата: 16.01.03 13:50
Оценка:
Здравствуйте, bkat, Вы писали:

B>Еще одна занимательная задачка...


B>Многие наверное знают следующую задачу.

B>Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть.
B>Найти способ честно поделить торт так, чтобы никому не было обидно.

Первый делит. Второй выбирает.

B>Знает ли кто решение этой задачи в общем случае:

B>1 торт, N едоков;
B>K тортов, N едоков;

Тоже самое. Один делит, а кусок берет последним. Каждый торт делится отдельно от других.
"Будь достоин победы" (c) 8th Wizard's rule.
Re[2]: дележка торта
От: bkat  
Дата: 16.01.03 14:06
Оценка:
Здравствуйте, Lexey, Вы писали:

B>>Знает ли кто решение этой задачи в общем случае:

B>>1 торт, N едоков;

L>Один делит, а кусок берет последним.


А делит только один?
Re[2]: дележка торта
От: Mystic Украина http://mystic2000.newmail.ru
Дата: 16.01.03 14:35
Оценка:
L>Тоже самое. Один делит, а кусок берет последним. Каждый торт делится отдельно от других.

А кто выбирает первым? В это случае имеется резон организовать коалицию тому кто делит, и тому, кто первый выбирает. ИМХО, в этом случае должен быть аукцион.
Re[3]: дележка торта
От: Lexey Россия  
Дата: 16.01.03 14:37
Оценка:
Здравствуйте, Mystic, Вы писали:

L>>Тоже самое. Один делит, а кусок берет последним. Каждый торт делится отдельно от других.


M>А кто выбирает первым? В это случае имеется резон организовать коалицию тому кто делит, и тому, кто первый выбирает. ИМХО, в этом случае должен быть аукцион.


Про коалиции речи в исходной постановке не было. С ними все будет гораздо веселее.
"Будь достоин победы" (c) 8th Wizard's rule.
Re[4]: дележка торта
От: Михаил Можаев Россия www.mozhay.chat.ru
Дата: 16.01.03 14:40
Оценка:
Здравствуйте, Lexey, Вы писали:

L>>>Один делит, а кусок берет последним.

B>>А делит только один?
L>Ага. Поскольку ему не хочется оказаться в проигрыше, ему придется делить все поровну.

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

Могу предложить следующее решение (не очень хорошо подходит для круглых тортов, но в теории и для них все в порядке):
Один плавно ведет ножик вдоль торта (перпендикулярно лезвию), отмечая все больший кусок. Когда кто-то посчитает, что ему хватит, говорит "стоп" и ему отрезают этот кусок. Делящий также может сказать "стоп" в любой момент.
... << RSDN@Home 1.0 beta 4 >>
Re[5]: дележка торта
От: Lexey Россия  
Дата: 16.01.03 14:43
Оценка:
Здравствуйте, Михаил Можаев, Вы писали:

ММ>Здравствуйте, Lexey, Вы писали:


L>>>>Один делит, а кусок берет последним.

B>>>А делит только один?
L>>Ага. Поскольку ему не хочется оказаться в проигрыше, ему придется делить все поровну.

ММ>А в каком порядке остальные будут выбирать? Я думаю, что никто не захочет уступить и каждому, кроме первого вполне может


Это абсолютно фиолетово. Можно разыграть. При отсутсвии коалиций никакой разницы не будет. С коалициями такой подход неприемлим.

>показаться, что лучший кусок уже взяли до него.
"Будь достоин победы" (c) 8th Wizard's rule.
Re: дележка торта
От: siavol Россия  
Дата: 16.01.03 15:12
Оценка:
Здравствуйте, bkat, Вы писали:

B>Еще одна занимательная задачка...


B>Многие наверное знают следующую задачу.

B>Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть.
B>Найти способ честно поделить торт так, чтобы никому не было обидно.

B>Знает ли кто решение этой задачи в общем случае:

B>1 торт, N едоков;
B>K тортов, N едоков;

А если сделать так:
1. Сначала все едоки делают по одному разрезу торта. В итоге имеем 2*N кусков
2. Каждый едок (в порядке очередности из п. 1) берет по куску
3. Каждый едок (в порядке очередности из п. 1) берет по куску
Надо робить. by В.Высоцкий
Re: дележка торта
От: vasketsov Россия http://ntprog.by.ru
Дата: 16.01.03 15:56
Оценка:
Здравствуйте, bkat, Вы писали:

B>Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть.

B>Найти способ честно поделить торт так, чтобы никому не было обидно.

Решение приведено еще вроде как у Гарднера.
Тривиально обобщается на любое количество тортов.
Смысл в том, что один двигает нож через торт (в оригинале было нечто типа проволоки ), и любой имеет право в любой момент сказать стоп, нож опускается и он берет отрезанный кусок. Для K тортов процедура может быть повторена K раз. Доказательство, что все довольны, тоже довольно тривиальное, идея такая, если у кого-то меньше, чем поровну, тозначит у кого-то другого больше, но "обделенный" перед "жадиной" "стоп" не сказал, потому противоречие.
Васкецов Сергей
http://registry.km.ru
Re: дележка торта
От: MichaelP  
Дата: 17.01.03 08:08
Оценка:
Здравствуйте, bkat, Вы писали:

B>Многие наверное знают следующую задачу.

B>Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть.
B>Найти способ честно поделить торт так, чтобы никому не было обидно.

Пришло мне в голову такое обобщение.

У одного из них день рождения и они совместно решил, что имениник должен получить кусок в r раз (r не обязательно целое) больше чем другой.
Найти решение для нецелых r , хотя бы для двух человек, мне с ходу не удалось
Re[2]: дележка торта
От: vasketsov Россия http://ntprog.by.ru
Дата: 17.01.03 12:06
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Пришло мне в голову такое обобщение.

MP>У одного из них день рождения и они совместно решил, что имениник должен получить кусок в r раз (r не обязательно целое) больше чем другой.
Ну, для нецелых, но являющихся обыкновенной дробью — практически как и для целых, то есть, формально, увеличивается число кусков на знаменатель дроби. А вот для всяких там прочих трансцендентных — чего-то не получается, да и вряд ли получится, оценка-то на глаз должна происходить, приборов-то нет.
Васкецов Сергей
http://registry.km.ru
Re: Трое на одного. Кто больше?
От: gloomy rocker Россия  
Дата: 17.01.03 12:43
Оценка:
Вариант "двое на одного" считаем решенным:
первый делит, второй выбирает.

Тепрь обобщаем до "Трое на одного"
A — первый человек
B — второй
С — третий
И так, пока не останутся неделимые крошки
Скука — двигатель прогресса.
Re[2]: Трое на одного. Кто больше?
От: vasketsov Россия http://ntprog.by.ru
Дата: 17.01.03 13:18
Оценка:
Здравствуйте, gloomy rocker, Вы писали:

GR>Тепрь обобщаем до "Трое на одного"

Да, как представлю такое решение в ситуации "третьим будешь?" — до дойдет.
Васкецов Сергей
http://registry.km.ru
Re: дележка торта
От: KGP http://kornilow.newmail.ru
Дата: 17.01.03 13:56
Оценка:
Здравствуйте, bkat, Вы писали:

B>Еще одна занимательная задачка...


B>Многие наверное знают следующую задачу.

B>Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть.
B>Найти способ честно поделить торт так, чтобы никому не было обидно.

B>Знает ли кто решение этой задачи в общем случае:

B>1 торт, N едоков;
B>K тортов, N едоков;
1) Любой делит на N равных частей — ему отдают меньшую
2) Складывают оттавшиеся N-1 частей ... N=N-1 .... и т.д. 1 шаг
Re: дележка торта
От: UgN  
Дата: 19.01.03 13:31
Оценка:
Здравствуйте, bkat, Вы писали:


B>Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть.

B>Найти способ честно поделить торт так, чтобы никому не было обидно.
B>Знает ли кто решение этой задачи в общем случае:
B>1 торт, N едоков;
B>K тортов, N едоков;

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


Уточнения.

1. Каждый претендент хочет получить 1/N часть торта, где N — общее кол-во претендентов.

2. Каждый i претендент обладает некой точностью глазомера D[i]
и в соответствии с ней определяет размер своего куска = 1/N +- D[i]

3. Если размер доставшегося куска находится в пределах 1/N +- D[i] претендент[i] не обижается.


Задача 1.


1 Торт, 2 Претендента

Аксиома:

Если торт делит претендент с наилучшим глазомером (миним. D[i]), то оба претендента остаются довольными независимо от того, кому какой кусок достался.

Решение.
--------
1.0 Пусть тот у кого нож, называется Режущий, а другой будет Оценщик.

1.1 Произвольно выбранный претендент берет нож и показывает как он хочет разделить торт на две равные части ( с учетом своего глазомера ).
Оценщик выражает свое согласие, либо несогласие.

1.2 Если Оценщик согласен, что такой разрез даст два равных (с учетом его глазомера) куска, Режущий делает разрез и берет себе любой кусок.
Очевидно, что довольны оба, так как Режущий предложил такое разделение, а Оценщик согласился. Задача решена.
При этом глазомер Режущего лучше или равен глазомеру Оценщика. (точнее)

1.3 Если Оценщик несогласен, значит глазомер Оценщика точнее. Меняем претендентов местами. Теперь у Режущего глазомер будет точнее и новый Оценщик согласится с предложением. См. п. 1.2.



Задача 2.

1 Торт, 3 Претендента

Решение.
-------

Аналогично Задаче 1.

2.1 Произвольно выбранный претендент берет нож и показывает как он хочет разделить торт на две равные части ( с учетом своего глазомера ).
Оценщики ( их теперь 2 ) выражают свое согласие, либо несогласие.

2.2 Если оба Оценщика согласны, что такой разрез даст три равных (с учетом глазомера каждого) куска, Режущий делает разрез и берет себе любой кусок. Оставшийся кусок делится на двоих как в Задаче 1.
При этом глазомер Режущего лучше или равен глазомеру любого Оценщика. (точнее)

2.3 Если хотя бы один Оценщик несогласен, значит глазомер несогласного Оценщика точнее. Меняем Режущего и несогласного Оценщика местами. Теперь у Режущего глазомер будет точнее, чем глазомер каждого оценщика, и они оба согласятся с предложением.
См. п. 2.2

2.4. Если несогласны оба Оценщика, значит у Режущего самый плохой глазомер. Меняем местами Режущего с любым Оценщиком.
Новый режущий делает свое предложение. Дальше все происходит либо как в п. 2.2, либо как в п. 2.3



Задача с 1 тортом и N Претендентами.

Решается аналогично.
Рекурсивно:
1. Находим претендента с лучшим глазомером.
2. Он отрезает себе 1/N кусок и уходит.
3. Решаем задачу для 1/(N-1) претендентов ( для N = 3 и N = 2 решение показано выше )


Задача с K тортами и N Претендентами.

Сводится к K задачам с 1 тортом и N претендентами.


Единственно, плохо при больших N -- замучаешься выборы проводить...
( может их постепенно упорядочивать в соответствии с глазомером? )
Re[2]: дележка торта
От: -=[x]=- Россия  
Дата: 20.01.03 07:01
Оценка:
Здравствуйте, UgN, Вы писали:

UgN>...


А может проще?
Например, я и моя подруга едим торт.
Я режу его на 2 равных (по моему мнению) куска. Мне безразлично, какой из них есть.
Подруга выбирает из этих двух тот, который (по ее мнению) больше. Теперь она довольна.
Я ем оставшийся, и тоже доволен (см. жирный текст).

Осталось перенести на вариант со мной и k подругами.
... << RSDN@Home 1.0 beta 3 >>
icq: 118852038
Re[3]: дележка торта
От: Atilla Россия  
Дата: 20.01.03 07:11
Оценка:
на практике бывает так, что после того как ты выбрал или разрезал кусок, оказывается, что можно было это сделать более выгодным образом.
Кроме того, способ не оптимальный: допустим подруге больше нравится левая часть торта, чем правая (правая, с горчицей и луком , ей неприятна). Вам же, наоборот, нравится правая часть. В этом случае можно себе отрезать правый кусок побольше и подруга не обидится, выберет кусок, который ей больше нравится, хоть и меньше. Таким образом у каждого делящего будет кусок, который лучше (по мнению этого человека), чем кусок друга.
... << RSDN@Home 1.0 beta 4 >>
Кр-ть — с.т.
Re[3]: дележка торта
От: UgN  
Дата: 20.01.03 07:27
Оценка:
Здравствуйте, -=[x]=-, Вы писали:

X>Осталось перенести на вариант со мной и k подругами.


Ага, совсем ничего...
Re: дележка торта
От: Real 3L0 Россия http://prikhodko.blogspot.com
Дата: 20.01.03 09:06
Оценка:
Здравствуйте, bkat, Вы писали:

B>Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть.

B>Найти способ честно поделить торт так, чтобы никому не было обидно.

B>Знает ли кто решение этой задачи в общем случае:

B>1 торт, N едоков;
B>K тортов, N едоков;

(Ответ Если нож острый, то весь торт забирает тот, у кого нож. (Выполнение условий Остальные не обижаются потому, что живы остались! А если не верят, что чесно, пусть попробуют обидиться!
Решение в общем случае:
Для 1 торта и N едоков надо брать нож длиной 5см*N+5см, но не больше 1м ...
Для K тортов и N едоков решение анналогично следует из выше сказанного ...

Задача будет интрересней, если будет 1 торт, N едоков и N ножей ...
Прыгая от радости, смотри, чтобы кто-нибудь не убрал у тебя землю из-под ног. << RSDN@Home 1.4 >>
Вселенная бесконечна как вширь, так и вглубь.
Re: дележка торта
От: Valentin Pimenov  
Дата: 20.01.03 09:21
Оценка:
Здравствуйте, bkat, Вы писали:

B>Еще одна занимательная задачка...


B>Многие наверное знают следующую задачу.

B>Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть.
B>Найти способ честно поделить торт так, чтобы никому не было обидно.

B>Знает ли кто решение этой задачи в общем случае:

B>1 торт, N едоков;
B>K тортов, N едоков;

Простейший случай все знают (2 человека, 1 торт): один режет, другой выбирает себе кусок.
Случай, когда людей N:
1. Первая итерация такая же как и в простейшем случае.
2. Вторая итерация: каждый из 2-х режет свой кусок ("половинку") на 3 части. Затем третий берет по одному кусочку у каждого.
3. Третья итерация: каждый из 3-х режет свой кусок на 4 части... и т.д. до исчерпания людей

Случай, когда тортов больше одного: всё то же самое что и во втором. Тут возможны варианты в способе деления, но общий смысл алгоритма остается:
1. В первой итерации можно резать все торты пополам,
2. Или разделить все торты пополам (если, например, тортов 3, то по полтора торта).

With best wishes
Valentin Pimenov aka Valker
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.