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

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

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

Примеры:

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

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

Из букв А и В составлено 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). Всего шестибуквенных словно поскольку буквы А и В равноправны достаточно рассмотреть только слова начинающиеся на букву А

АААААА

ААААА+В

ААА+АВА

АААА+ВВ

А+ААВАА

ААА+ВАВ

АА+АВВА

ААА+ВВВ

ААВАА+А

АА+ВААВ

А+АВАВА

АА+ВАВ+В!

ААВВАА

А+АВВА+В!