On the Two Properties of the Frobenius Number

Research article
DOI:
https://doi.org/10.23670/IRJ.2022.123.59
Issue: № 9 (123), 2022
Suggested:
28.07.2022
Accepted:
02.09.2022
Published:
16.09.2022
2267
26
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.

1. Введение

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

Для натуральных чисел img определим аддитивную полугруппу img, порожденную этими числами. Отметим, что любой элемент img полугруппы img может быть представлен в виде линейной комбинации вида  img

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

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

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

2. Свойство 1

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

Действительно, пусть каждое из img чисел img принадлежит полугруппе img. Поскольку img одно из чисел исходного множества img, то прибавив его к каждому из чисел img, мы получим следующие img чисел img, так же принадлежащих полугруппе img, и так далее по индукции.

Этот простой факт можно сформулировать и по-другому: необходимым условием того, чтобы число img являлось числом Фробениуса для исходного множества натуральных чисел img является принадлежность последовательных натуральных чисел img полугруппе img, где img – одно из чисел img. Если же удается показать, что число img не принадлежит аддитивной полугруппе img, то это условие становится и достаточным.

Свойство 1. Пусть img. Тогда справедлива формула

img
(1)

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

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

img
(2)

В частности, при i=a имеем равенство img, которое означает, что img. Действительно, коэффициент img не может быть положительным, ибо в этом случае получится противоречие с определением числа Фробениуса:

img

Что касается остальных img чисел img, то можно утверждать, что все коэффициенты img.

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

img
(3)

Если же img, то для всех img получим противоположное неравенство

img
(4)

Отсюда следует, что все числа img, то есть, числа img, входят в состав полугруппы img.

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

img
(5)

входящих в состав полугруппы img. В то же время, число img не может входить в состав img поскольку  img.

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

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

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

img
(6)

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

img
(7)

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

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

img
(8)

Действительно, если число img является целым числом p, то число img и по определению img. Если число img, то img и img. Если число img, то img, и img. Наконец, если число img, то img, и img.

В частности, для трех последовательных натуральных чисел img число Фробениуса в соответствии с формулой Брауэра равно:

img
(9)

3. Свойство 2

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

img
(10)

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

 

img
(11)

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

 

img
(12)

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

img
(13)

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

Докажем, что при img, имеет место формула

img
(14)

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

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

img
(15)

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

img

img

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

img

img

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

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

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

img
(16)

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

img
(17)

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

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

img
(18)

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

img
(19)

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

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

Итак, все img последовательных натуральных чисел, начиная с числа img, принадлежат полугруппе img. Отсюда следует, в соответствии с утверждением 1, что все натуральные числа, начиная с числа img будут принадлежать этой полугруппе, что и означает справедливость формулы (10) и свойства 2.

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

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

Article metrics

Views:2267
Downloads:26
Views
Total:
Views:2267