Проблема Фробениуса

Пусть А = {aif..., ak} — возрастающая последовательность натуральных чисел, k > 1, (А) — аддитивная полугруппа, порожденная множеством А. Полугруппа (А) состоит из всех линейных комбинаций чисел av ..., ak с целыми неотрицательными коэффициентами.

Множество А называется примитивным, если НОД(я 1?ak) = 1.

Теорема 2.21. Если множество А примитивное, то найдется s е N такое, что t е (А) при любом натуральном t > s.

4 Для примитивного множества А по теореме 2.8 найдутся целые числа сХу ст такие, что схах + ... + стат = 1. В левой части данного выражения обозначим р и -q суммы положительных и отрицательных слагаемых. Тогда р, q е (А), и р - q = 1. Любое число t > 0 разделим с остатком на ах: t = axh + г, где h > 0 и 0 < г < ах. Тогда х - 1 )q + t = axh + (aj - 1 - r)q + + rp e (А). Значит, все натуральные числа t > (ах - 1 )qy принадлежат (А). ? Число Фробениуса g(a{y ..., ak) определено для любого примитивного множества Л,..., ak) при ах> 1 как наибольшее натуральное число t ? (Л), т.е. число, не представимое в виде линейной комбинации чисел а ..., ak с неотрицательными целыми коэффициентами. При ах = 1 полагаютg(l, а2, ак) = -1.

Обозначим С(А) множество всех чисел t и определим число Фробениуса: g(A) = g(a{} ak) = тахС(Л). Определение g(ax, ..., ak) известно как диофантова проблема Фробениуса (ПФ). Определение множества С(А) называется расширенной проблемой Фробениуса (РПФ).

Опубликован обзор результатов[1] до 2005 г. ПФ и РПФ для k = 2 решены[2] еще в 1884 г.:

Алгоритм решения РПФ при k = 3 получен в [11], оценена сложность алгоритма. Отметим, что активно изучались свойства множества С(А), первые результаты получены Сильвестром.

Формула решения ПФ при k > 2 не была получена, уже при k = 3 доказано[3], что не найдется конечного числа полиномов, выражающих в общем случае число g(av аъ ci%) с помощью разбиения области определения. Точные формулы имеются лишь для частных случаев.

Более продуктивным был алгоритмический подход к ПФ. Представлен [21] теоретико-графовый алгоритм определения g(a{y ..., ak) со сложностью 0(ax(k + log<2j)), ПФ сведена к поиску определенного вида наибольшего кратчайшего пути в орграфе с ах вершинами и с kax дугами, где из каждой вершины исходит k дуг весов ах, ..., соответственно. В [16] оценка сложности ПФ снижена до величины 0(kax). В [14] для РПФ и ПФ предложена редукция множества А к собственному подмножеству, снижающая сложность задачи в ряде случаев.

Алгоритмы не дают аналитической формулы для ПФ. Однако некоторые аналитические оценки могут быть полезны для различных приложений, например,

а также оценка Брауэра1 (здесь dj = НОД(«1,af), i = 2,/

  • [1] AlfonsinJ. R. The Diophantine Frobenius Problem. Oxford University Press, 2005.
  • [2] SylvesterJ.J. “Problem 7382”, Educational Times 37 (1884), 26; reprinted in “Mathematicalquestions with their solution”, with additional papers and solutions, Educational Times 41 (1884).P.21.
  • [3] Curtis F. On formulas for the Frobenius number of a numerical semigroup, Math. Scand.67 (1990). P. 190-192.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >