Проблема с монетой

В математике задача о монетах (также называемая задачей о монетах Фробениуса или задачей Фробениуса , в честь математика Фердинанда Фробениуса ) — это математическая задача , в которой требуется найти наибольшую денежную сумму, которую нельзя получить, используя только монеты указанного номинала . ^[1] Например, наибольшая сумма, которую нельзя получить, используя только монеты достоинством 3 и 5 единиц, составляет 7 единиц. Решение этой задачи для заданного набора номиналов монет называется числом Фробениуса набора. Число Фробениуса существует до тех пор, пока набор номиналов монет является взаимно простым .

Существует явная формула для числа Фробениуса, когда есть только два разных номинала монет, и : тогда число Фробениуса равно . Если число номиналов монет равно трем или более, явная формула неизвестна. Однако для любого фиксированного числа номиналов монет существует алгоритм для вычисления числа Фробениуса за полиномиальное время (в логарифмах номиналов монет, формирующих входные данные). ^[2] Ни один известный алгоритм не является полиномиальным по числу номиналов монет, и общая задача, где число номиналов монет может быть сколь угодно большим, является NP-трудной . ^{[3] [4]}${\displaystyle x}$${\displaystyle у}$${\displaystyle xy-xy}$

Математически задачу можно сформулировать так:

Даны положительные целые числа, такие что gcd , найдите наибольшее целое число, которое не может быть выражено в виде целочисленной конической комбинации этих чисел, т.е. в виде суммы:${\displaystyle a_{1},a_{2},\точки ,a_{n}}$${\displaystyle (a_{1},a_{2},\точки,a_{n})=1}$${\displaystyle k_{1}a_{1}+k_{2}a_{2}+\dots +k_{n}a_{n}}$

где — неотрицательные целые числа.${\displaystyle k_{1},k_{2},\точки ,k_{n}}$

Это наибольшее целое число называется числом Фробениуса множества и обычно обозначается как${\displaystyle \{a_{1},a_{2},\точки ,a_{n}\}}$${\displaystyle g(a_{1},a_{2},\точки ,a_{n})}$

Существование числа Фробениуса зависит от условия, что наибольший общий делитель (НОД) равен 1. Действительно, потенциальные суммы кратны НОД во всех случаях. Следовательно, если он не равен 1, то всегда существуют произвольно большие числа, которые не могут быть получены как суммы. Например, если у вас есть два типа монет достоинством 6 центов и 14 центов, НОД будет равен 2, и не будет никакого способа объединить любое количество таких монет, чтобы получить сумму, которая была бы нечетным числом ; кроме того, четные числа 2, 4, 8, 10, 16 и 22 (меньше m=24 ) также не могут быть образованы. С другой стороны, всякий раз, когда НОД равен 1, множество целых чисел, которые не могут быть выражены как коническая комбинация, ограничено согласно теореме Шура , и, следовательно, число Фробениуса существует.${\displaystyle \{a_{1},a_{2},\точки ,a_{n}\}}$

Замкнутое решение для задачи с монетой существует только при n = 1 или 2. Замкнутое решение для n  > 2  неизвестно. ^[4]

Если , то мы должны иметь , чтобы можно было образовать все натуральные числа.${\displaystyle n=1}$${\displaystyle а_{1}=1}$

Если , то число Фробениуса можно найти по формуле , которая была открыта Джеймсом Джозефом Сильвестром в 1882 году. ^{[5] [nb 1]} Сильвестр также продемонстрировал для этого случая, что существует всего непредставимых (положительных) целых чисел.${\displaystyle n=2}$${\displaystyle g(a_{1},a_{2})=a_{1}a_{2}-a_{1}-a_{2}}$${\displaystyle N(a_{1},a_{2})=(a_{1}-1)(a_{2}-1)/2}$

Другая форма уравнения для дана Скупенем ^[8] в следующем предложении: Если и , то для каждого существует ровно одна пара неотрицательных целых чисел и такая, что и .${\displaystyle g(a_{1},a_{2})}$${\displaystyle a_{1},a_{2}\in \mathbb {N} }$${\displaystyle \НОД(a_{1},a_{2})=1}$${\displaystyle n\geq (a_{1}-1)(a_{2}-1)}$${\displaystyle \ро}$${\displaystyle \сигма}$${\displaystyle \сигма <a_{1}}$${\displaystyle n=\rho a_{1}+\sigma a_{2}}$

Формула доказывается следующим образом. Предположим, что мы хотим построить число . Так как , все целые числа для взаимно различны по модулю . Таким образом, любое целое число должно быть сравнимо по модулю с одним из этих остатков; в частности, если взять есть уникальное значение и уникальное целое число , такое что . Переставляя, мы получаем неотрицательное целое число , такое что . Действительно, поскольку .${\displaystyle n\geq (a_{1}-1)(a_{2}-1)}$${\displaystyle \НОД(a_{1},a_{2})=1}$${\displaystyle n-ja_{2}}$${\displaystyle j=0,1,\ldots ,a_{1}-1}$${\displaystyle а_{1}}$${\displaystyle м}$${\displaystyle а_{1}}$${\displaystyle m=a_{1}}$${\displaystyle j=\sigma \geq 0}$${\displaystyle т}$${\displaystyle a_{1}=n-\sigma a_{2}+ta_{1}}$${\displaystyle \rho =1-t}$${\displaystyle n=\rho a_{1}+\sigma a_{2}}$${\displaystyle \rho \geq 0}$${\displaystyle \rho a_{1}=n-\sigma a_{2}\geq (a_{1}-1)(a_{2}-1)-(a_{1}-1)a_{2}=-a_{1}+1>(-1)a_{1}}$

Чтобы показать, что ровно половина целых чисел представима в виде неотрицательных целых линейных комбинаций, сначала нужно показать, что если целое число представимо, то непредставимо, где .${\displaystyle 0,1,\ldots ,ab-ab}$${\displaystyle k\in [0,ab-ab]}$${\displaystyle Нк}$${\displaystyle N=ab-ab}$

Затем показывают, что верно и обратное: если не представимо, то представимо. Чтобы показать это, воспользуемся тем фактом, что , что позволяет нам записать . Сокращая и переставляя коэффициенты, добавляя кратные по мере необходимости, мы можем предположить (на самом деле, это единственное такое, удовлетворяющее уравнению и неравенствам).${\displaystyle к}$${\displaystyle Нк}$${\displaystyle \НОД(а,б)=1}$${\displaystyle k=xa+yb}$${\displaystyle ab}$${\displaystyle 0\leqx<b}$${\displaystyle x}$${\displaystyle x}$

Аналогично мы берем удовлетворяющие и . Теперь мы можем сложить эти уравнения, чтобы записать , что, используя дает . Целое число положительно, так как . Фактически, поскольку левая часть делится на , и , мы должны иметь, что делится на . Тем не менее , так что , так что . Подставляя это в и вычитая из обеих сторон, получаем . Так что . Это подразумевает, что , что означает, что ровно одно из или отрицательно. Если отрицательно, то , что означает, что представимо; случай, когда отрицательно, влечет, что представимо.${\displaystyle u,v}$${\displaystyle N-k=ua+vb}$${\displaystyle 0\leq u<b}$${\displaystyle N=(u+x)a+(y+v)b}$${\displaystyle N=ab-a-b}$${\displaystyle ab-b(1+y+v)=a(x+u+1)}$${\displaystyle x+u+1}$${\displaystyle x,u\geq 0}$${\displaystyle ab-b(1+y+v)=a(x+u+1)}$${\displaystyle b}$${\displaystyle (a,b)=1}$${\displaystyle x+u+1}$${\displaystyle b}$${\displaystyle x,u\leq b-1}$${\displaystyle x+u+1\leq 2b-1}$${\displaystyle x+u+1=b}$${\displaystyle ab-b(1+y+v)=a(x+u+1)}$${\displaystyle ab}$${\displaystyle b(1+y+v)=0}$${\displaystyle 1+y+v=0}$${\displaystyle y+v=-1}$${\displaystyle y}$${\displaystyle v}$${\displaystyle y}$${\displaystyle v\geq 0}$${\displaystyle N-k=ua+vb}$${\displaystyle v}$${\displaystyle k}$

Таким образом, для любого неотрицательного целого числа мы знаем, что ровно одно из или представимо (и они различны, поскольку должны быть нечетными, поскольку целые числа являются взаимно простыми). Это показывает, что половина целых чисел в заданном диапазоне представимы; поскольку в диапазоне есть целые числа , это дает желаемый результат.${\displaystyle k\in [0,ab-a-b]}$${\displaystyle k}$${\displaystyle (ab-a-b)-k}$${\displaystyle ab-a-b}$${\displaystyle a,b}$${\displaystyle (ab-a-b+1)=(a-1)(b-1)}$${\displaystyle [0,ab-a-b]}$

Известны формулы ^[9] и быстрые алгоритмы ^[10] для трех чисел, хотя вычисления могут быть очень утомительными, если выполнять их вручную.

Также были определены более простые нижние и верхние границы для чисел Фробениуса при n = 3. Асимптотическая нижняя граница, полученная Дэвисоном

${\displaystyle f(a_{1},a_{2},a_{3})\equiv g(a_{1},a_{2},a_{3})+a_{1}+a_{2}+a_{3}\geq {\sqrt {3a_{1}a_{2}a_{3}}}}$

является относительно точным. ^[11] ( здесь — модифицированное число Фробениуса, которое является наибольшим целым числом, не представимым с помощью положительных целых линейных комбинаций .) Сравнение с фактическим пределом (определенным параметрическим соотношением, где ) показывает, что приближение всего на 1 меньше истинного значения, так как . Предполагается, что аналогичная параметрическая верхняя граница (для значений , которые являются попарно взаимно простыми и ни один элемент не представим другими) равна , где .${\displaystyle f}$${\displaystyle a_{1},a_{2},a_{3}}$${\displaystyle f(z(i))=9i^{2}+54i+79}$${\displaystyle z(i)=a_{1}a_{2}a_{3}=(3i+7)(3i+10)(3i^{2}+19i+29)}$${\displaystyle i\rightarrow \infty }$${\displaystyle a_{1},a_{2},a_{3}}$${\displaystyle f(z(i))=6i^{2}+19i+13}$${\displaystyle z(i)=a_{1}a_{2}a_{3}=(3i+2)(3i+3)(6i+7)}$

Асимптотическое среднее поведение для трех переменных также известно как: ^[12]${\displaystyle f}$

${\displaystyle f(a_{1},a_{2},a_{3})\sim {\frac {8}{\pi }}{\sqrt {a_{1}a_{2}a_{3}}},}$

В 1978 году Вильф предположил, что если даны взаимно простые целые числа и их число Фробениуса , то мы имеем${\displaystyle a_{1}<a_{2}<...<a_{d}}$${\displaystyle F}$

${\displaystyle d\geq {\frac {F+1}{F+1-g}},}$

где обозначает количество всех непредставимых положительных целых чисел. ^[13] В 2015 году асимптотическая версия этого была доказана Москариелло и Саммартано. ^[14]${\displaystyle g}$

Существует простая формула для числа Фробениуса набора целых чисел в арифметической последовательности . ^[15] Даны целые числа a , d , w с gcd( a ,  d ) = 1:

${\displaystyle g(a,a+d,a+2d,\dots ,a+wd)=\left(\left\lfloor {\frac {a-2}{w}}\right\rfloor \right)a+d(a-1)}$

Приведенный выше случай можно выразить как частный случай этой формулы.${\displaystyle n=2}$

В случае, если , мы можем опустить любое подмножество элементов из нашей арифметической последовательности, и формула для числа Фробениуса останется прежней. ^[16]${\displaystyle a>w^{2}-3w+1}$${\displaystyle a+2d,a+3d,...,a+(w-3)d,a+(w-2)d}$

Также существует решение в замкнутой форме для числа Фробениуса множества в геометрической последовательности . ^[17] Даны целые числа m , n , k с gcd( m ,  n ) = 1:

${\displaystyle g(m^{k},m^{k-1}n,m^{k-2}n^{2},\dots ,n^{k})=n^{k-1}(mn-m-n)+{\frac {m^{2}(n-1)(m^{k-1}-n^{k-1})}{m-n}}.}$

Более простая формула, которая также отображает симметрию между переменными, выглядит следующим образом. Даны положительные целые числа , пусть . Тогда ^[18]${\displaystyle a,b,k}$${\displaystyle \gcd(a,b)=1,}$${\displaystyle A_{k}(a,b)=\{a^{k},a^{k-1}b,\ldots ,b^{k}\}}$

${\displaystyle g(A_{k}(a,b))={\sigma }_{k+1}(a,b)-{\sigma }_{k}(a,b)-(a^{k+1}+b^{k+1}),}$

где обозначает сумму всех целых чисел в${\displaystyle {\sigma }_{k}(a,b)}$${\displaystyle A_{k}(a,b).}$

Один особый случай задачи с монетой иногда также называют числами Макнаггетса . Версия задачи с монетой Макнаггетса была представлена ​​Анри Пиччиотто, который поместил ее в качестве головоломки в журнале Games Magazine в 1987 году ^[19] и включил ее в свой учебник по алгебре, написанный в соавторстве с Анитой Ва. ^[20] Пиччиотто придумал это приложение в 1980-х годах, обедая со своим сыном в McDonald's, решая задачу на салфетке. Число Макнаггетса — это общее количество McDonald's Chicken McNuggets в любом количестве коробок. В Соединенном Королевстве оригинальные коробки (до введения коробок для наггетсов размером с Happy Meal ) были на 6, 9 и 20 наггетсов.

Согласно теореме Шура , поскольку 6, 9 и 20 являются (множественно) взаимно простыми , любое достаточно большое целое число может быть выражено как (неотрицательная, целая) линейная комбинация этих трех. Следовательно, существует наибольшее не-число Макнаггета, и все целые числа, большие его, являются числами Макнаггета. А именно, каждое положительное целое число является числом Макнаггета, за конечным числом исключений:

1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37 и 43 (последовательность A065003 в OEIS ).

Таким образом, наибольшее число, не являющееся числом Макнаггета, равно 43. ^[21] Тот факт, что любое целое число, большее 43, является числом Макнаггета, можно увидеть, рассмотрев следующие целочисленные разбиения:

${\displaystyle 44=6+6+6+6+20}$

${\displaystyle 45=9+9+9+9+9}$

${\displaystyle 46=6+20+20}$

${\displaystyle 47=9+9+9+20}$

${\displaystyle 48=6+6+9+9+9+9}$

${\displaystyle 49=9+20+20}$

Любое большее целое число можно получить, добавив некоторое количество 6 к соответствующему разделу выше. Простая проверка показывает, что 43 McNuggets действительно нельзя купить , так как:

1. ячейки из 6 и 9 по отдельности не могут образовать число 43, поскольку они могут создавать только числа, кратные 3 (за исключением самой 3);
2. включение одного поля с числом 20 не поможет, так как требуемый остаток (23) также не кратен 3; и
3. Очевидно, что более одной коробки на 20 штук, дополненной коробками размером 6 штук или больше, не могут привести к общему количеству 43 Макнаггетсов.

С момента появления коробок для наггетсов размером с Happy Meal, состоящих из 4 частей, самым большим числом, не являющимся McNugget, стало 11. В странах, где размер из 9 частей заменен размером из 10 частей, самого большого числа, не являющегося McNugget, не существует, поскольку нечетное число сделать невозможно.

В регби-юнионе существует четыре типа очков: штрафной гол (3 очка), дроп-гол (3 очка), попытка (5 очков) и реализованная попытка (7 очков). Объединив их, можно получить любое количество очков, кроме 1, 2 или 4. В регби-7 , хотя разрешены все четыре типа очков, попытки штрафных голов редки, а результативные попытки почти неизвестны. Это означает, что командные очки почти всегда состоят из кратных попыток (5 очков) и реализованных попыток (7 очков). Следующие очки (в дополнение к 1, 2 и 4) не могут быть получены из кратных 5 и 7 и поэтому почти никогда не встречаются в семерках: 3, 6, 8, 9, 11, 13, 16, 18 и 23. В качестве примера, ни один из этих очков не был зафиксирован ни в одной игре Мировой серии по семеркам 2014-15 годов .

Аналогично, в американском футболе единственный способ для команды набрать ровно одно очко — это если против команды противника будет назначен сейфти , когда они попытаются реализовать тачдаун (который в этом случае имеет ценность 6). Поскольку за сейфти в обычной игре присуждается 2 очка, а за филд-голы — 3 очка , возможны все счета, кроме 1–0, 1–1, 2–1, 3–1, 4–1, 5–1 и 7–1.

Алгоритм сортировки Шелла — это алгоритм сортировки, временная сложность которого в настоящее время является открытой проблемой . Сложность в худшем случае имеет верхнюю границу, которая может быть задана в терминах числа Фробениуса заданной последовательности положительных целых чисел.

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

Когда одномерный многочлен возводится в некоторую степень, можно рассматривать показатели степени многочлена как набор целых чисел. Развернутый многочлен будет содержать степени, большие, чем число Фробениуса для некоторой экспоненты (когда НОД = 1), например, для набора {6, 7} , имеющего число Фробениуса 29, поэтому член с никогда не появится ни для какого значения , но некоторое значение даст члены, имеющие любую степень, большую 29. Когда НОД экспонент не равен 1, то степени, большие, чем некоторое значение, появятся только в том случае, если они кратны НОД, например, для , степени 24, 27,... появятся для некоторых значений , но никогда не будут значения, большие 24, которые не кратны 3 (и меньшие значения 1-8, 10-14, 16, 17, 19-23).${\displaystyle x}$${\displaystyle (1+x^{6}+x^{7})^{n}}$${\displaystyle x^{29}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle x}$${\displaystyle (1+x^{9}+x^{15})^{n}}$${\displaystyle n}$

• Проблема почтовых марок
• Проблема внесения изменений
• Чеканка серебряных монет
• Числовая полугруппа

• Tuenter, Hans JH (апрель 2006 г.). «Проблема Фробениуса, суммы степеней целых чисел и повторения для чисел Бернулли». Журнал теории чисел . 117 (2): 376–386. doi : 10.1016/j.jnt.2005.06.015 . MR  2213771. Zbl  1097.11010.

• Как заказать 43 Chicken McNuggets – Numberphile