Разбиение натурального ряда (стр. 3 из 3)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Где

Упражнение 4

Найти явные формулы для возрастающих последовательностей

и , заполняющих натуральный ряд без пропусков и перекрытий и удовлетворяющих соотношению при всех n= 1,2,3…

Итак, явные формулы для последовательностей доказаны.

§4. Геометрическая интерпретация

Удивительно простое и наглядное доказательство теоремы из § 1 получаем, если рассмотрим геометрическую интерпретацию.

Пусть, как и ранее, α и β – положительные иррациональные числа.

Причем

. Тогда , откуда .

Нарисуем на листе бумаги, как на координатной плоскости прямую l, заданную уравнением у=(α-1)x, которое можно записать так же в виде x=(β-1)y.

Занумеруем подряд все клетки, которые пересекают l, начиная с нулевой клетки, которой принадлежит начало координат (для … взято

α=

)

Если мы обозначим числа, стоящие над линией за a- числа, а под линией за b – числа то получатся две последовательности, о которых мы говорили в §1.

Поскольку число α иррационально, прямая l не проходит через узлы сетки. Значит, l входит в очередную клетку либо слева, пересекая вертикальную линию сетки, либо снизу, пересекая горизонтальную линию.

Если l вошла в клетку слева и пересекла при этом вертикаль х=n, то номер клетки, в которую при этом вошла прямая равен n+[( α-1)n]=[ αn].

Если же прямая l пересекла снизу горизонталь y=m, то номер соответствующей клетки равен [(β-1)m]+m=[βm].

§5. Некоторые приложения. Палиндромы

Обозначим натуральные числа принадлежащие последовательности a

буквой А, а принадлежащие последовательности - буквой В.построим последовательность.

АВААВАВААВААВАВААВАВААВААВАВААВААВАВААВАВААВАВАВА…

Рассмотрев последовательность повнимательнее, заметим, что ее можно разделить на палиндромы.

Определение: Палиндромы (перевертыш) – это слово, которое выглядит одинаково при чтении слова как слева направо, так и справа налево.

Примеры:

Шалаш, ротор или АВВАВАВВА.

Рассмотрим задачу, связанную с палиндромами (аналогичную задачу решал в своей статье Акулич)

Из букв А и В составлено 2010-буквенное слово. Докажите, что его можно разбить менее чем на 900 более коротких слов, каждое из которых является палиндромом.

Возьмем произвольное 2010-буквенное слово и разобьем его сначала на 5-буквенные – их будет всего 402. Каждое из этих 5-буквенных слов, в свою очередь, может быть составлено не более чем из двух палиндромов. Поэтому произвольное 2010-буквенное слово можно составить не более чем из 804 палиндромов, т.е. меньше чем из 900, что и требовалось доказать.

Чтобы решать такие задачи в общем виде, введем функцию f(n).Через нее обозначим такое наименьшее натуральное число, что всякое слово длиной n, составленное из букв А и В может быть разбито не более чем на f(n) палиндромов.

Упражнение 1

Придумайте слово из букв А и В которое нельзя разбить менее чем на 3 палиндрома, но которое после приписывания к нему справа или слева любой из букв А и В можно разбить на два палиндрома.

АВААВВ+А

Оказалось, что задачи можно решить в общем виде. Введем функцию f(n).

Через f(n) обозначим такое наименьшее число, что всякое слово длиной n, состоящее из букв А и В, может быть разбито не более чем на f(n) палиндромов.

Пример:

Найдем f(6). Всего шестибуквенных слов

но поскольку буквы А и В равноправны достаточно рассмотреть только слова начинающиеся на букву А

АААААА

ААААА+В

ААА+АВА

АААА+ВВ

А+ААВАА

ААА+ВАВ

АА+АВВА

ААА+ВВВ

ААВАА+А

АА+ВААВ

А+АВАВА

АА+ВАВ+В!

ААВВАА

А+АВВА+В!

А+АВВВА

АА+ВВВ

АВА+ААА

А+ВАААВ

АВА+АВА

АВА+А+ВВ!

АВАВА+А

АВАВА+В

АВА+ВВ+А!

АВА+ВВВ

АВВА+АА

АА+ВААВ

АВВА+В+А!

АВВА+ВВ

АВВВА+А

АВВВА+В

АВВВВА

А+ВВВВВ

Восклицательными знаками отмечены слова, которые нельзя разбить менее чем на три палиндрома. Ясно, что всякое шестибуквенное слово можно разбить не более чем на три палиндрома. Ниже приведем 10 значений функции f

n	1	2	3	4	5	6	7	8	9	10
f(n)	1	2	2	2	2	3	3	4	4	4
n/f(n)	1	1	1.5	2	2.5	2	2.33	2	2.25	2.5

n/f(n) – это средняя длина палиндромов, на которые разбито самое трудно разбиваемое n- буквенное слово.

Упражнение 2

Для каждого n- 1,2,3,…10 укажите слово длиной n из букв А и В, которое нельзя разбить менее чем на f(n) палиндромов.

n=1 А

n=2 ВВ

n=3 АВВ

n=4 ААВВ

n=5 АВАВВ

n=6 АВААВВ

n=7 ВАВААВВ

n=8 ВВААВВАА

n=9 АВАВАВААВ

n=10 АВАВАВАВВВ

В статье А. Баабабоваприведена теорема:

При любом натуральном n имеем f(3n)=n+1, f(3n+1)=n+1, f(6n+2)=2n+2.при любом натуральном n>1 имеем f(6n+5)=2n+2, исключительное значение f(11)=5.

Следствие из теоремы

Предел

существует и равен 3.

Каждое слово из n букв А и В может быть разбито не более чем на [(n+4)/3] палиндромов.

4)f(6k+5) = 2k+2

.

Итак, в каждом из случаев получаем один и тот же предел 3.

Следовательно

ЗАКЛЮЧЕНИЕ

В процессе работы над темой нами были изучены вопросы о разбиениях натурального ряда на две непересекающиеся возрастающие последовательности, также были решены самостоятельно 6 упражнений, доказано следствие к теореме из § 3.

Литература

1. Акулич И.Ф. Ум хорошо, а пять лучше // Квант. – 1998. - №6

2.Баобабов А. «Пентиум» хорошо, а ум лучше // Квант.-1999. - №4,№5

3. Зайцев В.В., Рыжков В.В., Сканави М.И. Элементарная математика М.Наука, 1976

4. Макарычев Ю.Н., Миндюк Н.Г., Нешков К.И., Суворова С.Б. Алгебра 8 класс. М. Просвещение, 1996