О двух свойствах числа Фробениуса

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

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

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

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

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

Утверждение 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)

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

(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.

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