Есть идея! - [52]
А вот аналогичная задача, требующая иного решения. В бутыль неправильной формы из прозрачного стекла налит концентрированный раствор кислоты. На стенках бутылки имеются 2 отметки: одна соответствует 10 л кислоты, другая — 5 л.
Кто-то отлил немного кислоты, отчего уровень ее в бутыли стал чуть ниже отметки 10 л. Вам требуется отлить для опыта ровно 5 л кислоты. Кислота слишком опасная и летучая, чтобы ее можно было переливать в другие мерные сосуды. Как легко и просто отмерить ровно 5 л кислоты?
Одно из решений состоит в том, чтобы, бросая в бутыль стеклянные шарики (или шарики из любого другого материала, не разъедаемого кислотой), довести уровень кислоты до отметки 10 л, после чего отливать кислоту до тех пор, пока ее уровень в бутыли не сравняется с отметкой 5 л.
Как распределить домашние обязанности
Мистер и миссис Джонс только что поженились. У каждого из них есть постоянная работа, и они решили распределить между собой и обязанности по дому.
Стремясь к честному распределению обязанностей по дому, супруги Джонс составили перечень всех работ по дому на неделю.
Бастер. Я беру на себя половину обязанностей, дорогая. Остальные обязанности предоставляю тебе.
Жанет. Прошу прощения, Бастер, но, по-моему, ты распределил обязанности нечестно. Мне ты оставил всю грязную работу, а себе взял то, что чище и полегче.
С этими словами миссис Джонс взяла список обязанностей по дому и отметила те работы, которые бы ей хотелось взять на себя. Ее муж не согласился с новым распределением обязанностей.
Жанет. Если ты думаешь, что я буду делать всю грязную работу, то ты просто сошел с ума.
Пока супруги пререкались, в дверь позвонили. Это пришла мать миссис Джонс.
Миссис Смит. Из-за чего драка, голубки? Ваши крики слышны на лестнице.
Выслушав доводы Бастера и его жены, миссис Смит улыбнулась.
Миссис Смит. Я нашла великолепное решение. Сейчас я покажу вам, как распределить обязанности по дому, чтобы вы оба остались довольны.
Миссис Смит. Пусть один из вас разделит перечень обязанностей на 2 части, каждую из которых он бы охотно взял на себя, а другой выберет себе любую половину. Тогда обязанности будут распределены в соответствии с желаниями каждого из вас, не так ли?
Но год спустя, когда миссис Смит переехала к молодоженам, ситуация несколько осложнилась. Миссис Смит охотно согласилась взять на себя треть обязанностей по дому, но все трое никак не могли придумать, как справедливо разделить между собой обязанности. Не взялись бы вы им помочь?
Задача о честном разделе, с которой столкнулась чета Джонсов, в книгах по занимательной математике обычно фигурирует, как задача о разделе пирога между двумя людьми, каждый из которых хотел бы заполучить не меньше половины.
Эту задачу мы решили, а вот задача о честном разделе пирога между тремя людьми, каждый из которых хотел бы заполучить не менее трети пирога, осталась нерешенной.
Она допускает следующее решение. Один из любителей пирога медленно ведет большим ножом над пирогом. Пирог может быть любой формы. Вести нож нужно так, чтобы доля пирога по одну сторону ножа непрерывно возрастала от нуля до максимума. Как только любой из трех участников раздела сочтет, что по одну сторону ножа осталась треть пирога, он произносит вслух: «Режь!» Тот, кто держит нож, немедленно отрезает кусок пирога и отдает тому, что подал команду. Если команду «Режь!» подадут одновременно двое или даже трое любителей пирога, отрезанный кусок вручается любому из них.
Двое остальных вполне удовлетворены куском пирога, доставшимся им на двоих: ведь этот кусок составляет не менее ⅔ от всего пирога. Задача о разделе этого куска сводится к предыдущей задаче о честном разделе между двумя претендентами и решается, если один режет, а другой выбирает.
Метод честного раздела допускает очевидное обобщение на случай n участников. Один из участников ведет ножом над пирогом. Первый, кто подаст команду «Режь!», получает первый кусок (если команду подадут сразу несколько человек, отрезанный кусок достается одному из них по жребию). Затем процедура повторяется с n − 1 остальными участниками. Так продолжается до тех пор, пока не останутся 2 участника. Последняя порция пирога делится между ними по принципу «я режу, ты выбираешь», или, если угодно, при помощи все той же универсальной процедуры: один ведет ножом над пирогом, и каждый может скомандовать «Режь!», если сочтет, что по одну сторону ножа осталось не менее ½ порции, доставшейся им на двоих. Общее решение задачи о справедливом разделе может служить прекрасным примером доказательства, проводимого при помощи метода математической индукции. Ясно, что тот же алгоритм справедливого раздела применим и к задаче о распределении домашних обязанностей между n обитателями квартиры, не оставляющем ни у кого ни малейшего повода для неудовольствия.
Математик из Кембриджского университета Джон X. Конуэй рассмотрел задачу о справедливом разделе при гораздо более жестких требованиях. Традиционный алгоритм позволяет каждому участнику получить долю, которую тот считает не меньше причитающейся ему. Существует ли алгоритм, при котором каждый участник будет также пребывать в уверенности, что никому из остальных не достанется больше, чем ему самому? Поразмыслив, вы поймете, что при числе участников больше трех традиционный алгоритм не дает такой уверенности. Конуэй и другие нашли решение задачи для случая, когда число участников с обостренным чувством справедливости равно трем. Для большего числа участников решение, насколько известно, пока не найдено.
