Задача Знама

 В теории чисел задача Знама спрашивает, какие множестваk целых чисел имеют свойство, что каждое целое в множествеявляется собственным делителем произведения других целых чисел вмножестве плюс 1. Задача Знама названа по имени словацкого математикаСтефана Знама, который предложил задачу в 1972, хотя другие математикирассматривали похожие задачи приблизительно в то же время. Близкаязадача не требует, чтобы делитель был собственным делителем, иназывается несобственной задачей Знама.
 Одно решение несобственной задачи легко получить для любого k —первые k членов последовательности Сильвестра имеют требуемыесвойства. Сан показал, что имеется по меньшей мере одно решение(собственной) задачи Знама для любого k ≥ 5. Решение Санаосновывается на рекуррентном соотношении, подобном соотношению дляпоследовательности Сильвестера, но с другим множеством начальныхзначений.
 Задача Знама тесно связана с египетскими дробями. Известно, чтосуществует лишь конечное число решений для любого фиксированногоk. Неизвестно, имеются ли решения задачи Знама только с нечётнымичислами. Имеются также некоторые другие открытые проблемы.

Задача


 Задача Знама спрашивает, какие множества k целых чисел имеютсвойство, что каждое целое в множестве является собственным делителемпроизведения других целых чисел в множестве плюс 1. То есть, если даночисло k, какие существуют множества целых чисел
{n1,,nk}
, таких, что для любого i числоni делит, но не равен
(jinnj)+1

 Близкая задача касается множества целых чисел, которые являютсяделителями произведения остальных чисел плюс единица, но не обязательноэти делители должны быть собственными. Не похоже, что данная задача влитературе получила устойчивое имя, и мы будем её называть несобственнойзадачей Знама. Любое решение задачи Знама является также решениемнесобственной задачи Знама, но обратное не всегда верно.

История


 Задача Знама названа по имени словацкого математика Стефана Знама,который предложил задачу в 1972. Барбо предложил несобственную задачуЗнама для k = 3, а Морделл, нашёл все решения несобственнойзадачи для k ≤ 5. Скула показал, что задача Знама не имеетрешений для k \textless 5, и приписывает Я. Янаку нахождениерешения \{2, 3, 11, 23, 31\} для k = 5.

Примеры


 Одно из решений для k = 5 равно \{2, 3, 7, 47, 395\}. Несложныевычисления показывают, что
 :\{\textbar \textbaralign=``right'' \textbar 3 × 7 × 47 × 395\textbar\textbar + 1 = \textbar\textbar 389866,\textbar\textbar   \textbar\textbar делится на 2, но не равно 2,\textbar- \textbaralign=``right'' \textbar 2 × 7 × 47 × 395\textbar\textbar + 1 = \textbar\textbar 259911,\textbar\textbar   \textbar\textbar делится на 3, но не равно 3,\textbar- \textbaralign=``right'' \textbar 2 × 3 × 47 × 395\textbar\textbar + 1 = \textbar\textbar 111391,\textbar\textbar   \textbar\textbar делится на 7, но не равно 7,\textbar- \textbaralign=``right'' \textbar 2 × 3 × 7 × 395\textbar\textbar + 1 = \textbar\textbar 16591,\textbar\textbar   \textbar\textbar \textbarделится на 47, ноне равно 47 \textbar- \textbaralign=``right'' \textbar 2 × 3 × 7 ×47 \textbar\textbar + 1 = \textbar\textbar 1975,\textbar\textbar   \textbar\textbar делится на 395, но не равно395. \textbar\}
 Интересное ``чуть не решение'' для k = 4 — множество \{2, 3, 7,43\}, образованное четырьмя первыми членами последовательностиСильвестера. Множество имеет свойство, что каждое целое число вмножестве делит произведение других членов множества плюс 1, нопоследний член этого множества равен произведению первых трёх членовплюс единица, так что этот член не является собственным делителем. Такимобразом, это решение является решением несобственной задачи Знама, а незадачи Знама.

Связь с египетскимидробями


 Любое решение несобственной задачи Знама эквивалентно решению уравнения
1xi+1xi=y,
(Ф1) где y, как и любойxi, должен быть целым числом. Чтобы этопоказать, рассмотрим

Xi=jinxj (Ф2)
 Заметим, что все xi должны быть взаимно просты (иначе общий делительxi и xj должен делить Xi и Xi+1). Положим
N=1nXi+1
(Ф3) По тем же причинам, что и выше, любоеxi делит N, а поскольку они все взаимнопросты, N делится напроизведение jinxj. Разделим теперь обе частиуравнения (Ф3) на jinxj, получим (Ф4)
 Обратно — все решения уравнения (Ф1) соответствуют решениямнесобственной задачи Знама. Однако для всех известных решений y =1, так что они удовлетворяют уравнению
1xi+1xi=1.
(Ф4)
 Таким образом, это ведёт к представлению числа единица в виде египетскойдроби, суммы долей единицы. Некоторые из цитируемых статей о задачеЗнама изучают также решения этого уравнения. Брентон и Хилл описываютприложение уравнения (Ф4) в топологии для классификации особенностейповерхностей, а Домарацки и др. описывают приложение к теориинедерминированных конечных автоматов.

Числорешений


 Как показали Янак и Скула, число решений для любого k конечно,так что имеет смысл посчитать общее число решений для каждого k.
 Брентон и Василиу после вычислений нашли, что число решений для малыхзначений k, начиная с k = 5, образуют последовательность

 2, 5, 18, 96 .
 На настоящий момент несколько решений известны для k = 9 иk = 10, но не известно, сколько решений осталось не найдено дляэтих значений. Однако, если k не фиксировано, существуетбесконечно много решений — Цао и Цзин показали, что имеется по меньшеймере 39 решений для любого k ≥ 12, что улучшает более раннийрезультат, в котором доказано существование меньшего количества решений.Сан и Цао высказали предположение, что число решений для каждогоk растёт монотонно от k.
 Неизвестно, имеется ли какое-либо решение задачи Знама только снечётными числами. За одним исключением, все известные решенияначинаются с 2. Если все числа в решении задачи Знама или несобственнойзадачи Знама являются простыми, их произведение является . Неизвестно,существует ли бесконечное число решений этого вида.