|
Справедливый раздел
Hесколько золотоискателей захотели разделить намытый ими золотой песок
поровну, однако весов рядом не оказалось, а поехать в город, оставив песок
никто не захотел. Если бы их было двое, то все было бы понятно: первый делит
кучу на две части, а второй первым выбирает себе любую часть, при этом, если
кому то и досталась меньшая часть, то ему в этом следует винить только себя.
Обобщите способ раздела песка поровну между n золотоискателями (n>2). Способ
должен гарантировать, что каждый получит не менее 1/n песка (конечно если
только он сам не оплошается), даже если остальные золотоискатели вступят в
сговор.
|
|
Вообще существует много способов решения (и я их все принимал), но мне
нравится этот:
У Гарднера описан так называемый "громкий" метод решения.
Для удобства представим, что все золото перелито в один длинный кусок
золотой проволоки, который и нужно разделить так, чтобы никто не был в
обиде.
Один из делящих (неважно, кто) медленно перемещает руку с кусачками от
одного конца проволоки к другому, тем самым отмеряя проволоку. В тот
момент, когда кому-то кажется,
что отмеренная доля не меньше 1/n, он громко кричит "Стоп" и тут же человек
с кусачками
сжимает инструмент, и крикнувший получает эту самую долю. Все молчавшие,
естественно,
считают, что 1/n еще не достигнута, поэтому оставшаяся часть не меньше
(n-1)/n, а значит, каждый из них имеет шанс получить не меньше 1/n. Далее
процесс дележа продолжается уже для (n-1) человека тем же самым образом.
|
