Обезьяна и кокосы - The monkey and the coconuts

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

Общее описание

Обезьяна и кокосы - самый известный представитель класса задач-головоломок, требующих целочисленных решений, структурированных как рекурсивное деление или дробление некоторой дискретно делимой величины с остатками или без них, а также окончательное деление на некоторое количество равных частей, возможно, с остаток. Проблема настолько хорошо известна, что весь класс часто называют «проблемами типа обезьяны и кокоса», хотя большинство из них не имеют непосредственного отношения к проблеме. Другой пример: «У меня есть целое количество фунтов цемента, я не знаю сколько, но после добавления девятого и одиннадцатого он был разделен на 3 мешка, каждый с целым количеством фунтов. Сколько фунтов цемента у меня было? " Проблемы требуют либо начального, либо конечного количества. Заявленное или подразумеваемое - это наименьшее положительное число, которое может быть решением. В таких задачах есть два неизвестных, начальное число и конечное число, но только одно уравнение, которое является алгебраической редукцией выражения для связи между ними. Общим для этого класса является природа результирующего уравнения, которое является линейным диофантовым уравнением с двумя неизвестными. Большинство членов класса детерминированы, но некоторые нет (обезьяна и кокосы - одни из последних). Знакомые алгебраический методы решения таких уравнений отсутствуют.

История

Зарождение класса таких задач приписывают индийскому математику. Махавира в главе VI, §131¹⁄₂, 132​¹⁄₂ его Ганита-сара-санграха («Компендиум по сути математики»), около 850 г. н. Э., В котором говорилось о последовательном делении фруктов и цветов с определенными остатками.^[1] Это сделало бы проблемы-прародители более 1000 лет назад, прежде чем они возродятся в современную эпоху. Проблемы, связанные с разделением, которые вызывают Китайская теорема об остатках появился в китайской литературе еще в первом веке нашей эры. Сунь Цзы спросил: Найдите число, которое оставляет остатки 2,3,2 при делении на 3,5,7 соответственно. Диофант Александрийский впервые изучал проблемы, требующие целочисленных решений в 3 веке нашей эры. Алгоритм Евклида для наибольшего общего делителя, лежащий в основе решения таких задач, был открыт греческим геометром. Евклид и опубликовал в своем Элементы в 300CE.

Проф. Дэвид Сингмастер, историк головоломок, прослеживает серию менее правдоподобных связанных проблем в средние века, с некоторыми ссылками еще на Вавилонскую империю около 1700 г. до н.э. Они включают общую тему сложения или вычитания частей кучи или определенного количества дискретных объектов и вопроса, сколько их могло быть в начале. Следующая ссылка на подобную проблему находится в Жак Озанам с Récréations mathématiques et Physiques, 1725. В области чистой математики, Лагранж в 1770 г. излагал теорема о непрерывной дроби и применил его к решению диофантовых уравнений.

Первое описание задачи в близкой к современной формулировке появилось в дневниках математика и автора. Льюис Кэрролл («Алиса в стране чудес») в 1888 году, когда на столе лежит стопка орехов, поочередно разделенных четырьмя братьями, каждый раз с оставшейся частью одного, отдаваемой обезьяне, и последнее деление получается равным. Проблема никогда не появлялась ни в одной из опубликованных автором работ, хотя, судя по другим ссылкам, проблема была в обращении в 1888 году. Почти идентичная проблема вскоре появилась в W.W. Роуз Болл с Элементарная алгебра, 1890. Такая близость предполагает общий источник; распространение проблемы могло произойти через обмены Кэрролла с Варфоломей Прайс, профессор математики, друг и наставник Кэрролла. Существовали четыре варианта задачи: две формы, одна с остатками от одного, а другая с остатками от нуля, но орехами, отброшенными после деления, и два окончания, в одном из которых последний деление имеет остаток, а в другом - нет (или нет орехов). отбрасываются). Проблема упоминалась в трудах математиков того времени, и их решения, в основном неправильные, указывали на то, что проблема была новой и незнакомой в то время.

Устройство отмеченных объектов (см. Синие кокосы ниже), чтобы помочь в концептуализации деления с остатками, впервые появилось в 1912 году в работе Норман Х. Эннинг с корзиной яблок, разделенной тремя мужчинами.

Проблема стала печально известной, когда американский писатель и новеллист Бен Эймс Уильямс изменил старую задачу и включил ее в рассказ "Кокосы" в номере журнала The Times от 9 октября 1926 г. Субботняя вечерняя почта.^[2] Вот как проблема была сформулирована Уильямсом (сжато и перефразировано):

Пятеро мужчин и обезьяна потерпели кораблекрушение на острове. Первую ночь они провели, собирая кокосы. Ночью один мужчина проснулся и решил съесть свою долю кокосов. Он разделил их на пять стопок. Остался один кокос, поэтому он отдал его обезьяне, затем спрятал свою долю, сложил остальные вместе и снова заснул.

Вскоре проснулся второй мужчина и сделал то же самое. После разделения кокосов на пять стопок остался один кокосовый орех, который он дал обезьяне. Затем он спрятал свою долю, сложил остальное и вернулся в постель. Третий, четвертый и пятый человек проделали точно такую ​​же процедуру. На следующее утро, проснувшись, они разделили оставшиеся кокосы на пять равных частей. На этот раз кокосов не осталось.

Сколько кокосов было в исходной куче?

Уильямс не включил в историю ответ. Журнал был наводнен более чем 2000 писем, в которых просили дать ответ на эту проблему. Редактор поста, Гораций Лоример, как известно, отправил Уильямсу телеграмму, в которой говорилось: «ДЛЯ ЛЮБВИ МАЙКА, СКОЛЬКО КОКОСОВ? АД ЗДЕСЬ ПОПУЛЯЕТ». Уильямс продолжал получать письма с просьбами о решении или предложениями новых на следующие двадцать лет.^[3]

Мартин Гарднер описал проблему в своем апрельском 1958 г. Колонка "Математические игры" в Scientific American. Он заявил, что Уильямс изменил старую проблему, чтобы сделать ее более запутанной. В старой версии на последнем делении есть кокос для обезьяны; в версии Уильямса финальный дивизион утром выходит сравняющим. Но имеющиеся исторические свидетельства не указывают, к каким версиям Уильямс имел доступ.^[4] Гарднер однажды сказал своему сыну Джиму, что это его любимая проблема,^[5] настолько, что позже он решил сделать ее первой главой своего сборника «Лучшие статьи», Колоссальная книга математики.^[3] Он сказал, что «Обезьяна и кокосы» - «вероятно, самая трудная и реже решаемая» диофантова головоломка.^[2] С тех пор версия проблемы Уильямса стала основным продуктом развлекательная математика.^[6] Оригинальный рассказ, содержащий проблему, был полностью перепечатан в Клифтон Фадиман антология 1962 года Математическая сорока,^[7] книга, которая Математическая ассоциация Америки рекомендует к приобретению в математические библиотеки бакалавриата.^[8]

В литературе появилось множество вариантов, в которых варьируется количество моряков, обезьян или количество кокосов, выдаваемых обезьяне (ам).^[9]

Решения

Диофантова проблема

Диофантов анализ это исследование уравнений с рациональными коэффициентами, требующих целочисленных решений. В диофантовых задачах меньше скватонов, чем неизвестных. «Дополнительная» информация, необходимая для решения уравнений, - это условие, что решения должны быть целыми числами. Любое решение должно удовлетворять всем уравнениям. Некоторые диофантовы уравнения не имеют решения, некоторые имеют одно или конечное число, а другие имеют бесконечно много решений.

Обезьяна и кокосы алгебраически сводятся к линейному диофантовому уравнению с двумя переменными, имеющему вид

ах + по = сили, в более общем смысле,

(a / d) x + (b / d) y = c / d

где d это наибольший общий делитель из а и б.^[10] От Личность Безу, уравнение разрешимо тогда и только тогда, когда d разделяет c. Если это так, то уравнение имеет бесконечно много периодических решений вида

х = х₀ + т· б,

у = у₀ + т· а

где (Икс₀,у₀) является решением и т - параметр, который может быть любым целым числом. Проблема не предназначена для решения методом проб и ошибок; существуют детерминированные методы решения (Икс₀,у₀) в этом случае (см. текст).

Многочисленные решения, начиная с 1928 г., были опубликованы как для исходной задачи, так и для модификации Вильямса.^{[11][12][13][14]} Умные и сжатые решения с использованием сравнений по модулю, сит и альтернативных оснований счисления были разработаны, частично или в основном на основе рекурсивного определения проблемы, структуры, которая неприменима в общем случае. Наименьшие положительные решения для обеих версий достаточно велики, так что метод проб и ошибок, скорее всего, будет бесплодным. Была представлена ​​оригинальная концепция отрицательных кокосов, которая случайно решила исходную проблему. Формалистические решения основаны на алгоритме Евклида, примененном к диофантовым коэффициентам. Наконец, исчисление конечных разностей дает параметризованное общее решение для любого количества матросов и всех кратных кокосов, которые могли быть в исходной куче. В наше время компьютерный перебор положительных целых чисел быстро дает решение.

Прежде чем приступить к решению проблемы, можно отметить несколько моментов. Если не было остатков, то есть 6 делений по 5, 5⁶= 15 625 кокосовых орехов должно быть в куче; в 6-м и последнем дивизионе каждый моряк получает 1024 кокоса. Не меньшее положительное число приведет к тому, что все 6 делений получатся четными. Это означает, что в задаче, как указано, к куче может быть добавлено любое кратное 15625, и это будет удовлетворять условиям задачи. Это также означает, что количество кокосов в исходной куче меньше 15625, иначе вычитание 15625 даст меньшее решение. Но число в исходной стопке не так уж и мало, например, 5 или 10 (поэтому это сложная проблема) - оно может быть сотнями или тысячами. В отличие от метода проб и ошибок в случае угадывания корня полинома, метод проб и ошибок для диофантова корня не приведет к какой-либо очевидной сходимости. Нет простого способа оценить, каким будет решение.

Оригинальная версия

Сводный анализ как исходной проблемы, так и версии Уильяма был представлен Мартин Гарднер когда он описал проблему в своей колонке «Математические игры». Гарднер начинает с решения исходной проблемы, потому что она менее сложна, чем вариант Уильямса. Позволять N быть размером с исходную стопку и F быть количеством кокосов, полученных каждым моряком после окончательного деления на 5 равных частей утром. Тогда количество кокосов, оставшихся до утреннего деления, равно F.· 5 + 1. Если это количество обозначено п, число, оставшееся перед последней матросской дивизией:

${\displaystyle n'=n\cdot {\tfrac {5}{4}}+1}$

изменение порядка действий моряка в ночное время. Но каждый моряк следовал одной и той же процедуре; таким образом определяется рекурсивный ряд из 5 таких ${\displaystyle n'}$s (заменяя ${\displaystyle n}$ с участием ${\displaystyle n'}$ и создание нового ${\displaystyle n'}$), пятая и последняя из которых N само количество кокосов до деления первым матросом. Последовательная замена ${\displaystyle n'}$s и ${\displaystyle n}$ дает:

${\displaystyle N=(((((F\cdot 5+1)\cdot {\tfrac {5}{4}}+1)\cdot {\tfrac {5}{4}}+1)\cdot {\tfrac {5}{4}}+1)\cdot {\tfrac {5}{4}}+1)\cdot {\tfrac {5}{4}}+1}$

которое сводится к диофантову уравнению:^[3]

${\displaystyle 1024N=15625F+11529}$

По основной теореме это уравнение имеет решение тогда и только тогда, когда 11529 делится на Наибольший общий делитель из 1024 и 15625. 1024 = 4⁵ и 15625 = 5⁶, поэтому их НОД равен 1, а 11529 делится на 1, так что уравнение разрешимо.

Гарднер отмечает, что это уравнение слишком сложно решить методом проб и ошибок.^[15] Более того, у него бесконечное количество решений. Но Гарднер ошибался относительно трудности. Фактически, если (N, F) это решение, то так (N + 15625 т, F + 1024 т) для любого целого числа т. Это означает, что уравнение также имеет решения в отрицательных целых числах. Попробовав несколько маленьких отрицательных чисел, выяснится, что N = -4 и F = -1 - решение.^[16] Это связано с абсурдным представлением о негативных кокосах; поэтому мы добавляем 15625 к -4 и прибавляем 1024 к -1, чтобы получить наименьшее положительное решение (15621, 1023).^[17]

Версия Вильямса

Подход с отрицательными кокосами неприменим к версии Уильямса, по крайней мере, для любого достаточно небольшого |N|, поэтому необходим более систематический подход.

Использование сита

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

Если F это количество кокосов, которое каждый моряк получает в финальном дивизионе утром, стопка утром - 5F, которое также должно делиться на 4, так как последний матрос ночью сложил 4 стопки для утреннего деления. Итак, утренняя куча, позвони по номеру п, кратно 20. Стопка до того, как проснулся последний моряк, должна была составлять 5/4 (п) +1. Если ночью проснулся только один моряк, то 5/4 (20) +1 = 26 работает для минимального количества кокосов в исходной куче. Но если два матроса проснулись, 26 не делится на 4, поэтому утренняя куча должна быть кратна 20, что дает стопку, делимую на 4, прежде чем проснется последний моряк. Так получилось, что 3 * 20 = 60 работает для двух моряков: применяя формулу рекурсии для п дважды дает 96 как наименьшее количество кокосов в исходной стопке. 96 делится на 4 еще раз, так что при пробуждении 3 матросов куча могла составлять 121 кокосовый орех. Но 121 не делится на 4, поэтому для пробуждения 4 моряков нужно совершить еще один прыжок. В этот момент аналогия становится тупой, потому что для того, чтобы вместить 4 пробуждающихся моряка, утренняя куча должна быть кратной 60: если одна постоянная, можно обнаружить, что 17 * 60 = 1020 подходит и минимальное количество в исходной стопке будет 2496. Последняя итерация 2496 для пробуждения 5 матросов, то есть 5/4 (2496) +1 доводит исходную стопку до 3121 кокоса.

Синие кокосы

Еще один прием, предшествующий этой проблеме, - использование дополнительных или отмеченных объектов, в данном случае голубых кокосов, для уточнения процесса деления. Предположим, что первый моряк перед разделением добавляет четыре синих кокоса в кучу, чтобы гарантировать деление на 5 (поскольку мы знаем, даже если он этого не сделает, остаток будет 1, поэтому добавление 4 делает стопку делимой на 5). Он делит стопку, берет пятую с лишним (не синим) кокосом, который бросает обезьяне, прячет свою долю, затем складывает остальные вместе, откладывая 4 синих кокоса в сторону. Каждый моряк делает то же самое. После пятого матроса (или после разделения утром, если там есть остаток) синие кокосы остаются в стороне и никому не принадлежат. Поскольку исходная куча делится 5 раз (или 6, если утром остается остаток), включая синие кокосы, она должна была быть 5 раз.⁵ (5⁶) кокосы. Получается, что стопка 3125-4 = 3121 (15625-4 = 15621) кокосов. Синие кокосы можно рассматривать как «виртуальные» кокосы, которые не играют никакой роли в проблеме, а служат только для уточнения делимости.^[18]

Нумерация по основанию 5

Простое и очевидное решение появляется, когда деления и вычитания выполняются по основанию 5. Рассмотрим вычитание, когда первый моряк берет свою долю (и долю обезьяны). Пусть n₀, п₁, ... представляют собой цифры N, количество кокосов в исходной стопке и s₀, с₁... представляют цифры доли моряка S, обе с основанием 5. После доли обезьяны младшая цифра N должна теперь быть 0; после вычитания наименее значимая цифра N ', оставленная первым моряком, должна быть 1, отсюда следует следующее (фактическое количество цифр в N, а также S неизвестно, но сейчас они не имеют значения):

п5п4п3п2п1 0 (N5) s4s3s2s1s0   (S5) 1 (N '5)

Цифра, вычитаемая из 0 по основанию 5, чтобы получить 1, равна 4, поэтому s₀= 4. Но поскольку S равно (N-1) / 5, и при делении на 5₅ просто сдвигает число вправо на одну позицию, n₁= s₀= 4. Итак, теперь вычитание выглядит так:

п5п4п3п2 4 0 с4s3s2s1 4          1  

Поскольку следующий моряк собирается проделать то же самое с N ', младшая значащая цифра N' становится 0 после того, как подбрасывает единицу обезьяне, и LSD S 'должен быть 4 по той же причине; следующая цифра N 'также должна быть 4. Итак, теперь это выглядит так:

п5п4п3п2 4 0 с4s3s2s1 4        4 1 

Заимствование 1 от n₁ (а теперь 4) оставляет 3, поэтому s₁ должно быть 4, поэтому n₂ также. Итак, теперь это выглядит так:

п5п4п3 4 4 0 с4s3s2 4 4        4 1  

Но те же рассуждения снова применимы к N 'применительно к N, поэтому следующая цифра N' равна 4, поэтому s₂ и н₃ тоже 4 и т. д. Есть 5 отделов; первые четыре должны оставить нечетное число с основанием 5 в стопке для следующего деления, но последнее деление должно оставить четное число с основанием 5, чтобы утреннее деление получилось четным (через 5 сек). Итак, есть четыре четверки в N после LSD, равного 1: N = 44441₅=3121₁₀

Численный подход

Простой числовой анализ выглядит следующим образом: если N - начальное число, каждый из 5 моряков перемещает исходную кучу таким образом:

N => 4 (N – 1) / 5 или эквивалентно N => 4 (N + 4) / 5 - 4.

Повторение этого перехода 5 раз дает число, оставшееся до утра:

N => 4 (N + 4) / 5 - 4

=> 16 (N + 4) / 25 - 4

=> 64 (N + 4) / 125 - 4

=> 256 (N + 4) / 625 - 4

=> 1024 (N + 4) / 3125 - 4

Поскольку это число должно быть целым числом, а 1024 является относительно простым числом 3125, N + 4 должно быть кратным 3125. Наименьшее такое кратное число равно 3125· 1, поэтому N = 3125-4 = 3121; число, оставшееся на утро, составляет 1020, что при необходимости делится на 5 без остатка.

По модулю сравнения

Простое лаконичное решение может быть получено путем прямого использования рекурсивной структуры задачи: кокосовые орехи делятся на пятые части, каждый раз оставляя одну (отложив последнее деление утром). В стопке, оставшейся после каждого деления, должно быть целое количество орехов. Если бы такое деление было только одно, то очевидно, что 5· 1 + 1 = 6 - решение. Фактически решение, кратное пяти плюс один, так что возможная общая формула равна 5.· k - 4, так как число, кратное 5 плюс 1, также кратно 5 минус 4, поэтому 11, 16 и т. Д. Также подходят для одного деления.^[19]

Если сделано два деления, кратное 5· Следует использовать 5 = ​​25, а не 5, потому что 25 можно дважды разделить на 5. Таким образом, количество кокосов, которые могут быть в куче, равно k · 25 - 4.k= 1, что дает 21, является наименьшим положительным числом, которое можно последовательно разделить на 5 дважды с остатком 1. Если делений 5, то делится на 5⁵= 3125 обязательны; наименьшее такое число - 3125 - 4 = 3121. После 5 делений остается 1020 кокосов, число делится на 5, как того требует задача. Фактически, после п делений, можно доказать, что оставшаяся куча делится на п, свойство, удобное для использования создателем задачи.

Формальный способ сформулировать приведенный выше аргумент:

Первоначальная стопка кокосов будет разделена на 5 в общей сложности 5 раз, а остаток - 1 раз, не считая последнего деления утром. Пусть N = количество кокосов в исходной стопке. Каждое деление должно оставлять количество орехов одного и того же класса конгруэнтности (модификатор 5). Так,

${\displaystyle N\equiv 4/5\cdot (N-1)}$ (mod 5) (-1 - это орех, брошенный обезьяне)

${\displaystyle 5N\equiv 4N-4}$ (мод 5)

${\displaystyle N\equiv -4}$ (mod 5) (–4 - класс сравнения)

Итак, если мы начали с орехов по модулю класса –4, то мы останемся в классе по модулю –4. Поскольку в конечном итоге мы должны разделить стопку 5 раз или 5 ^ 5, исходная стопка была 5 ^ 5 - 4 = 3121 кокосовый орех. Остаток 1020 кокосов удобно равномерно разделить на 5 часов утра. Это решение существенно меняет то, как (вероятно) была построена проблема.

Диофантово уравнение и формы решения

Эквивалентное диофантово уравнение для этой версии:

${\displaystyle 1024N=15625F+8404}$ (1)

где N исходное количество кокосов, и F это число, полученное каждым матросом в последней дивизии утром. Это лишь тривиально отличается от приведенного выше уравнения для предшествующей задачи, и разрешимость гарантируется теми же рассуждениями.

Повторный заказ,

${\displaystyle 1024N-15625F=8404}$ (2)

Это диофантово уравнение имеет решение, которое непосредственно следует из Евклидов алгоритм; на самом деле она имеет бесконечно много периодических решений, положительных и отрицательных. Если (x₀, y₀) является решением 1024x – 15625y = 1, то N₀= х₀ · 8404, Ф₀= y₀ · 8404 является решением (2), что означает, что любое решение должно иметь вид

${\displaystyle {\begin{cases}N=N_{0}+15625\cdot t\\F=F_{0}+1024\cdot t\end{cases}}}$

где ${\displaystyle t}$ - произвольный параметр, который может иметь любое целое значение.

Редукционистский подход

Можно взять обе части (1) выше по модулю 1024, поэтому

${\displaystyle 1024N=15625F+8404\mod 1024}$

Другой способ думать об этом - чтобы ${\displaystyle n}$ чтобы быть целым числом, правая часть уравнения должна быть целым кратным 1024; это свойство не изменится, если вынести из RHS как можно больше чисел, кратных 1024. Уменьшая обе стороны кратно 1024,

${\displaystyle 0=(15625F-15\cdot 1024F)+(8404-8\cdot 1024)\mod 1024}$

вычитание,

${\displaystyle 0=265F+212\mod 1024}$

факторинг,

${\displaystyle 0=53\cdot (5F+4)\mod 1024}$

RHS по-прежнему должен быть кратным 1024; поскольку 53 является относительно простым числом 1024, 5F+4 должно быть кратно 1024. Наименьшее из таких кратных - 1.· 1024, поэтому 5F+ 4 = 1024 и F = 204. Подставляя в (1)

${\displaystyle 1024N=15625\cdot 204+8404\Rightarrow N={\frac {3195904}{1024}}\Rightarrow N=3121}$

Евклидов алгоритм

Алгоритм Евклида довольно утомителен, но общая методология решения рациональных уравнений ax + by = c требует интегральных ответов. Из (2) видно, что 1024 (2¹⁰) и 15625 (5⁶) взаимно просты, и поэтому их НОД равен 1, но нам нужны уравнения редукции для обратной подстановки, чтобы получить N и F в терминах этих двух величин:

Сначала получите последовательные остатки, пока не останется НОД:

15625 = 15 · 1024 + 265 (а)

1024 = 3 · 265 + 229 (б)

265 = 1 · 229 + 36 (с)

229 = 6 · 36 + 13 (г)

36 = 2 · 13 + 10 (е)

13 = 1 · 10 + 3 (ж)

10 = 3 · 3 + 1 (г) (остаток 1 - это НОД 15625 и 1024)

1 = 10 - 3 (13–1 · 10) = 4 · 10 - 3 · 13 (переставить (g), заменить 3 из (f) и объединить)

1 = 4 · (36 - 2 · 13) - 3 · 13 = 4 · 36 - 11 · 13 (замените 10 из (e) и объедините)

1 = 4 · 36 - 11 · (229 - 6 · 36) = –11 · 229 + 70 * 36 (замените 13 из (d) и объедините)

1 = –11 · 229 + 70 · (265 - 1 · 229) = –81 · 229 + 70 · 265 (замените 36 из (c) и объедините)

1 = –81 · (1024 - 3 · 265) + 70 · 265 = –81 · 1024 + 313 · 265 (замените 229 из (b) и объедините)

1 = –81 · 1024 + 313 · (15625 - 15 · 1024) = 313 · 15625 - 4776 · 1024 (замените 265 из (a) и объедините)

Итак, пара (N₀, F₀) = (–4776 · 8404 313 * 8404); наименьший ${\displaystyle t}$ (см. (3) в предыдущем подразделе), который сделает как N, так и F положительными, равно 2569, поэтому:

${\displaystyle N=N_{0}+15625\cdot 2569=3121}$

Непрерывная дробь

Как вариант, можно использовать непрерывную дробь, построение которой основано на алгоритме Евклида. Непрерывная дробь для¹⁰²⁴⁄₁₅₆₂₅ (Точно 0,065536) равно [; 15,3,1,6,2,1,3];^[20] его конвергент прекращается после того, как повторение³¹³⁄₄₇₇₆, давая нам x₀= –4776 и y₀= 313. Наименьшее значение т для которого как N, так и F неотрицательны, равно 2569, поэтому

${\displaystyle N=-4776\cdot 8404+15625\cdot 2569=3121}$.

Это наименьшее положительное число, удовлетворяющее условиям задачи.

Обобщенное решение

Когда количество моряков является параметром, пусть это будет ${\displaystyle m}$тщательное алгебраическое сокращение отношения между количеством кокосов в исходной куче и количеством, назначенным каждому матросу утром, дает аналогичное диофантово соотношение, коэффициенты которого являются выражениями в ${\displaystyle m}$.

Первый шаг - получить алгебраическое разложение рекуррентного соотношения, соответствующего каждому матросовому преобразованию сваи, ${\displaystyle n_{i}}$ число, оставленное моряком:

${\displaystyle n_{i}={\frac {m-1}{m}}(n_{i-1}-1)}$

где ${\displaystyle n_{i\rightarrow 0}\equiv N}$, первоначально собранное число и ${\displaystyle n_{i\rightarrow m}}$ номер уехал утром. Расширение повторяемости путем замены ${\displaystyle n_{i}}$ для ${\displaystyle n_{i-1}}$ ${\displaystyle m}$ раз дает:

${\displaystyle n_{m}=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-\left[({\frac {m-1}{m}})^{m}+...+({\frac {m-1}{m}})^{2}+{\frac {m-1}{m}}\right]}$

Учитывая последний термин,

${\displaystyle n_{m}=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-\left({\frac {m-1}{m}}\right)\cdot \left[({\frac {m-1}{m}})^{m-1}+...+{\frac {m-1}{m}}+1\right]}$

Многочлен степенного ряда в скобках вида ${\displaystyle x^{m-1}+...+x+1}$ суммы в ${\displaystyle (1-x^{m})/(1-x)}$ так,

${\displaystyle n_{m}=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-\left({\frac {m-1}{m}}\right)\cdot \left[\left(1-({\frac {m-1}{m}})^{m}\right){\bigg /}\left(1-({\frac {m-1}{m}})\right)\right]}$

что упрощает:

${\displaystyle n_{m}=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-(m-1)\cdot {\frac {m^{m}-(m-1)^{m}}{m^{m}}}}$

Но ${\displaystyle n_{m}}$ число, оставшееся утром, кратное ${\displaystyle m}$ (т.е. ${\displaystyle F}$, номер, присвоенный каждому матросу утром):

${\displaystyle m\cdot F=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-(m-1)\cdot {\frac {m^{m}-(m-1)^{m}}{m^{m}}}}$

Решение для ${\displaystyle n_{0}}$(=${\displaystyle N}$),

${\displaystyle N=m^{m}\cdot {\frac {m-1+m\cdot F}{(m-1)^{m}}}-(m-1)}$

Уравнение представляет собой линейное диофантово уравнение с двумя переменными, ${\displaystyle N}$ и ${\displaystyle F}$. ${\displaystyle m}$ - параметр, который может быть любым целым числом. Характер уравнения и метод его решения не зависят от ${\displaystyle m}$.

---

Теперь применимы соображения теории чисел. Для ${\displaystyle N}$ чтобы быть целым числом, достаточно, чтобы ${\displaystyle {\frac {m-1+m\cdot F}{(m-1)^{m}}}}$ быть целым числом, так пусть будет ${\displaystyle r}$:

${\displaystyle r={\frac {m-1+m\cdot F}{(m-1)^{m}}}}$

Уравнение необходимо преобразовать к виду ${\displaystyle ax+by=\pm 1}$ решения которых являются формульными. Отсюда:

${\displaystyle (m-1)^{m}\cdot r-m\cdot s=-1}$, где ${\displaystyle s=1+F}$

Потому что ${\displaystyle m}$ и ${\displaystyle m-1}$ взаимно просты, существуют целочисленные решения ${\displaystyle (r,s)}$ по личности Безу. Это уравнение можно переформулировать так:

${\displaystyle (m-1)^{m}\cdot r\equiv -1\mod m}$

Но (м–1)^м это многочлен Z · м–1, если м это странно и Z · м+1 если м четный, где Z - многочлен с мономиальным базисом в м. Следовательно р₀= 1, если м это странно и р₀= –1, если м это даже решение.

---

Тождество Безу дает периодическое решение ${\displaystyle r=r_{0}+k\cdot m}$, поэтому заменяя ${\displaystyle r}$ в диофантовом уравнении и переставив:

${\displaystyle N=r_{0}\cdot m^{m}-(m-1)+k\cdot m^{m+1}}$

где ${\displaystyle r_{0}=1}$ для ${\displaystyle m}$ странно и ${\displaystyle r_{0}=-1}$ для ${\displaystyle m}$ даже и ${\displaystyle k}$ любое целое число.^[21] Для данного ${\displaystyle m}$, самый маленький положительный ${\displaystyle k}$ будет выбран так, что ${\displaystyle N}$ удовлетворяет ограничениям постановки задачи.

В версии проблемы Уильяма ${\displaystyle m}$ 5 моряков, так что ${\displaystyle r_{0}}$ равно 1, а ${\displaystyle k}$ можно принять равным нулю для получения наименьшего положительного ответа, поэтому N = 1  · 5⁵ - 4 = 3121 для количества кокосов в исходной стопке. (Можно отметить, что следующее последовательное решение уравнения для k= –1, равно –12504, поэтому метод проб и ошибок около нуля не решит версию задачи Вильямса, в отличие от исходной версии, уравнение которой, к счастью, имело отрицательное решение небольшой величины).

Вот таблица положительных решений ${\displaystyle N}$ для первых нескольких ${\displaystyle m}$ (${\displaystyle k}$ любое неотрицательное целое число):

${\displaystyle m}$	${\displaystyle N}$
2	${\displaystyle 11+k\cdot 8}$[22]
3	${\displaystyle 25+k\cdot 81}$
4	${\displaystyle 765+k\cdot 1024}$
5	${\displaystyle 3121+k\cdot 15,625}$
6	${\displaystyle 233,275+k\cdot 279,936}$
7	${\displaystyle 823,537+k\cdot 5,764,801}$
8	${\displaystyle 117,440,505+k\cdot 134,217,728}$

Другие варианты и общие решения

Другие варианты, включая предполагаемую проблему предшественника, имеют связанные общие решения для произвольного количества моряков.

Когда в утреннем делении есть остаток от единицы, решение следующее:

${\displaystyle N=-(m-1)+k\cdot m^{m+1}}$

Для ${\displaystyle m=5}$ и ${\displaystyle k=1}$ это дает 15 621 как наименьшее положительное число кокосов для версии задачи до Уильяма.

В некоторых более ранних альтернативных формах задачи деления выходили равномерно, а орехи (или предметы) выделялись из оставшейся стопки. после деление. В этих формах отношение рекурсии:

${\displaystyle n_{i}={\frac {m-1}{m}}n_{i-1}-1}$

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

${\displaystyle N=-m+k\cdot m^{m+1}}$

Например, когда ${\displaystyle m=4}$ и ${\displaystyle k=1}$, исходная куча состоит из 1020 кокосов, и после четырех последовательных делений в ночь с выделением кокосового ореха обезьяне после каждого деления, утром остается 80 кокосов, так что последнее деление получается даже без кокосов. .

Когда в результате утреннего деления остается орех, общее решение:

${\displaystyle N=r_{0}\cdot m^{m}-m+k\cdot m^{m+1}}$

где ${\displaystyle r_{0}=-1}$ если ${\displaystyle m}$ странно, и ${\displaystyle r_{0}=1}$ если ${\displaystyle m}$ даже. Например, когда ${\displaystyle m=3}$, ${\displaystyle r_{0}=-1}$ и ${\displaystyle k=1}$, исходная куча состоит из 51 кокоса, и после трех последовательных делений в ночи с кокосом, выделенным обезьяне после каждого деления, утром остается 13 кокосовых орехов, поэтому в последнем делении остается кокосовый орех для обезьяны.

Другие варианты пост-Вильямса, которые определяют другие остатки, включая положительные (например, обезьяна добавляет кокосы в кучу), рассматривались в литературе. Решение:

${\displaystyle N=r_{0}\cdot m^{m}-c\cdot (m-1)+k\cdot m^{m+1}}$

где ${\displaystyle r_{0}=1}$ для ${\displaystyle m}$ странно и ${\displaystyle r_{0}=-1}$ для ${\displaystyle m}$ даже, ${\displaystyle c}$ остаток после каждого деления (или количества обезьян) и ${\displaystyle k}$ любое целое число (${\displaystyle c}$ отрицательно, если обезьяны добавляют в кучу кокосы).

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

Смотрите также

• Проблема архимеда о скоте, существенно более сложная диофантова проблема
• Последняя теорема Ферма, возможно, самое известное диофантово уравнение из всех
• Проблема с пушечным ядром

использованная литература

1. ХРОНОЛОГИЯ РЕКРЕАЦИОННОЙ МАТЕМАТИКИ Дэвида Сингмастера [1]
2. Уличный (2005)
3. Гарднер (2001)
4. Антоник (2013)
5. Антоник (2013): «Затем я спросил Джима, есть ли у его отца любимая головоломка, и он почти сразу ответил:« Обезьяны [sic] и кокосы. Он очень любил это ».
6. Вольфрам Mathworld
7. КИРКУС: ОБЗОР "Математической сороки" 27 июля 1962 г.
8. Математическая сорока, Клифтон Фадиман, Математическая ассоциация Америки, Спрингер, 1997 г.
9. Паппас, Т. «Обезьяна и кокосы». Радость математики. Сан-Карлос, Калифорния: Wide World Publ./Tetra, стр. 226-227 и 234, 1989.
10. d при необходимости можно найти через Алгоритм Евклида
11. Андервуд Р. С. и Роберт Э. Мориц. "3242." Американский математический ежемесячник 35, вып. 1 (1928): 47-48. DOI: 10.2307 / 2298601.
12. Киршнер, Роджер Б. «Обобщенная проблема кокоса», The American Mathematical Monthly 67, вып. 6 (1960): 516-19. DOI: 10.2307 / 2309167.
13. С. Сингх и Д. Бхаттачарья, «О делении кокосов: линейная диофантова проблема», The College Mathematics Journal, май 1997 г., стр. 203–204.
14. Г. Сальваторе и Т. Шима, «О кокосах и целостности», Crux Mathematicorum, 4 (1978) 182–185
15. Гарднер (2001) стр. 4: «Уравнение слишком сложно решить методом проб и ошибок, и хотя существует стандартная процедура для его решения с помощью хитроумного использования непрерывных дробей, этот метод долгий и утомительный».
16. Богомольный (1996)
17. Гарднер (2001) стр. 5: «Это решение иногда приписывают физику из Кембриджского университета П.А.М. Дираку (1902–1984), но в ответ на мой вопрос профессор Дирак написал, что он получил решение от Дж. Х. К. Уайтхеда, профессора математики (и племянника известного философа). Профессор Уайтхед, отвечая на аналогичный вопрос, сказал, что получил это от кого-то другого, и я больше не занимался этим вопросом ».
18. Более простой иллюстрацией этого устройства является более старая проблема человека, который завещает своим трем сыновьям 17 лошадей, указывая, что старший сын получает половину, следующий сын - третья, а младший сын - девятый. Сыновья сбиты с толку, поэтому они советуются с мудрым торговцем лошадьми. Он говорит: «Возьми мою лошадь». Сыновья должным образом делят лошадей, обнаруживая, что все подразделения выходят ровно, с одной остающейся лошадью, которую они возвращают торговцу.
19. Особый случай - когда k= 0, поэтому начальная стопка содержит -4 кокоса. Это работает, потому что после того, как вы подбросите обезьяне один положительный кокос, в куче будет -5 кокосов. После деления остается -4 кокоса. Сколько бы таких делений ни было сделано, в оставшейся стопке будет -4 кокоса. Это математическая аномалия, называемая «фиксированной точкой». Лишь у нескольких проблем есть такая точка, но когда она есть, ее намного легче решить. Все решения проблемы кратны 5, добавляются к фиксированной точке или вычитаются из нее.
20. Увидеть Вот для изложения метода.
21. Гарднер дает эквивалентную, но довольно загадочную формулировку, необъяснимо выбрав неканонический ${\displaystyle r_{0}=-1+1\cdot m}$ когда ${\displaystyle m}$ четное, а затем рефакторинг выражения таким образом, чтобы скрыть периодичность:

    для ${\displaystyle m}$ странный,${\displaystyle N=(1+m\cdot k)\cdot m^{m}-(m-1)}$

    для ${\displaystyle m}$ даже, ${\displaystyle N=(m-1+m\cdot k)\cdot m^{m}-(m-1)}$

    где ${\displaystyle k}$ - параметр, который может быть любым целым числом.
22. В то время как N= 3 удовлетворяет уравнению, 11 - наименьшее положительное число, которое дает каждому моряку ненулевое положительное количество кокосов на каждом делении, что является неявным условием задачи.

Источники

• Антоник, Гэри (2013). Мартин Гарднер "Обезьяна и кокосы" в Numberplay Газета "Нью-Йорк Таймс:, 7 октября 2013 г.
• Pleacher, Дэвид (2005). Проблема недели: обезьяна и кокосы 16 мая 2005 г.
• Гарднер, Мартин (2001). Колоссальная книга математики: классические головоломки, парадоксы и задачи W.W. Norton & Company; ISBN  0-393-02023-1
• Папас, Теони (1993). Радость математики: открывать для себя математику повсюду | Издательство Wide World Publishing, 23 января 1993 г., ISBN  0933174659
• Вольфрам Mathworld: Проблема с обезьяной и кокосом
• Киршнер, Р. Б. "Обобщенная проблема кокоса". Амер. Математика. Ежемесячно 67, 516-519, 1960.
• Фадиман, Клифтон (1962). Математическая сорока, Саймон и Шустер
• Богомольный Александр (1996) Отрицательные кокосы по завязке

внешние ссылки

• Обезьяны и кокосы - Numberphile видео
• Кокосы, копия истории в том виде, в котором она была опубликована в газете «Saturday Evening Post»