По любому натуральному n строится последовательность s(n) = {s1, ..., sk, ...}:
s1=n, sk+1=sk/2, если sk четно, sk+1=(3sk+1)/2, если sk нечетно.
В математическом фольклоре s(n) известна много лет под названием сиракузская последовательность. Значения s(n), вычисленные на компьютере для всех n<240, после хаотического блуждания с завораживающим постоянством приходят к 1.
Пример s(31) приходит к 1 за 68 шагов: 31, 47, 71, 107, 161, 242, 121, 182, 91, 137, 206, 103, 155, 233, 350, 175, 263, 395, 593, 890, 445, 668, 334, 167, 251, 377, 566, 283, 425, 638, 319, 479, 719, 1079, 1619, 2429, 3644, 1822, 911, 1367, 2051, 3077, 4616, 2308, 1154, 577, 866, 433, 650, 325, 488, 244, 122, 61, 92, 46, 23, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1.
Верно ли, что s(n) при всех n приходит к 1, а точнее - к циклу 1<->2 ?
Эта нерешенная (3n+1)-проблема известна с 1930 года.
Аналогично формулируется (3n-1)-проблема:
По любому натуральному n строится последовательность s(n) = {s1,... sk, ...},
s1=n, sk+1=sk/2, если sk четно, sk+1=(3sk-1)/2, если sk нечетно.
Верно ли, что s(n) при всех n приходит либо к 1, либо к одному из двух циклов ? Вскоре вы узнаете, что это за циклы.
Ниже предлагается новый подход к (3n+1)-проблеме и к (3n-1)-проблеме.
Возможно, его развитие поможет в дальнейшем решить эти проблемы.
1. Проверьте, что 1<->2 - цикл в (3n+1)-проблеме. Проверьте, что 1 - неподвижная точка в (3n-1)-проблеме. Найдите 2 цикла в (3n-1)-проблеме.
Предположим на минуту, что верна следующая теорема: ни в (3n+1)-проблеме, ни в (3n-1)-проблеме нет других циклов. Следует ли из нее положительное решение (3n+1)-проблемы и (3n-1)-проблемы?
2. Сравните первые серии нечетных чисел в сиракузской
последовательности s(15) в (3n+1)-проблеме и в
последовательности s(17) в (3n-1)-проблеме:
15, 23, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1.
17, 25, 37, 55, 82, 41, ...
С точностью до 1 числа в обеих сериях - это подчиняющиеся красивому закону (какому?) числа 16, 24, 36, 54, 81. Чтобы отметить, что 1 вычитается из всех этих чисел (или прибавляется ко всем этим числам), заключим их в скобки:
15, 23, 35, 53, 80 = -1 + [16, 24, 36, 54, 81],
17, 25, 37, 55, 82 = 1 + [16, 24, 36, 54, 81].
Рассмотрите другие примеры, например, следующие 3 серии в (3n+1)-проблеме:
31, 47, 71, 107, 161, 242; 7, 11, 17, 26; 87, 131, 197, 296.
Попробуйте найти общее правило и описать каждую серию нечетных чисел (с четным числом в конце серии) с помощью всего двух чисел: "коэффициента c и степени d".
3. Вот s(27) в (3n+1)-проблеме: 27, 41, 62, 31, 47, 71, 107, 161, 242, 121, 182, 91, 137, 206, 103, 155, 233, 350, 175, 263, 395, 593, 890, 445, 668, 334, 167, 251, 377, 566, 283, 425, 638, 319, 479, 719, 1079, 1619, 2429, 3644, 1822, 911, 1367, 2051, 3077, 4616, 2308, 1154, 577, 866, 433, 650, 325, 488, 244, 122, 61, 92, 46, 23, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1. Рассмотрим серии нечетных чисел (с четным числом в конце каждой серии):
27, 41, 62 = -1 + [28, 42, 63]
31, 47, 71, 107, 161, 242 = -1 + [32, 48, 72, 108, 162, 243]
121, 182 = -1 + [122, 183]
91, 137, 206 = -1 + [92, 138, 207]
103, 155, 233, 350 = -1 + [104, 156, 234, 351]
175, 263, 395, 593, 890 = -1 + [176, 264, 396, 594, 891]
445, 668, 334 = -1 + [446, 669], 334
Стоп! Мы встретили 2 четных числа подряд (668, 334), это (по ОПРЕДЕЛЕНИЮ) КОНЕЦ ЦЕПОЧКИ.
Представим эту ЦЕПОЧКУ в виде последовательности {c,d}-пар (с четным числом 334 в конце): {7,2} {1,5} {61,1} {23,2} {13,3} {11,4} {223,1}, 334.
Пояснение. [28, 42, 63] = 7*[22, 2*3, 32] <-> {7,2} . Сравните с предыдущей задачей 2, где [16=24, 24=23*3, 36=22*32, 54=2*33, 81=34] <-> {1,4} .
Итак, я предлагаю
1) выписывать {c,d}-ПАРЫ вместо ЧИСЕЛ,
2) рассматривать ЦЕПОЧКИ {c,d}-пар (с четным числом в конце каждой цепочки).
3) ассоциировать s(n) с множеством цепочек.
4. Будьте внимательны со следующими сериями нечетных чисел:
167, 251, 377, 566 = -1 + [ ]
283, 425, 638 = -1 + [ ]
319, 479, 719, 1079, 1619, 2429, 3644, 1822 = -1 + [ ], 1822,
первая строчка 167, 251, 377, 566 начинается РАНЬШЕ (я предлагаю всегда начинать цепочки с нечетных чисел, кратных трем):
111, 167, 251, 377, 566 = -1 + [112, 168, 252, 378, 567] = -1 + 7*[16, 24, 36, 54, 81] <-> {7,4},
так что первая {c,d}-пара в этой цепочке - {7,4}. Каковы остальные {c,d}-пары в этой цепочке? Постарайтесь дать точное определение ЦЕПОЧЕК в (3n+1)-проблеме.
5. Продолжите (рассмотрите соответствующие {c,d}-пары и цепочки): 911, 1367, 2051, 3077, 4616, 2308, 1154, 577, 866, 433, 650, 325, 488, 244, 122, 61, 92, 46, 23, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1.
Некоторые из них мы обсудим подробнее в разделе "Основные задачи".
Верны ли в (3n+1)-проблеме следующие утверждения I и II?
I. Для любого n>2, n не равно 0 (mod 6), существует ровно одна пара (a,b), такая что s(6a+3) содержит n, s(n) содержит 6b+4 и отрезок [s(6a+3),s(6b+4)] не содержит других чисел = 4 (mod 6).
II. В любой цепочке {c1,d1},...,{cn,dn} все ck различны.
III. Сколь длинными бывают цепочки? (Сколько {c,d}-пар могут они содержать?)
6. В (3n-1)-проблеме аналогом утверждения I является утверждение
I'. Для любого n>2, n не равно 0 (mod 6), существует ровно одна пара (a,b), такая что s(6a+3) содержит n, s(n) содержит 6b+2 и отрезок [s(6a+3),s(6b+2)] не содержит других чисел = 2 (mod 6).
Формально в (3n-1)-проблеме утверждения I' и II неверны, но вероятно, имеется лишь 4 контрпримера к ним: 3 числа, не удовлетворяющих I' и 1 цепочка, не удовлетворяющая II. Найдите их.
7. a. Если гипотеза о сиракузской последовательности верна, то все натуральные n>2, n не равно 0 (mod 6), являются вершинами дерева T. В (3n+1)-проблеме некоторые нечетные числа в s(n) равны 1 (mod 3), некоторые равны 2 (mod 3), а некоторые равны 0 (mod 3). Как это связано со степенями вершин T? Сформулируйте правило.
b. Сформулируйте аналогичное правило для (3n-1)-проблемы.
Длина и структура цепочки В соответствии с утверждением I и с 7a, возьмем любую цепочку (a,b), т.е. отрезок [6a+3, 6b+4] последовательности s(6a+3) до первой пары 12b+8, 6b+4 четных чисел подряд. Пока это лишь экспериментальный результат, что для любого числа n>2, n не равно 0 (mod 6), последовательность s(n) содержит такую пару. Этот факт не доказан ни для всех n>2, ни для n=6a+3. Но имеется миллион примеров цепочек. Так что пусть (a,b) - одна из них. Разобьем отрезок [6a+3, 12b+8] цепочки (a,b) на куски, каждый из которых содержит одно или несколько нечетных чисел и ровно одно четное число (в конце каждого куска).
По определению число L этих кусков есть ДЛИНА цепочки, а
конечная последовательность d1, ...,
dL (где dk - число
нечетных чисел в k-ом куске) - СТРУКТУРА цепочки.
Последнее число последнего (L-го) куска - это первое в цепочке
число, кратное четырем, т. е. число вида 12b+8, выпишем вслед за
ним и число 6b+4. Пример:
d1=2 27 41 62
d2=5 31 47 71 107 161 242
d3=1 121 182
d4=2 91 137 206
d5=3 103 155 233 350
d6=4 175 263 395 593 890
d7=1 445 668 334
8. Попробуйте найти другую цепочку той же длины L=7 с той же структурой.
9. a) Возьмем любую конечную последовательность из нулей и единиц, например:
1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0.
Докажите, что найдется такое n, что в начальном отрезке s(n) на местах единиц будут стоять нечетные числа, а на местах нулей - четные числа.
b) Обратно, каждой s(n) можно сопоставить бесконечную последовательность из нулей и единиц (единицы соответствуют нечетным числам, а нули - четным числам). Покажите, что эти последоватедьности различны, если они сопоставлены различным s(n) и s(m).
10. Докажите, что для любого натурального L и любых натуральных d1, ..., dL существует цепочка со структурой d1, ..., dL.
11. Докажите следующую теорему:
Теорема 1. Пусть (a,b) - цепочка длины L со структурой d1, ..., dL.
Положим j=d1+...+dL,
i=j+L, A=2i,
B=3j, a'=a+A,
b'=b+B. Тогда
1) (a',b') - цепочка,
2) ее длина равна L, как и у цепочки (a,b),
3) ее структура: d1, ...,
dL, тоже как и у цепочки (a,b).
Итак, вместо миллиона примеров цепочек, теперь у нас есть бесконечное множество цепочек: вместе с любой цепочкой (a0,b0) у нас имеется бесконечная последовательность цепочек (ak,bk)=(a0,b0)+k*(A,B), k=1,2,3, ...
12. Докажите следующую теорему:
Теорема 2. Пусть (a,b) и (a',b') - 2 цепочки с одной и той же структурой d1, ..., dL, a'>a. Положим j=d1+...+dL, i=j+L, A=2i, B=3j. Тогда существует такое k, что a'=a+kA, b'=b+kB.
13. Докажите, что в (3n+1)-проблеме имеются цепочки со структурами
<1>, <1,1>, <1,1,1>, <1,1,1,1>, <1,1,1,1,1>, ...
<1>: c1 = 11 = 5*2+1, a0 = 3, b0 = 2,
<1,1>: c1 = 41 = 5*23+1, a0 = 13, b0 = 7,
<1,1,1>: c1 = 161 = 5*25+1, a0 = 53, b0 = 22,
<1,1,1,1>: c1 = 641 = 5*27+1, a0 = 213, b0 = 67,
<1,1,1,1,1>: c1 = 2561 = 5*29+1, a0 = 853, b0 = 202,
............................................................
a) Найдите остальные cj для этих цепочек,
b) Найдите рекуррентные формулы для a0 и b0,
c) Найдите cj, 1<j<6, и a0 и b0 для цепочки со структурой <1,1,1,1,1,1>.
14. Сформулируйте и решите задачу, аналогичную 13, для (3n-1)-проблемы.
15. a) Докажите для любого n=6a+3, что сиракузская последоватедьность s(n) не может зациклиться прежде, чем цепочка с началом n=6a+3 закончится, т. е. прежде, чем появятся числа 12b+8 и 6b+4. b) Можете ли вы получить тот же результат для любого n (n>2, n не равно 6a+3) ?