Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/1998/06/kv0698kaleid.pdf Дата изменения: Fri Dec 23 19:24:49 2005 Дата индексирования: Tue Oct 2 00:34:32 2012 Кодировка: Windows-1251 Поисковые слова: clouds

КАЛЕЙДОСКОП

'КВАНТА'

третьем туре предыдущего конкурса 'Математика 68' с легкой руки Анатолия Павловича Савина была предложена следующая задача: В последовательности a1 , a2 , a3 , ... число a1 равняется 1799, а число a2 равняется 1828. Каждое из следующих чисел находится по закону an +1 = n . Чему равняется an-1 a1997 ? Несколько неожиданным представляется тот факт, что, начиная с шестого номера, значения членов последовательности an повторяются: a6 = a1 , a7 = a2 , a8 = a3 и т.д. Обнаружив и обосновав эту закономерность, уже без труда можно рассчитать величину a1997 = a5399 + 2 = = a2 = 1828. Некоторые школьники сочли, что с этой задачей играючи справится компьютер. Для этого достаточно составить простенькую программу, что-то вроде: aпред пред : = 1799 ; aпред : = 1828 ; i : = 2; начало цикла пока i < 1997 i : = i + 1; a : = aпред + 1 aпред пред ; aпред пред : = aпред ;
a +1

В

Замечательные последовательности
дательному исследователю возможную закономерность, наличие же ее нужно обосновывать иным способом, например с помощью алгебраических выкладок. Кстати, для обоснования периодичности последовательности an недостаточно убедиться лишь в единичном совпадении a6 = a1 , как это сделали некоторые из участников конкурса. Каждый член последовательности an зависит от двух предыдущих членов, поэтому необходимо обязательно убедиться также в том, что a7 = = a2 . Замечательные числовые последовательности частые гости у тех, кто подружился с числами. Возьмем первые 9 членов арифметической прогрессии 143, 286, 429, ..., 1287 и умножим их на число 777. В итоге получим последовательность 111111, 222222, 333333, ..., 999999. Этот пример умножения 'с некоим удивлением' приводит уже автор первого российского учебника по математике Леонтий Магницкий (1669 1739). Следующая замечательная последовательность описана в книге Жака Арсака 'Программирование игр и головоломок' (М.: Наука, 1990). В качестве начального члена последо-

mr

mr

вательности выберем произвольное натуральное число. Все остальные члены последовательности получаются по правилу: за любым элементом последовательности следует число, равное сумме кубов всех цифр данного элемента. Например, b1 = 27 ; 3 3 b2 = 2 + 7 = 8 + 343 = 351 ;
b3 = 3 + 5 + 1 = 27 + 125 + 1 = 153 ; 3 3 3 b4 = 1 + 5 + 3 = 153 ;
3 3 3

lq

e

j

и т.д. Любопытно, что какое бы начальное число b1 , делящееся на 3, мы ни взяли, рано или поздно мы неизбежно придем к числу 153. Этот замечательный факт помог доказать компьютер. Прежде всего заметим, что все члены последовательности bn принадлежат единому семейству чисел, кратных трем (пожалуйста, убедитесь в этом самостоятельно). Далее замечаем, что для элемента последовательности bn , больше некоторого порога, следующий элемент bn+1 всегда меньше своего предшественника. Действительно, для k-значного числа bn сумма кубов его цифр огра3 ничена сверху числом k 9 = 729k. 4 При k 5 имеем bn 10 > 3645 =

mr

a

конец цикла; вывод а. Рассуждавшие так попали в ловушку! Дело в том, что с абсолютной точностью компьютер умеет обрабатывать лишь целые числа, а вот дробные числа, хотя и с достаточно высокой точностью, вычисляются им приближенно. Так, например, для числа a1997 железный вычислитель может выдать результат 1,828000 000000 0000 10 3 , гарантируя лишь 16 точных значащих цифр после запятой. Что располагается начиная с 17-го места после запятой и далее для компьютера 'покрыто мглой'. В данном случае он может лишь подсказать наблю-

пред

:= a


!

!
$ ' &
Рис. 3

#
!

" #

%

!

"
Рис. 2

Рис. 1



= 729 5 bn +1 . Итак, порог это 4 число 10 . Достаточно проверить справедливость связанного с числом 153 замечательного факта для всех кратных трем чисел от 1 до 104 , и мы тем самым докажем его справедливость для всех остальных чисел данного семейства. Вот здесь-то как раз и может пригодиться компьютер! Рассмотрим другую замечательную последовательность. В качестве начального элемента выберем четырехзначное натуральное число, не все цифры которого равны между собой. Переход от данного элемента последовательности к следующему производится по такому правилу. Расположим десятичные цифры в записи данного числа в порядке убывания слева направо получим первое число. Расположим их в обратном порядке и вычтем это второе число из первого. Таким образом получаем следующий элемент последовательности. Как ведут себя члены такой последовательности? Следующая числовая последовательность: 11, 101, 1001, 10001, ..., 100...001, ... обладает загадками иного рода. Сразу можно заметить, что члены этой последовательности, содержащие четное число нулей, делятся на 11 (быстро убедиться в этом помогает известный признак делимости на 11: число делится на 11, если в десятичной записи этого числа сумма цифр, стоящих на четных местах, равна сумме цифр, стоящих на нечетных местах). Элементы последовательности с нечетным количеством нулей также обнаруживают некоторые закономерности. Для всех n = 0, 1, 2, ... числа 101+ 2 n + 1 делятся на 11; 2+ 4 n числа 10 + 1 делятся на 101; 4+8n числа 10 + 1 делятся на 73; 8 +1 6 n числа 10 + 1 делятся на 17; ...

Открытым остается вопрос: всяk кое ли число вида 10 + 1 составное (здесь k натуральное)? Замечательные последовательности можно искать не только в мире чисел, но и в мире фигур. Пусть на плоскости задано некоторое множество точек, пронумерованных от 1 до n. Конфигурацию этих точек будем наращивать по следующему правилу. Начнем соединять отрезками точку 1 по порядку с другими точками, имеющими больший номер: с точкой 2, с точкой 3 и т.д. Затем ту же операцию произведем, отправляясь от точки 2, от точки 3 и т.д. (точка с меньшим номером всегда соединяется с точкой с большим номером). Каждый раз, когда на пересечении отрезков образуется одна новая точка, она получает следующий по порядку незанятый номер: n + 1, n + 2 и т.д. Если проводимый отрезок пересекает сразу несколько других отрезков нумерация вновь образованных точек производится в по-

рядке возрастания от точки с меньшим номером в сторону точки с большим номером. Легко заметить, что 3 точки на плоскости не порождают новых точек (рис.1), 4 точки могут породить одну-единственную пятую точку (рис.2). Чудеса начинаются, когда в исходной конфигурации участвуют 5 точек. Вообще говоря, 5 точек это 'критическая масса', с которой начинается 'цепная реакция': необузданный рост новых точек (рисунок 3 конфигурация после соединения точек 1, 2, 3, 4 с другими точками). Однако существуют такие исходные конфигурации, когда рост новых точек производится 'равномерно' (на рисунке 4 показана конфигурация после соединения точек 1, 2, ..., 13 с другими точками). Существует ли исходная конфигурация из 6 и большего количества точек, обладающая этим же свойством? А.Жуков
!

%

$ "

! '

&



Рис. 4

"

#