Обезьяна и кокосы

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

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

Проблему можно выразить так:

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

Сколько кокосов было в первоначальной куче?

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

Другой пример: «У меня есть целое количество фунтов цемента, я не знаю сколько, но после сложения девятого и одиннадцатого оно было разделено на 3 мешка, в каждом по целому числу фунтов. Сколько фунтов цемента у меня было?»

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

История

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

Профессор Дэвид Сингмастер , историк головоломок, прослеживает ряд менее правдоподобно связанных между собой проблем на протяжении средневековья, с некоторыми упоминаниями еще о Вавилонской империи примерно в 1700 году до нашей эры. Они связаны с общей темой сложения или вычитания частей стопки или определенного количества отдельных объектов и вопроса, сколько их могло быть вначале. Следующая ссылка на подобную проблему находится в книге Жака Озанама « Математические и физические упражнения» (1725). В области чистой математики Лагранж в 1770 году изложил свою теорему о непрерывной дроби и применил ее к решению диофантовых уравнений.

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

Проблема стала печально известной, когда американский писатель и автор рассказов Бен Эймс Уильямс модифицировал старую задачу и включил ее в рассказ «Кокосы» в номере « Saturday Evening Post» от 9 октября 1926 года . Вот как проблему сформулировал Уильямс (сокращенно и перефразировано):

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

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

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

Сколько кокосов было в первоначальной куче?

Уильямс не включил в историю ответ. Журнал был завален более чем 2000 письмами с просьбой найти ответ на проблему. The Post Редактор Хорас Лоример , как известно, отправил Уильямсу телеграмму, в которой говорилось: «ИЗ ЛЮБВИ МАЙКА, СКОЛЬКО КОКОСОВ? Уильямс продолжал получать письма с просьбой найти решение или предложить новые в течение следующих двадцати лет.

Мартин Гарднер описал эту проблему в своей колонке «Математические игры» в журнале Scientific American в апреле 1958 года . По словам Гарднера, Уильямс модифицировал старую задачу, сделав ее еще более запутанной. В старой версии в последнем дивизионе для обезьяны есть кокос; в версии Уильямса финальное утреннее разделение оказывается равным. Но имеющиеся исторические свидетельства не указывают, к каким версиям имел доступ Уильямс. Гарднер однажды сказал своему сыну Джиму, что это его любимая задача. Он сказал, что «Обезьяна и кокосы» — это «вероятно, самая прорабатываемая и реже всего решаемая» диофантова головоломка. С тех пор версия задачи Уильямса стала основой развлекательной математики . Оригинальный рассказ, содержащий задачу, был полностью перепечатан в антологии Клифтона Фадимана 1962 года «Математическая сорока» . книга, которую Математическая ассоциация Америки рекомендует приобрести в математических библиотеках студентов.

В литературе появилось множество вариантов, в которых варьируется количество моряков, обезьян или кокосов.

Решения

Диофантова задача

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

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

ax + by = c или, в более общем смысле,

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

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

Икс знак равно Икс ₀ + т · б ,

у = у ₀ + т · а

где ( x ₀ , y ₀ ) — решение, а t — параметр, чем может быть любым целым числом. Проблема не предназначен для решения методом проб и ошибок; там являются детерминистическими методами решения ( x ₀ , y ₀ ) в данном случае (см. текст).

Начиная с 1928 года были опубликованы многочисленные решения как исходной задачи, так и модификации Уильямса.

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

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

Оригинальная версия, с остатком одного кокоса.

Колонка Мартина Гарднера в «Математических играх» 1958 года начинает свой анализ с решения исходной задачи (с одним кокосом, оставшимся утром), потому что это проще, чем версия Уильямса. Пусть F — количество кокосов, полученных каждым моряком после окончательного деления утром на 5 равных долей. Тогда количество кокосов, оставшихся до утреннего деления, равно $5F+1$; число присутствующих, когда проснулся пятый матрос, было ${\tfrac {5}{4}}(5F+1)+1={\tfrac {25}{4}}F+{\tfrac {9}{4}}$; число присутствующих, когда четвертый матрос проснулся, было ${\tfrac {5}{4}}({\tfrac {25}{4}}F+{\tfrac {9}{4}})+1={\tfrac {125}{16}}F+{\tfrac {241}{16}}$; и так далее. Мы находим, что размер N исходной кучи удовлетворяет диофантовому уравнению

$1024N=15625F+11529$

Гарднер отмечает, что это уравнение «слишком сложно решить методом проб и ошибок». но представляет решение, которое он приписывает JHC Whitehead (через Поля Дирака ): Уравнение также имеет решения в отрицательных целых числах. Попробовав несколько небольших отрицательных чисел, оказывается, что $N=-4,F=-1$ это решение. Прибавляем 15625 к N и 1024 к F, чтобы получить наименьшее положительное решение: $N=15621,F=1023$.

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

Версия Уильямса, без остатков кокосов.

Методом проб и ошибок не удалось решить версию Уильямса, поэтому необходим более систематический подход.

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

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

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

Синие кокосы

Еще один прием – использование дополнительных предметов для пояснения процесса деления. Предположим, вечером мы добавим в кучу четыре синих кокоса. Тогда первый проснувшийся моряк обнаружит, что куча делится на пять без остатка, а не на один кокос. Моряк делит стопку на пятые части так, чтобы каждый синий кокос находился в отдельной пятой части; затем он берет пятый кокос без синего кокоса, дает один из своих кокосов обезьяне и складывает остальные четыре пятых (включая все четыре синих кокоса) обратно вместе. Каждый моряк делает то же самое. Во время заключительного утреннего дележа синие кокосы остаются в стороне и никому не принадлежат. Поскольку за ночь вся куча была разделена поровну 5 раз, в ней должно было находиться 5 ⁵ кокосы: 4 синих кокоса и 3121 обычный кокос.

Прием использования дополнительных объектов для помощи в концептуализации разделения появился еще в 1912 году в решении Нормана Х. Эннинга .

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

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

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

n5n4n3n2n1 0   (N5)
  s4s3s2s1s0   (S5)
          1   (N'5)

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

n5n4n3n2 4 0
  s4s3s2s1 4
          1

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

n5n4n3n2 4 0
  s4s3s2s1 4
        4 1

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

n5n4n3 4 4 0
  s4s3s2 4 4
        4 1

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

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

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

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

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

Н => 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 и т. д. тоже работают на одно деление.

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

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

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

$N\equiv 4/5\cdot (N-1)$ (мод 5) (-1 — это орех, брошенный обезьяне)

$5N\equiv 4N-4$ (против 5)

$N\equiv -4$ (mod 5) (–4 – класс конгруэнтности)

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

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

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

$1024N=15625F+8404$ (1)

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

Изменение порядка,

$1024N-15625F=8404$ (2)

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

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

где $t$ — произвольный параметр, который может иметь любое целочисленное значение.

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

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

$1024N=15625F+8404\mod 1024$

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

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

вычитание,

$0=265F+212\mod 1024$

факторинг,

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

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

$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 из (д) и объедините)

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

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

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

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

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

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

$F=F_{0}+1024\cdot 2569=204$

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

Альтернативно можно использовать цепную дробь, построение которой основано на алгоритме Евклида. Непрерывная дробь для 1024 ⁄ 15625 (точно 0,065536) равно [;15,3,1,6,2,1, 3 ]; его сходимость прекращается после повторения 313/4776 , что –4776 дает нам x0 ₌ и y0 ₌ 313. Наименьшее значение t, для которого N и F неотрицательны, равно 2569, поэтому

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

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

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

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

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

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

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

$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]$

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

$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]$

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

$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]$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если у утреннего деления остаток также равен единице, решение будет таким:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Источники

• Антоник, Гэри (2013). Мартин Гарднер «Обезьяна и кокосы в игре чисел», The New York Times :, 7 октября 2013 г.
• Плечер, Дэвид (2005). Проблема недели: Обезьяна и кокосы 16 мая 2005 г.
• Паппас, Теони (1993). Радость математики: открытие математики по всему миру. Издательство, 23 января 1993 г., ISBN   0933174659
• Wolfram Mathworld: Задача об обезьяне и кокосе
• Киршнер, Р.Б. «Обобщенная проблема кокоса». амер. Математика. Ежемесячно 67, 516–519, 1960.
• Фадиман, Клифтон (1962). Математическая сорока , Саймон и Шустер.
• Богомольный, Александр (1996) Негативные кокосы при разрезании узла

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

• Обезьяны и кокосы – видео для любителей цифр
• Кокосы , копия истории, опубликованной в Saturday Evening Post.