Введение
В математике, задача о монетах (также известная как задача Фробениуса о монетах или просто задача Фробениуса, в честь математика Фердинанда Фробениуса) — это математическая задача, которая ставит вопрос о нахождении наибольшей денежной суммы, которую нельзя получить, используя только монеты заданного номинала. Например, наибольшая сумма, которую нельзя получить, используя только монеты номиналом 3 и 5, равна 7. Решение этой задачи для заданного набора номиналов монет называется числом Фробениуса для этого набора. Число Фробениуса существует, если набор номиналов монет взаимно просты. Существует явная формула для числа Фробениуса, когда есть только два различных номинала монет, *a* и *b*: число Фробениуса тогда равно *ab* - *a* - *b*. Если количество номиналов монет равно трем или более, явной формулы не известно. Однако, для любого фиксированного числа номиналов монет существует алгоритм вычисления числа Фробениуса за полиномиальное время (относительно логарифмов номиналов монет, представляющих входные данные). Ни один известный алгоритм не является полиномиальным по времени относительно количества номиналов монет, и общая задача, где количество номиналов монет может быть произвольно большим, является NP-трудной.
In mathematics, the coin problem (also referred to as the Frobenius coin problem or Frobenius problem, after the mathematician Ferdinand Frobenius) is a mathematical problem that asks for the largest monetary amount that cannot be obtained using only coins of specified denominations. For example, the largest amount that cannot be obtained using only coins of 3 and 5 units is 7 units. The solution to this problem for a given set of coin denominations is called the Frobenius number of the set. The Frobenius number exists as long as the set of coin denominations is setwise coprime. There is an explicit formula for the Frobenius number when there are only two different coin denominations, and : the Frobenius number is then If the number of coin denominations is three or more, no explicit formula is known. However, for any fixed number of coin denominations, there is an algorithm for computing the Frobenius number in polynomial time (in the logarithms of the coin denominations forming an input). No known algorithm is polynomial time in the number of coin denominations, and the general problem, where the number of coin denominations may be as large as desired, is NP hard.
Числа Фробена для малого n
Закрытое решение для задачи о монетах существует только при n = 1 или 2. Для n > 2 не известно решений в замкнутой форме. Сильвестр также показал для этого случая, что существует общее число непредставимых (положительных) целых чисел. Другая форма уравнения для приведена Скупиеном в следующем утверждении: Если и , то для каждого существует ровно одна пара неотрицательных целых чисел и такая, что и .
The formula is proved as follows. Suppose we wish to construct the number Since , all of the integers for are mutually distinct modulo Thus any integer must be congruent modulo to one of these residues; in particular, taking there is a unique value of and a unique integer , such that Rearranging, we have a nonnegative integer so that Indeed, because
To show that exactly half of the integers are representable as non negative integer linear combinations, one first shows that if the integer is representable, then is not representable, where
One then shows that the converse is true as well: if is not representable, then is representable. To show this, use the fact that , which allows us to write Reducing and re arranging the coefficients by adding multiples of as necessary, we can assume (in fact, this is the unique such satisfying the equation and inequalities). Similarly we take satisfying and Now we can add these equations to write which, using yields The integer is positive, because In fact, since the left hand side of is divisible by , and , we must have that is divisible by Yet , so , so that Substituting this into and subtracting from both sides yields So This implies that , which means that exactly one of or is negative. If is negative, then , which means that is representable; the case when is negative entails that is representable. Thus for any non negative integer , we know that exactly one of or is representable (and these are distinct, because must be odd as the integers are relatively prime). This shows that half of the integers in the given range are representable; since there are integers in the range , this gives the desired result.
Доказательство формулы следующее. Предположим, мы хотим представить число . Поскольку все целые числа для взаимно различны по модулю , любое целое число должно быть сравнимо по модулю с одним из этих остатков; в частности, выбрав , существует единственное значение и единственное целое число такое, что . Перегруппировав, получим неотрицательное целое число такое, что . Действительно, потому что .
The formula is proved as follows. Suppose we wish to construct the number Since , all of the integers for are mutually distinct modulo Thus any integer must be congruent modulo to one of these residues; in particular, taking there is a unique value of and a unique integer , such that Rearranging, we have a nonnegative integer so that Indeed, because
To show that exactly half of the integers are representable as non negative integer linear combinations, one first shows that if the integer is representable, then is not representable, where
One then shows that the converse is true as well: if is not representable, then is representable. To show this, use the fact that , which allows us to write Reducing and re arranging the coefficients by adding multiples of as necessary, we can assume (in fact, this is the unique such satisfying the equation and inequalities). Similarly we take satisfying and Now we can add these equations to write which, using yields The integer is positive, because In fact, since the left hand side of is divisible by , and , we must have that is divisible by Yet , so , so that Substituting this into and subtracting from both sides yields So This implies that , which means that exactly one of or is negative. If is negative, then , which means that is representable; the case when is negative entails that is representable. Thus for any non negative integer , we know that exactly one of or is representable (and these are distinct, because must be odd as the integers are relatively prime). This shows that half of the integers in the given range are representable; since there are integers in the range , this gives the desired result.
Чтобы показать, что ровно половина целых чисел представимы в виде неотрицательных целочисленных линейных комбинаций, сначала показывают, что если целое число представимо, то не представимо, где . Затем показывают, что обратное также верно: если не представимо, то представимо. Чтобы это показать, используем тот факт, что , что позволяет нам записать . Уменьшая и переставляя коэффициенты, добавляя при необходимости кратные , мы можем предположить (на самом деле, это единственное такое , удовлетворяющее уравнению и неравенствам). Аналогично, выберем такое, что и . Теперь мы можем сложить эти уравнения, чтобы получить , что, используя , дает . Целое число положительно, потому что . Фактически, поскольку левая часть делится на , а , мы должны иметь, что делится на . Однако , поэтому , так что . Подставляя это в и вычитая из обеих частей, получаем , что означает, что . Это означает, что ровно одно из или отрицательно. Если отрицательно, то , что означает, что представимо; случай, когда отрицательно, влечет за собой, что представимо. Таким образом, для любого неотрицательного целого числа мы знаем, что ровно одно из или представимо (и они различны, потому что должно быть нечетным, поскольку взаимно просты). Это показывает, что половина целых чисел в данном диапазоне представима; поскольку в диапазоне целых чисел, это дает желаемый результат.
The formula is proved as follows. Suppose we wish to construct the number Since , all of the integers for are mutually distinct modulo Thus any integer must be congruent modulo to one of these residues; in particular, taking there is a unique value of and a unique integer , such that Rearranging, we have a nonnegative integer so that Indeed, because
To show that exactly half of the integers are representable as non negative integer linear combinations, one first shows that if the integer is representable, then is not representable, where
One then shows that the converse is true as well: if is not representable, then is representable. To show this, use the fact that , which allows us to write Reducing and re arranging the coefficients by adding multiples of as necessary, we can assume (in fact, this is the unique such satisfying the equation and inequalities). Similarly we take satisfying and Now we can add these equations to write which, using yields The integer is positive, because In fact, since the left hand side of is divisible by , and , we must have that is divisible by Yet , so , so that Substituting this into and subtracting from both sides yields So This implies that , which means that exactly one of or is negative. If is negative, then , which means that is representable; the case when is negative entails that is representable. Thus for any non negative integer , we know that exactly one of or is representable (and these are distinct, because must be odd as the integers are relatively prime). This shows that half of the integers in the given range are representable; since there are integers in the range , this gives the desired result.
Арифметические последовательности
Существует простая формула для числа Фробениуса набора целых чисел в арифметической прогрессии. Для заданных целых чисел a, d, w, где НОД(a, d) = 1:
Вышеуказанный случай можно выразить как частный случай этой формулы. Если w = 0, мы можем исключить любое подмножество элементов из нашей арифметической прогрессии, и формула для числа Фробениуса останется прежней.
Другие примеры
В регби-юнион существует четыре типа набора очков: штрафной гол (3 очка), дроп-гол (3 очка), попытка (5 очков) и реализация после попытки (7 очков). Комбинируя их, можно получить любое количество очков, кроме 1, 2 или 4. В регби-7, хотя все четыре типа набора очков разрешены, попытки реализации штрафных ударов редки, а дроп-голы практически неизвестны. Это означает, что результаты команд почти всегда состоят из кратных попыток (5 очков) и реализаций после попыток (7 очков). Следующие результаты (в дополнение к 1, 2 и 4) нельзя получить, используя только кратные 5 и 7, и поэтому они почти никогда не встречаются в регби-7: 3, 6, 8, 9, 11, 13, 16, 18 и 23. Например, ни один из этих результатов не был зафиксирован ни в одном матче Мировой серии по регби-7 в 2014 году. Аналогично, в американском футболе, единственный способ для команды набрать ровно одно очко – это когда команде соперника присуждают сейфти при попытке реализации после тачдауна (который в этом случае оценивается в 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).