Разбиение натурального ряда

научная работа

§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.

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

Делись добром ;)