On the Two Properties of the Frobenius Number

Shevchenko V.N.; Savelyev V.P.

doi:10.23670/IRJ.2022.123.59

On the Two Properties of the Frobenius Number

Research article

Савельев Владимир Петрович0000-0002-6578-7022Нижегородский государственный инженерно-экономический университет, Княгинино, Российская Федерация
Шевченко Валерий НиколаевичНижегородский государственный университет им. Н.И. Лобачевского, Нижний Новгород, Российская Федерация

Savelyev V. P.
Shevchenko V. N.

https://doi.org/10.23670/IRJ.2022.123.59

DOI:

https://doi.org/10.23670/IRJ.2022.123.59

EDN:

EZDDMT

Suggested:

28.07.2022

Accepted:

02.09.2022

Published:

16.09.2022

Issue: № 9 (123), 2022

Rightholder: authors. License: Attribution 4.0 International (CC BY 4.0)

3887

34

XML

PDF

Abstract

The problem of finding the Frobenius number is urgent, it is closely related to the graph theory and the well-known knapsack and exchange problems. The formula for calculating the Frobenius number is known only for two numbers: if the greatest common divisor of natural numbers a and b is one, then frob(a,b) = ab - a - b. The paper proves two properties on the problem of finding the Frobenius number for three natural numbers. The first of these properties complements, even enriches, the mentioned famous Frobenius formula for two natural numbers. This property allows moving from a Frobenius number for two natural numbers to a Frobenius number for three natural numbers when the third number is a Frobenius number for the first two numbers: frob(a,b,frob(a,b)) = frob (a,b) - a. The second property belongs to the "homogeneity" properties of the frob operation, allowing in some cases to take the multiplier before one or more variables beyond the sign of the operation. As a result of this property, the problem of finding the Frobenius number for three numbers of special form is reduced to the well-known formula for the Frobenius number for three consecutive natural numbers.

Keywords:

additive semigroup, Frobenius problem, Frobenius number.

1. Введение

Проблеме нахождения числа Фробениуса для конечного множества чисел посвящено много работ, достаточно полный обзор которых имеется в [1]. Эта проблема актуальна, она тесно связана с рядом задач из теории графов и с известными задачами о рюкзаке и о размене. Формула для числа Фробениуса известна лишь для двух натуральных чисел. В общем случае такой формулы нет даже для трех натуральных чисел. В некоторых частных случаях формулы найдены, или предложены алгоритмы вычисления числа Фробениуса [2], [4], [9], [10]. Целью данной работы является получение двух новых формул числа Фробениуса для трех чисел специального вида. Первая формула позволяет перейти от числа Фробениуса для двух натуральных чисел к числу Фробениуса для трех натуральных чисел, когда третье число является числом Фробениуса для первых двух чисел. Эту формулу можно считать непосредственным продолжением и дополнением знаменитой формулы Фробениуса для двух чисел. Вторая формула сводит проблему нахождения числа Фробениуса для трех чисел специального вида к известной формуле числа Фробениуса для трех последовательных натуральных чисел.

Для натуральных чисел

определим аддитивную полугруппу

, порожденную этими числами. Отметим, что любой элемент

полугруппы

может быть представлен в виде линейной комбинации вида

где

– множество целых неотрицательных чисел.

Множество

называется множеством Фробениуса. Числом Фробениуса

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

.

Ниже, для доказательства того, что некоторое число является числом Фробениуса, используется следующее утверждение [11, С. 61].

2. Свойство 1

Утверждение 1. Пусть

и

. Если каждое из последовательных натуральных чисел, начиная с некоторого числа

, принадлежит аддитивной полугруппе

, то ей принадлежат все натуральные числа, начиная с числа

.

Действительно, пусть каждое из

чисел

принадлежит полугруппе

. Поскольку

одно из чисел исходного множества

, то прибавив его к каждому из чисел

, мы получим следующие

чисел

, так же принадлежащих полугруппе

, и так далее по индукции.

Этот простой факт можно сформулировать и по-другому: необходимым условием того, чтобы число

являлось числом Фробениуса для исходного множества натуральных чисел

является принадлежность последовательных натуральных чисел

полугруппе

, где

– одно из чисел

. Если же удается показать, что число

не принадлежит аддитивной полугруппе

, то это условие становится и достаточным.

Свойство 1. Пусть

. Тогда справедлива формула

(1)

Доказательство. Имеем:

Это значит, что числа

входят в аддитивную полугруппу G(a,b), то есть представимы в виде неотрицательной целочисленной комбинации

(2)

В частности, при i=a имеем равенство

, которое означает, что

. Действительно, коэффициент

не может быть положительным, ибо в этом случае получится противоречие с определением числа Фробениуса:

Что касается остальных

чисел

, то можно утверждать, что все коэффициенты

.

Действительно, если предположить, что некоторое

, то при

получим неравенство

(3)

Если же

, то для всех

получим противоположное неравенство

(4)

Отсюда следует, что все числа

, то есть, числа

, входят в состав полугруппы

.

Итак, перед числом

, которое является числом Фробениуса для чисел a,b, имеется

чисел

(5)

входящих в состав полугруппы

. В то же время, число

не может входить в состав

поскольку

.

Нетрудно видеть, что если число

не входит в состав полугруппы

, то это число не входит также и в состав полугруппы

поскольку

.

Итак, доказана справедливость формулы (1).

Ниже мы докажем свойство, которое позволяет найти число Фробениуса для трех чисел вида

, где

– четное натуральное число. Заметим, что при

мы имеем три последовательных натуральных числа. В работе Брауэра [9] получена формула для числа Фробениуса в случае, когда натуральные числа

образуют арифметическую прогрессию с разностью

(6)

где [x] обозначает наибольшее целое число, не большее, чем x (целая часть числа x). Нами формула Брауэра будет использоваться в более удобном виде

(7)

где [x] обозначает наименьшее целое число, не меньшее, чем x.

Обе формулы (6) и (7) верны, так как для всех

справедливо соотношение

(8)

Действительно, если число

является целым числом p, то число

и по определению

. Если число

, то

и

. Если число

, то

, и

. Наконец, если число

, то

, и

.

В частности, для трех последовательных натуральных чисел

число Фробениуса в соответствии с формулой Брауэра равно:

(9)

3. Свойство 2

Если

, то имеет место формула

(10)

Применяя формулу Брауэра (9) для четных значений

, и нечетных значений

, получим

(11)

Применяя формулу Брауэра (9) для нечетных значений

и нечетных значений

получим

(12)

Применяя формулу Брауэра (9) для нечетных значений

и четных значений, получим

(13)

Из формул (11), (12) и (13) следует, что формула (10) может быть верна только при условии, что a – четное число.

Докажем, что при

, имеет место формула

(14)

то есть справедлива формула (10).

Действительно, рассмотрим линейную комбинацию

(15)

Пусть

, тогда значение линейной комбинации (15) строго больше, чем

:

Если теперь предположить, что

тогда значение линейной комбинации (15) будет строго меньше, чем

:

Итак, число

не может быть представлено в виде линейной целочисленной комбинации (15), то есть не принадлежит аддитивной полугруппе

.

Теперь докажем, что любое число вида

может быть представлено в виде линейной комбинации (15).

Возьмем в линейной комбинации (15) следующие значения:

(16)

Тогда линейная комбинация (15) примет вид

(17)

и примет все натуральные значения с шагом 2 от значения

до значения

включительно.

Далее, возьмем в линейной комбинации (15) следующие значения

(18)

Тогда линейная комбинация (15) примет вид

(19)

и примет все натуральные значения с шагом 2 от значения

до значения

включительно.

Наконец, число

получится, если в линейной комбинации (15) взять значения:

.

Итак, все

последовательных натуральных чисел, начиная с числа

, принадлежат полугруппе

. Отсюда следует, в соответствии с утверждением 1, что все натуральные числа, начиная с числа

будут принадлежать этой полугруппе, что и означает справедливость формулы (10) и свойства 2.

4. Заключение

Обозначенные свойства числа Фробениуса доказаны.

Additional materials

Not specified

Financing

The authors did not receive financial support for research, writing and publishing articles

Acknowledgements

Not specified

Conflicts of interests

Not specified

References

Alfonsin J.R. The Diophantine Frobenius Problem / J.R. Alfonsin. – Oxford University Press, 2005. – 243 p.

Shevchenko V.N. Zadacha o razmene, zadacha Frobeniusa i zadacha gruppovoj minimizacii [The Exchange Problem, the Frobenius Problem, and the Group Minimization Problem] / V.N. Shevchenko // Kombinatorno-algebraicheskie metody v prikladnoj matematike [Combinatorial Algebraic Methods in Applied Mathematics]. – Gorky: Gorky University Publishing House, 1982. – P. 166–179. [in Russian]

Shevchenko V.N. Qualitative topics of linear and integer programming / V.N. Shevchenko. – Providence : AMS, 1996.

Selmer E.S. On the linear Diophantine problem of Frobenius in three variables / E.S. Selmer, O. Beyer // J. Reine Angewandte Math. – 1978. – № 301. – P.161–170.

Rodseth O.J., On a linear Diophantine problem of Frobenius / O.J. Rodseth // J. Reine Angewandte Math. – 1978. – № 301. – P.171–178.

Curtis. F. On formulas for the Frobenius number of a numerical semigroup / F. Curtis // Math. Scand. – 1990. – № 67. – P. 190–192.

Johnson S.M. A linear Diophantine Problem / S.M. Johnson // Can. J. Math. – 1960. – № 12. – P. 390–398.

Greenberg Solution to a Diophantine Equation for nonnegative integers / H. Greenberg // J. Algorithm. – 1988. – № 9(3). – P. 343–353.

Brauer A. On a problem of partitions / A. Brauer // Am. J. Math. – 1942. – № 64. – P. 299–312.

Savel'ev V.P. Algoritm vychislenija chisla Frobeniusa dlja treh natural'nyh chisel [Algorithm for Calculating Frobenius Number for Three Natural Numbers] / V.P. Savel'ev // Sbornik nauchnyh trudov 83-ej Mezhdunarodnoj konferencii Evrazijskogo Nauchnogo Ob'edinenija [Proceedings of the 83rd International Conference of the Eurasian Scientific Association]. – Moscow: ESA, 2022, – P. 19–22. [in Russian]

Savel'ev V.P. Zadachi diskretnoj i nepreryvnoj optimizacii. Chislo Frobeniusa [Discrete and Continuous Optimization Problems. Frobenius number] / V.P. Savel'ev. – LAP LAMBERT Academic Publishing, 2020. – 134 p. [in Russian]

References

Alfonsin J.R. The Diophantine Frobenius Problem / J.R. Alfonsin. – Oxford University Press, 2005. – 243 p.
Shevchenko V.N. Zadacha o razmene, zadacha Frobeniusa i zadacha gruppovoj minimizacii [The Exchange Problem, the Frobenius Problem, and the Group Minimization Problem] / V.N. Shevchenko // Kombinatorno-algebraicheskie metody v prikladnoj matematike [Combinatorial Algebraic Methods in Applied Mathematics]. – Gorky: Gorky University Publishing House, 1982. – P. 166–179. [in Russian]
Shevchenko V.N. Qualitative topics of linear and integer programming / V.N. Shevchenko. – Providence : AMS, 1996.
Selmer E.S. On the linear Diophantine problem of Frobenius in three variables / E.S. Selmer, O. Beyer // J. Reine Angewandte Math. – 1978. – № 301. – P.161–170.
Rodseth O.J., On a linear Diophantine problem of Frobenius / O.J. Rodseth // J. Reine Angewandte Math. – 1978. – № 301. – P.171–178.
Curtis. F. On formulas for the Frobenius number of a numerical semigroup / F. Curtis // Math. Scand. – 1990. – № 67. – P. 190–192.
Johnson S.M. A linear Diophantine Problem / S.M. Johnson // Can. J. Math. – 1960. – № 12. – P. 390–398.
Greenberg Solution to a Diophantine Equation for nonnegative integers / H. Greenberg // J. Algorithm. – 1988. – № 9(3). – P. 343–353.
Brauer A. On a problem of partitions / A. Brauer // Am. J. Math. – 1942. – № 64. – P. 299–312.
Savel'ev V.P. Algoritm vychislenija chisla Frobeniusa dlja treh natural'nyh chisel [Algorithm for Calculating Frobenius Number for Three Natural Numbers] / V.P. Savel'ev // Sbornik nauchnyh trudov 83-ej Mezhdunarodnoj konferencii Evrazijskogo Nauchnogo Ob'edinenija [Proceedings of the 83rd International Conference of the Eurasian Scientific Association]. – Moscow: ESA, 2022, – P. 19–22. [in Russian]
Savel'ev V.P. Zadachi diskretnoj i nepreryvnoj optimizacii. Chislo Frobeniusa [Discrete and Continuous Optimization Problems. Frobenius number] / V.P. Savel'ev. – LAP LAMBERT Academic Publishing, 2020. – 134 p. [in Russian]

Review

All articles are peer-reviewed. But the reviewer or the author of the article chose not to publish a review of this article in the public domain. The review can be provided to the competent authorities upon request.

Author information

ORCID:0000-0002-6578-7022
AffiliationNizhny Novgorod State University of Engineering and Economics, Knyaginino, Russian Federation
Role:Author, Methodology, Writing, reviewing and editing, Draft writing and preparation
AffiliationNizhny Novgorod State University, Nizhny Novgorod, Russian Federation
Role:Author, Conceptualization, Management

Article metrics

Downloads:34

ViewsDownloads

Views

Total: