28
КВАНТ 2008/№4
Жюри конкурса отмечает также хорошие работы школьницы Галямовой Оксаны, Белорецк, гимназия 14, 8 кл.
и следующих кружков: Центра дополнительного образования, Нижнекамск, руководитель Ф.Г.Калимуллина,
лицея 64, Омск, руководитель Ю.Е.Рязанова.
Все победители конкурса награждаются DVD- дисками – электронным архивом журнала «Квант» с 1970 по 2006 год.
Проблемы дележки
В.УФНАРОВСКИЙ
ВА РАЗБОЙНИКА ДЕЛЯТ ДОБЫЧУ. ГРАБИТЬ БЫЛО ТАК славно и легко, делить оказалось намного сложнее! Каждый из разбойников уверен, что именно он может разделить все поровну, но совершенно не верит в способности коллеги. Наконец, старший из них говорит: – Хорошо. У меня есть идея. Давай я попробую разделить добычу поровну. – Да ты ведь не умеешь! – закричал младший.
Иллюстрация В.Иванюка
29
К
– Подожди немного, – ответил старший и разделил все надвое. – Мне кажется, я поделил как надо. Ты согласен? – Нет, конечно. Это совершенно не равные части! – Пусть так. И какая же из частей, по-твоему, больше? – Вот эта! – не сомневаясь указал более юный грабитель. – Прекрасно! Бери ее. Ты доволен? – Конечно же! А ты? – Вне всяких сомнений. Я уверен, что обе части одинаковые: ведь это я делил их. Разбойники разошлись, довольные дележкой. В следующий раз их было трое. И опять надо было поделить добычу поровну, но уже на троих. Как же это сделать? Вначале старший грабитель попытался использовать ту же идею. Он поделил все на три (как ему казалось) равные части и предложил остальным разбойникам выбрать себе долю. Старший надеялся, что они выберут разные части – тогда он заберет оставшуюся, и все будут довольны. Но оба его коллеги захотели одну и ту же часть. – Ладно, – сказал он. – Раз вы оба считаете, что это самая большая часть, выберите самую маленькую. Я ее возьму себе, а вы между собой как-нибудь разберетесь. Это была хорошая идея, но, как на беду, теперь они выбрали разные части. И больше уже никто не знал, что делать. Пошли споры, потом выстрелы… Полиция появилась удивительно быстро, и разбойники были рады, что успели унести ноги. Но все трое продолжали размышлять: как же все-таки можно было поделить добычу по справедливости, чтобы каждый был уверен, что получил не меньше трети (даже если у всех разные точки зрения на то, что является третью добычи, а что – нет)? На следующий раз грабителей было десять. Но теперь им предстояло разделить добычу на 10 частей! Старший рассказал оставшимся, как сложно было делить даже на три части, и предложил: – Я думаю, надо позвать математика, иначе мы не справимся. У меня есть один хороший знакомый. – Надо будет ему платить? – скривились прочие. – Нет-нет, он это сделает бесплатно. Он очень любит решать сложные задачи. И будет доволен, если сумеет написать математическую статью об этом. – Без наших имен? – Без. – Ну тогда пусть попробует, – нехотя согласились разбойники. Математик и впрямь заинтересовался проблемой. Поразмыслив, он предложил следующее решение. – Разбойники, – начал он, – каждый из вас уверен, что он (и только он) знает, сколько составляет 1/10 часть от этого хлама? – Конечно, – несколько обиженно подтвердили они. – Прекрасно! Тогда ты, – указал он на одного из грабителей, – отдели 1/10 этого. – Тот повиновался. – Теперь ты, – указал он на другого. – Считаешь ли ты, что здесь больше 1/10?
М
Ш
– Нет, – ответил разбойник. – Замечательно! Тогда ты, – указал он на следующего. – Считаешь ли ты, что здесь больше 1/10? – Да, здесь слишком много, – проворчал тот. – Тогда уменьши долю, сделай в точности 1/10! – попросил математик. Разбойник несколько уменьшил кучку. – Вот теперь здесь действительно 1/10, – прокомментировал он. – А вы, – обратился математик к двум первым разбойникам, – теперь можете быть уверены, что в кучке даже меньше 1/10. – Конечно, из нее ведь убрали немного, – подтвердили они. – Ну и отлично! Тогда я спрошу следующего, – и он выбрал нового разбойника, – считаешь ли ты, что здесь больше 1/10? И таким образом математик опросил каждого, предлагая уменьшить долю тем, кто считал, что она слишком велика. Когда последний грабитель был опрошен, математик опять обратился ко всем. – Итак, среди вас не могло остаться никого, кто считает, что в этой кучке сейчас больше 1/10 добычи. – Естественно, – ответили разбойники. Каждый, кто думал, что часть велика, уже уменьшил ее. – Чудесно! И кто же последним уменьшил эту долю? – Я, – отозвался юный разбойник. – Значит, когда ты делил, ты был уверен что это и есть 1/10. – Я и сейчас в этом уверен. Ведь никто не уменьшил ее после меня. – Вот и бери ее себе! Ты считаешь, что это 1/10 добычи, остальные же уверены, что это не больше. – Да! – радостно согласились разбойники. Они начали понимать. – Ну и хорошо! Теперь у нас более простая задача: разделить остаток на 9 частей. Начнем так же. Ты, – указал математик на одного из грабителей, – отдели 1/9 этого… И тем же способом математик выдал долю еще одному грабителю, затем – еще одному, и вскоре уже каждый разбойник довольно улыбался, оказавшись со своей частью добычи. На радостях разбойники достали большую бутыль старого хорошего вина и устроили празднество. Внезапно математик предложил: – А хотите, я и вино разделю поровну? – Нет, это слишком долго. – Не волнуйтесь, я справлюсь быстро. – Как это? – не удержались они от любопытства. – Очень просто. Я сам не пью, поэтому делить надо опять на десятерых. Уверен ли каждый из вас, что он сможет определить, сколько составляет 1/10 часть содержимого этой бутыли? – Никаких проблем! – Тогда я потихонечку начну наливать вино из бутыли в этот кубок. Как только кто-нибудь решит, что это как раз 1/10, он должен немедленно крикнуть и остановить меня. Договорились?
30
КВАНТ 2008/№4
– Попробуем, – ответили разбойники несколько озадаченно. Они никогда еще не пили так странно. Математик начал наполнять кубок. Он становился все более и более полным. Наконец, один из разбойников не выдержал и закричал: – Стоп! Иначе будет слишком много. Сейчас как раз 1/10 часть бутыли! – Но другие так не думают? – спросил математик. – Конечно, нет, – подтвердил разбойник, – они ведь молчали, а значит, считают, что там меньше 1/10. – Ну и пусть! Тогда это твоя доля! А мы продолжим, – сказал математик и начал наполнять следующий кубок. – А если несколько человек крикнут вместе? – заволновался вдруг один из оставшихся. – Отдадим долю любому из них и продолжим делить. Все равно в итоге каждому достанется не меньше 1/10 с его точки зрения, – успокоил всех математик. Разбойники задумались на некоторое время. – Гениально! И так просто, – сказал, наконец, самый сообразительный из них. – А почему мы не могли так делить добычу? – спросил он. А что ты думаешь, читатель?
Комментарии Сказка ложь, да в ней намек. Надеемся, читатель понял задачу и красивое решение, представленное в этой сказке. Алгоритм дележки, который описан в ней, конечно же не единственный. Возможно, читателю удалось придумать свой. Но если нет, пусть следующие задачи помогут ему увидеть другие способы деления. Задача 1. Главная проблема в делении на троих была вот в чем: когда один из разбойников разделил добычу на три части, самую большую часть двое оставшихся указали одинаково, а самую маленькую – по-разному. Выйти из этой ситуации можно так: два оставшихся разбойника делят самую большую часть между собой, и еще каждый из них делит среднюю (со своей точки зрения) часть пополам с первым разбойником. Покажите, что при таком делении каждый должен быть доволен. Задача 2. Убедитесь, что следующий алгоритм тоже решает проблему для троих. Двое делят всю добычу между собой. Затем третий делит долю каждого из первых двух разбойников на три части. Двое первых выбирают по меньшей части из своих трех частей и отдают третьему. Задача 3. Работает ли такой алгоритм для четверых: сначала трое делят все между собой, затем каждый из них делит свою порцию на четыре части, после чего последний разбойник забирает по лучшему куску у каждого? Заметьте, что алгоритм подобен предыдущему, но все же слегка отличается. Задача 4. Сформулируйте и проверьте алгоритм для N разбойников на основе идей из предыдущих задач. Задача . Предположим, что в шайке есть атаман, выставивший дополнительное условие – он должен
получить не меньше любого другого разбойника (со своей точки зрения). Предложите соответствующий способ дележки: а) для случая трех разбойников; б) для произвольного их числа. Задача . Удастся ли трем завистникам поделить добычу так, чтобы каждый был уверен, что никто не получил больше, чем он сам? Можно ли придумать способ дележки для любого числа завистников? Заметьте, что эта задача более сложная, чем исходная задача о трех разбойниках или задача об атамане. Для тех, кто хотел бы углубиться в математические тонкости, мы рекомендуем заглянуть в Интернет на страницу http://www.turgor.ru/lktg/1999/razbr.php (где приведен целый исследовательский цикл задач о разбойниках, предлагавшийся в 1999 году участникам XI Летней конференции Турнира городов). Есть еще несколько деликатных вопросов. А что если разбойники начнут жульничать, например, кооперироваться между собой и делить не поровну? Может ли это быть выгодно? Но это тема для отдельного разговора. В предыдущих задачах неявно предполагалось, что добыча безгранично делима (т.е. каждый набор сокровищ может быть разделен на любое число частей, равных с точки зрения данного разбойника). А что делать, если добыча не очень-то делима? Скажем, как делить телевизор или алмаз? Если у разбойников имеются деньги, можно предложить такой элегантный алгоритм. Каждый разбойник оценивает каждый предмет в сумму денег, которую, по его мнению, предмет стоит. Тот, кто дает наибольшую сумму, ее и платит и забирает вещь себе. После этого все выплаченные деньги делятся поровну. Вот другая модификация этой идеи, которую автор с успехом использовал на практике. Есть покупатель и есть продавец. Продавец хочет продать подороже, но не обязан продавать. Покупатель хочет купить подешевле, но не обязан покупать. Вместо того чтобы торговаться, можно предложить такой метод. Продавец пишет на бумажке минимальную сумму А, за которую он готов отдать товар, а покупатель – максимальную сумму B, которую он готов заплатить. Затем они смотрят на бумажки. Если А>В, то сделка не состоится. Иначе ценой будет среднее арифметическое, и оба будут довольны. Разумеется, и в этом, и в предыдущем алгоритме вопрос о жульничестве особо интересен. И последнее. А как на практике разделить действительно поровну полный стакан воды (считая стакан цилиндром)? Очень просто: медленно (чтобы поверхность была плоской) отливать воду, пока не увидишь начало дна. Из соображений симметрии в стакане как раз и останется половина.