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

Не путать с проблемой внесения изменений .

Имея только монеты в 2 и 5 пенсов, нельзя заработать 3 пенса, но можно заработать любую большую целую сумму.

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

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

Заявление

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

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

где $k_{1},k_{2},\dots ,k_{n}$ являются неотрицательными целыми числами.

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

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

Числа Фробениуса для малых n

Решение в замкнутой форме для задачи о монетах существует только там, где n > 2 решение в замкнутой форме не известно = 1 или 2. Для n .

п = 1

Если $n=1$, то мы должны иметь $a_{1}=1$ так что можно составить все натуральные числа.

п = 2

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

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

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

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

Затем показывается, что верно и обратное: если $k$ непредставимо, то $N-k$ является представительным. Чтобы показать это, воспользуемся тем фактом, что $\gcd(a,b)=1$, что позволяет нам написать $k=xa+yb$. Уменьшение и перестановка коэффициентов путем добавления кратных $ab$ при необходимости мы можем предположить $0\leq x<b$ (на самом деле это $x$ уникальный такой $x$ удовлетворяющие уравнению и неравенствам).

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

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

п = 3

Формулы и быстрые алгоритмы известны три числа, хотя вычисления могут быть очень утомительными, если выполнять их вручную.

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

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

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

Асимптотическое среднее поведение $f$ для трех переменных также известен как:

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

Гипотеза Уилфа

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

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

где $g$ обозначает количество всех непредставимых положительных целых чисел. В 2015 году асимптотическую версию этого утверждения доказали Москариелло и Саммартано.

Числа Фробениуса для специальных наборов

Арифметические последовательности

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

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

The $n=2$ приведенный выше случай может быть выражен как частный случай этой формулы.

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

Геометрические последовательности

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

$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}}.$

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

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

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

Примеры

Числа Макнаггета

Коробка из 20 штук McDonald's Chicken McNuggets.

Один частный случай проблемы монет иногда также называют числами МакНаггетса . Версия задачи с монетами в Макнаггетсе была представлена ​​Анри Пиччиотто, который поместил ее как головоломку в журнал Games Magazine в 1987 году. и включил его в свой учебник алгебры, написанный в соавторстве с Анитой Ва. Пиччиотто задумался об этом приложении в 1980-х годах, когда обедал со своим сыном в Макдональдсе и решал задачу на салфетке. Число McNugget — это общее количество 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 ).

Общий	0	1	2	3	4	5
+0	0: 0 , 0 , 0	1: —	2: —	3: —	4: —	5: —
+6	6: 1 , 0 , 0	7: —	8: —	9: 0 , 1 , 0	10: —	11: —
+12	12: 2 , 0 , 0	13: —	14: —	15: 1 , 1 , 0	16: —	17: —
+18	18: 3 , 0 , 0	19: —	20: 0 , 0 , 1	21: 2 , 1 , 0	22: —	23: —
+24	24: 4 , 0 , 0	25: —	26: 1 , 0 , 1	27: 3 , 1 , 0	28: —	29: 0 , 1 , 1
+30	30: 5 , 0 , 0	31: —	32: 2 , 0 , 1	33: 4 , 1 , 0	34: —	35: 1 , 1 , 1
+36	36: 6 , 0 , 0	37: —	38: 3 , 0 , 1	39: 5 , 1 , 0	40: 0 , 0 , 2	41: 2 , 1 , 1
+42	42: 7 , 0 , 0	43: —	44: 4 , 0 , 1	45: 6 , 1 , 0	46: 1 , 0 , 2	47: 3 , 1 , 1
+48	48: 8 , 0 , 0	49: 0 , 1 , 2	50: 5 , 0 , 1	51: 7 , 1 , 0	52: 2 , 0 , 2	53: 4 , 1 , 1
+54	54: 9 , 0 , 0	55: 1 , 1 , 2	56: 6 , 0 , 1	57: 8 , 1 , 0	58: 3 , 0 , 2	59: 5 , 1 , 1
Возможный набор комбинаций коробочек, всего от 0 до 59 самородков. Каждая тройка обозначает количество коробок 6 , 9 и 20 соответственно.

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

$44=6+6+6+6+20$

$45=9+9+9+9+9$

$46=6+20+20$

$47=9+9+9+20$

$48=6+6+9+9+9+9$

$49=9+20+20$

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

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

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

Другие примеры

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

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

Приложения

Временная сложность сортировки Шелла

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

Проблема наименьшего живого веса

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

Члены расширенной степени многочлена

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

См. также

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

Дальнейшее чтение

• Туэнтер, Ханс Дж. Х. (апрель 2006 г.). «Задача Фробениуса, суммы степеней целых чисел и рекурренты для чисел Бернулли» . Журнал теории чисел . 117 (2): 376–386. дои : 10.1016/j.jnt.2005.06.015 . МР   2213771 . Збл   1097.11010 .

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

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