Задача А. Н. Колмогорова о циклах




Дата02.04.2016
Размер65.9 Kb.
Муниципальное бюджетное общеобразовательное учреждение г. Новосибирска «Гимназия № 1»

Задача А.Н. Колмогорова о циклах

Выполнил: Новиков Иван, ученик 11 «Е» класса МБОУ «гимназия №1»

Задачи:


В ходе решения задачи А. Н. Колмогорова о циклах

  1. Найти все числа, длина записи которых равна самому числу;

  2. Найти все циклы, построенные на многократном переходе от числа к длине его записи;

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

Каждое натуральное число n можно записать словами русского языка суммарной длины k. Рассмотрим функцию k(n) – число букв в записи числа. Функция k будет также натуральным числом. Таким образом, с каждым числом n можно сопоставить другое натуральное число, равное k(n).

Например, числу 1 (один) соответствует число 4.

1 → 4.

Числу 34 (тридцать четыре) соответствует число 14.



34 → 14

Рассмотрим первые 20 чисел



n

запись

k(n)

1

один

4

2

два

3

3

три

3

4

четыре

6

5

пять

4

6

шесть

5

7

семь

4

8

восемь

6

9

девять

6

10

десять

6

11

одиннадцать

11

12

двенадцать

10

13

тринадцать

10

14

четырнадцать

12

15

пятнадцать

10

16

шестнадцать

11

17

семнадцать

10

18

восемнадцать

12

19

девятнадцать

12

20

двадцать

8

Среди них есть 2 числа, для которых n=k(n): это 3 и 11.

Также среди них есть три числа, образующих цикл: 4 → 6 → 5→ 4.



Задача А. Н. Колмогорова заключается в том, чтобы найти все числа, для которых n=k(n), а также все циклы, подобные циклу 4 → 6 → 5→ 4, и доказать, что любое натуральное число можно, заменяя несколько раз n на k(n), привести к одному из циклов или чисел, для которых n=k(n).

Оценим сверху k(n) для различных значений n, при этом будем рассматривать 2 части записи, длину одной из которых мы оценили ранее. Например: двести пятьдесят три (длина части «пятьдесят три» оценена ранее). Ноль в любом из разрядов не произносится никаким образом.



  1. 20

Запись состоит из 2 частей: разряда десятков и разряда единиц. Длина записи разряда единиц не превышает 6, разряда десятков – 11 (у числа 8*). k(n)<=17. Т. к. для n<=20 k(n)<=17, то такая оценка справедлива для всех чисел от 1 до 99.

  1. 100<=n<999

Запись состоит из 2 частей: разряда сотен и оставшейся части. При этом оставшаяся часть является записью числа из случая 1, т. е. не превышающего 99. Длина первой части не превышает 9 (восемьсот для числа 8**), второй части – 17 (это следует из первого случая). k(n)<=26<100<=n. Т. к. для n<100 k(n)<=26, то такая оценка справедлива для всех чисел от 1 до 999.

  1. 1000<=n<999999

Запись состоит из 2 частей: первая обозначает количество тысяч, вторая (последние 3 цифры) – это разряды сотен, десятков и единиц. В отличие от двух первых случаев, первая часть всегда состоит из записи числа, не превышающего 999 (напр. семьсот пять, такие числа рассмотрены во 2 случае) и слова «тысяч» («тысяча» или «тысячи»). В первых двух случаях нет такого единообразия, окончания вида -сот чередуются с окончаниями вида –ста, -сти и –сто. Вторая часть – запись числа из п. 2, т. е. не превышающего 999 (см. случай 2). k(n)<=26+6+26. k(n)<=58. Теперь, рассуждая аналогично предыдущим случаям, расширяем оценку k(n)<=58 с множества 1000…999999 до множества 1…999999.

  1. 1000000<=n<999999999

Запись состоит из 2 частей: первая состоит из записи числа миллионов, не превышающего 999 (см. случай 2), и слова миллион («миллионов») вторая (последние 6 цифр) является записью числа, не превосходящего 999999, то есть рассмотренного в случае 3.

Можно сделать обобщение: k(n)<=k(n1)+k(n2)+λ, где n1 – целая часть при делении n на наибольшую степень числа 1000, не превышающую n, то есть на тысячу, миллион, миллиард, триллион и т. д n2 – остаток от деления, λ – длина слова, обозначающего вышеупомянутую степень 1000. Пример: 12 444 123 100, n1 =12 (двенадцать), n2 = 444 123 100 (четыреста сорок четыре миллиона сто двадцать три тысячи сто), λ = 8 (степень 1000 называется «миллиард»). Т. к. n1 <=999, то из случая 1 получаем, что k(n1)<=26. k(n)<=26+ k(n2)+λ



Наиб. степень 1000

Запись степени 1000

в падеже с наиб. λ



λ

Верхняя оценка k(n)

10000

-

0

26

10001

тысяча

6

26+26+6=58

10002

миллионов

9

58+9+26=93

10003

миллиардов

10

93+26+10=129

10004

триллионов

10

129+26+10=165

10005

квадриллионов

13

165+26+13=204

Проверено, что запись чисел от 1 до 26 содержит не более 17 букв, от 27 до 999 – не более 26 букв, то есть для всех n от 1 до 999 k(n)5 .

Т. к. существует лишь конечное количество названий степеней 1000, то функция k определена лишь на подмножестве натуральных чисел вида {1,2,3…999*1000p}. Среди степеней числа 1000 наиболее длинное название имеет 102920-я степень: дуцентдуомилианонгентновемдециллион. В этом названии 35 знаков.

В каждой строке таблицы, кроме первой, верхняя оценка k(n) меньше, чем наибольшая степень 1000, не превышающая числа (первый столбец). При переходе на строку вниз значение в 1 столбце увеличивается в 1000 раз, а в последнем – на 26 + длина слова, не превышающая 35.

Сравним числа 1000*a и b + 61, если b

1000*a=999*a+a, 999a>61, т. к. a>=1.

Значит, 1000*a>b + 61.

Эта задача стала заключительной в доказательстве утверждения 1:

Для всех чисел, превышающих 20, k(n)

Для чисел от 1 до 20 проверено, что каждое из них сводится к циклу или числам 3 или 11. Для всех остальных чисел при каждом подсчёте функции k число будет уменьшаться. Это значит, что циклов с участием чисел, превышающих 20, нет, а также каждое число, превышающее 20, при многократном подсчёте функции k станет <=20. В этом случае оно обязательно сведется к циклу или числам 3 или 11.



Выводы:

  1. проведена оценка длины записи натуральных чисел в различных промежутках;

  2. проведено решение задачи А. Н. Колмогорова о циклах;

  3. исследованы закономерности представления чисел в русском языке.


База данных защищена авторским правом ©uverenniy.ru 2016
обратиться к администрации

    Главная страница