Текст набран по книге М. Гарднер, "Математические головоломки и развлечения", М., Мир, 1971. Стр. 233.
Мартышка и кокосовые орехи
9 октября 1926 года в газете "Сатердей ивнинг пост" был напечатан небольшой рассказ Б. Э. Уильямса под названием "Кокосовые орехи". Сюжет этого рассказа сводился к тому, что некий строительный подрядчик хотел во что бы то ни стало помешать своему конкуренту получить важный заказ. Находчивый клерк подрядчика, зная страсть конкурента к занимательной математике, подсунул тому задачу настолько захватывающего содержание, что бедный конкурент, всецело поглощённый её решением, забыл подать заявку в установлённый срок и упустил контракт.
Вот эта задача в том виде, как её сформулировал клерк из рассказа Уильямса.
Пять матросов и мартышка потерпели кораблекрушение и высадились на необитаемом острове. Весь первый день они занимались сбором кокосовых орехов. Вечером они сложили все орехи в кучу и легли спать.
Ночью, когда все заснули, один из матросов встал. Он подумал, что утром при разделе орехов может вспыхнуть ссора, и решил взять свою долю орехов немедля. Поэтому он разделил все кокосовые орехи на пять равных кучек, а один оставшийся орех отдал мартышке. Затем он спрятал свою долю, а все остальные орехи снова сложил в одну кучу.
Через некоторое время проснулся другой "Робинзон" и сделал то же самое. У него тоже остался один лишний орех, и он отдал его мартышке. И так один за другим поступили все пятеро потерпевших кораблекрушение. Каждый из них взял себе одну пятую орехов из той кучи, которую он нашёл при пробуждении, и каждый отдал один орех мартышке. Утром они поделили оставшиеся орехи, и каждому досталось поровну - по одной пятой. Разумеется, каждый из матросов не мог не знать, что часть орехов не хватает, но так как у каждого из них совесть была одинаково нечиста, то никто ничего не сказал. Сколько кокосовых орехов было первоночально?
В рассказе Уильямса ответа не давалось. Говорят, что уже в течения первой недели после опубликования рассказа редакция "Сатердей ивнинг пост" получила около 2000 писем. Джордж Х. Лоример, занимавший в то время пост главного редактора газеты, направил Уильямсу следующую историческую телеграмму: Ради бога, сообщите, сколько было орехов. В редакции творится чёрт знает что.
В течение 20 лет Ульямс продолжал получать письма либо с просьбой сообщить ответ, либо с новыми решениями. В настоящие время задача о кокосовых орехах принадлежит к числу наиболие часто решаемых, но наименее поддающихся решению диофантовых головоломок (термин "диофантово уравнение" происходит от имени Диофанта Александрийского, греческого математика, который впервые подробно исследовал уравнения, допускающие решение в рациональных числах).
Задачу о кокосовых орехов придумал не Ульямс. Он лишь видоизменил уже известно до него задачу, чтобы сильнее запустить её. Более старая версия задачи почти полностью совпадают с приведенной в рассказе Уильямса. Единственное различие заключается в том, что утром при окончательном разделе орехов в старом варианте задача один орех снова оказывается лишним и достаётся мартышке, в то время как в рассказе окончательный раздел производится точно, без остатка. Некоторые диофантовы уравнение имеют лишь одно решение
(например, уравнение х2+2 = у3); другие
допускают конечно число решений, третьи (например, уравнение
х3 +y3=z3) не имеют одно решение.
Задача о кокосовых орехах и в изложении Ульимса, и в формулировке его предшественников допускает бесконечно много решений в целых числах. Наша задача состоит в том, чтобы найти среди них наименьшее положительное число.
Более старый вариант задачи можно свести к следующим шести неопределённым уравнениям.
N = 5A +1,
4A = 5B+1,
4B= 5C+1,
4С =5D +1,
4D= 5E+1,
4Е =5F +1.
Смысл каждого из этих уравнений очевиден: имеющееся количество орехов делят на пять частей (причём эту операцию проделывают шесть раз). Буква N означает первоначальное число орехов, буква F - число орехов, которое получил каждый моряк при окончательном разделе, единицы в правых частях уравнений - те орехи, которые достались мартышки, а каждая из букв - некоторое (пока неизвестно) целое положительное число.
С помощью хорошо известных из алгебры приемов эти уравнения нетрудно свести к одному диофантову уравнению с двумя неизвестными: 1024N= 15 625F +11 529.
Это уравнения слишком сложно, чтобы решать его методом проб и ошибок. Существует стандартный метод его решения, основанный на остроумном использовании непрерывных дробей, однако он приводит к длинным и громоздким вкладкам. Мы же рассмотрим здесь на первый взгляд бессмысленное и невероятное, но изящное и простое решение, в котором используется понятие об отрицательном число кокосовых орехов. Это решение иногда приписывают физика из Кембриджа Полю А. М.Дираку, однако в ответ на мой вопрос профессор Дирак написал, что ему решения сообщил Дж. Г. К.Уайтхэд, профессор
математика из Оксфорда (и племянник знаменитого философа). Профессор Уайтхэд в ответ на аналогичный вопрос заявил, что он узнал решения от кого-то ещё, и я не сал заниматься дальнейшим расследованием.
Независимо от того, кому первому пришла в голову мысль об отрицательных кокосовых орехах, рассуждать он мог примерно так. Поскольку шесть раз делили на пять кучек, ясно, что, прибавив число 56 (то есть 15 625) к любому ответу, мы получим другой, больший ответ. Более того, к решению задачи можно прибавлять кратное число 56 (при этом мы получим новое решение), и точно так же из решения можно вычитать любое кратное числа 56. Вычитая кратные, 56, мы в конце концов получим бесконечно много решений задачи в отрицательных числах. Все они будут удовлетворять исходному уравнению, но не будут удовлетворять первоначальной задаче, поскольку её решение должно быть целым положительным числом.
Очевидно, что небольшого положительного значения N, которое бы удовлетворяло условия задачи, не существует. Может быть, простое решение удастся найти в отрицательных числах? Простым подбором можно без особого труда обнаружить удивительный факт: такое решение действительно существует. Это N = - 4. Убедимся в том что число в самом деле удовлетворяет все условия задачи.
Первый моряк подходит к куче, в которой имеется - 4 кокосовых ореха, бросает один (положительный) кокосовый орех мартышке (получает мартышка свой орех до или после того, как вся куча будет разделена на пять частей, роли не играет). Таким образом, в куче оказывается -5 орехов. Это количество он раскладывает на пять кучек, по -1 ореху в каждой. Затем он прячет -1 орех, после чего остаётся -4 кокосовых ореха - ровно столько, сколько было вначале!
Следующий моряк проделывает то же ритуал с несуществующими орехами, и после окончательного раздела "имущества" у каждого моряка оказывается по - 2 ореха. В само лучшем положении при таком "пополнении запасов наоборот" оказывается мартышка: она умчится, получив свои +6 орехов! Чтобы найти ответ, то есть наименьшее целое положительное число, удовлетворяющее данным задачи, нам остаётся только прибавить 15625 к -4 и получить решение: 15621.
Этот же подход к задаче позволяет сразу же дать общее решение для случая n моряков, каждый из которых, разделив лежащие перед ним орехи на n равных частей, берёт себе одну n-ю. Когда моряков четверо, мы начинаем с - 3 кокосовых орехов и прибавляем 43. Если моряков шестеро, мы начинаем с -5 орехов и прибавляем 67. Аналогично можно поступать и при других значениях n. Рассуждая более формально, можно записать, что первоначально число кокосовых орехов равно k(nn+1)-m(n-1), где n - число людей, m - число орехов, отдаваемых мартышке при каждом разделе, a k - произвольное целое число, называемое параметром. Когда n = 5, a m = 1, наименьшее положительное решение (в целых числах) мы получим, положив параметр k равным 1.
К сожалению, столь необычный метод решения неприменим к том варианту задачи, который приводится в рассказе Уильямса, когда при последнем разделе орехов мартышка не получает ничего. Найти решение для этого случая я предоставляю тем читателям, которых это интересует. Разумеется, его можно найти с помощью обычных методов решения дифантовых уравнений, однако можно намного быстрее прийти к ответу, воспользовавшись тем, что уже известно из только что разобранного варианта. Для тех, кто находит, что и это слишком трудно, приводим очень простую задачу о кокосовых орехах, свободную от всех трудностей решения диофантовых уравнений.
Три моряка, бродя по острову, нашли кучу кокосовых орехов. Первый из них взял себе половину всех орехов и ещё пол-ореха, второй - половину того, что осталось, и ещё пол-ореха, и, наконец, третий также взял половину остатка и ещё пол-ореха. Остался ровно один орех, который они и отдали мартышке. Сколько орехов было в куче, когда моряки набрели на неё? Вооружившись 20 спичками, вы получите удобный материал для решения задачи подбором (методом проб и ошибок)
* * *
Если использование "отрицательных" кокосовых орехов для решение старого варианта задачи Уильямса кажется не вполне законным, то по существу тот же самый трюк проделать, выкрасив четыре кокосовых ореха в синей цвет. Впервые раскрашивание как способ решения задачи было открыто ещё в 1912 году профессором Н. Эннингом. В его задаче 3 человека делили между собой яблоки. Применительно к задаче о кокосовых орехах способ Эннинга заключается в следующем.
Начнём с 5 орехов. Это наименьшее число орехов, которое можно разделить на пять равных частей, забрать одну пятую и повторить этот процесс шесть раз подряд, не отдавая ни одного ореха мартышке. Окрасим четыре из 5 орехов в синей цвет и отложим их в сторону. Разделив оставшееся количество орехов на пять одинаковых частей, мы получим орех, который достанется мартышке.
После того как первый моряк возьмёт свою долю, а мартышка получит свой орех, вернём четыре синих ореха в общую кучу, в которой будет 5 орехов. Это число, очевидно, делится на 5 нацело Однако, прежде чем производить деление, отложе снова четыре синих орех в сторону. Тогда, вторично разделив орехи на пять равных кучек, мы снова обнаружим один лишний орех и отдадим его мартышке.
Эта процедура - прибавление синих орехов только для того, чтобы убедится, что число орехов в очерёдной куче нацело делится на 5, и последующее откладывание их в сторону - повторяется каждый раз. Выполнив её в шестой и последний раз, мы увидим, что синие орехи остались лежать в стороне. Они не достались никому. В наших манипуляциях с орехами они не играют особо важной роли, но помогают нам лучше понимать то, что при этом происходит.
Тем, кого интересуют стандартный метод решения диофантовых уравнений первой степени с помощью непрерывных дробей, можно порекомендовать чёткое изложения этого метода в книге Элен Мерил*. Его полезно знать всем любителям занимательных задач, поскольку многие известные головоломки основаны на уравнениях именно такого типа (см., например, задачу 8 в главе 29). Существуют и другие, весьма разнообразные методы решения задач о кокосовых орехах, в частности один из методов использует числовую систему с основанием 5, но все они слишком сложны для того, чтобы на них стоило останавливаться.
Ответы
Число кокосовых орехов в принадлежащем Уильямса варианте задачи равно 3121. Из разбора старой задачи известно, что 56 - 4 = 3121 есть наименьшее число орехов, которое можно пять раз делить на пять равных долей, отдавая при каждом делении один кокосовый орех мартышке. После пятикратного деления останется 1020 орехов. Это число делится на 5 нацело, что и позволяет произвести шестое деление на пять равных частей так, чтобы обезьяна не получила ни одного ореха.
В этом варианте задачи более общее решение записывается в виде двух диофантовых уравнений. При нечётном числе людей n следует брать уравнение
Число кокосовых орехов = (1+nk)nn-(n-1),
при чётном -
Число кокосовых орехов = (n-1+nk)nn-(n-1).
Величина k и в том и в другом уравнении означает параметр, который может принимать любые целые значение. В задачи Уильямса число людей равно 5 (нечётное число), следовательно, 5 следует подставить вместо n в первом уравнение. Чтобы получить наименьшее положительное решение, параметр kследует выбрать равным 0.
Более простая задача о трёх моряках, помещённая в конце главы, имеет ответ: 15 кокосовых орехов. Если вы попытаетесь решать её, разламывая спички на две половинке, чтобы обозначить половинки кокосовых орехов, то у вас может сложиться впечатление, что задача вообще неразрешима. На самом деле для того, чтобы выполнить все указание в условие задачи операции, разбивать кокосовые орехи совсем не нужно.
* H. Merrill, Mathematical Excursions, Dover paperback, 1957. См. также книгу: А. Я. Хинчин, Цепные дроби, М.- Л., Гостехиздат, 1949
Текст с книжки набрал Никита Скляревский
|
