Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/1999/05/41.pdf Дата изменения: Fri Dec 23 19:25:27 2005 Дата индексирования: Tue Oct 2 00:24:44 2012 Кодировка: Windows-1251

МАТЕМАТИЧЕСКИЙ

КРУЖОК

41

каждую букву а на АА, б на ББ, в на АБ. Получим слово ААББАБААББАБААББАБ ... ААББАБ ... Самые длинные палиндромы в этом слове АББА и БААБ имеют длину 4. Рассмотрев любое n-буквенное подслово этого слова, получаем неравенство f(n) n/4. Значит, отношение n/f(n) ограничено сверху числом 4. А теперь самое интересное. По-видимому, верна следующая теорема. Теорема 2. При любом натуральном 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. n Следствие. Предел lim существует и равен 3. n f n К сожалению, доказательство этой теоремы требует довольно большого перебора. Но главная идея может быть изложена довольно-таки коротко: каждое слово из n букв А и Б может быть разбито не более чем на [(n + 4)/3] палиндромов. Это легко доказать по индукции: база очевидна, а переход состоит в следующем. Если мы от слова сумеем отрезать начало длиной 3s или более, которое можно разбить на s палиндромов, то мы победили. Поэтому будем рассматривать только слова, в которых этого сделать нельзя. Довольно скучный перебор показывает, что есть всего одна неприятная возможность это

bg

АБААББ(БААБАБ)(БААБАБ)..., где БААБАБы бесконтрольно размножаются. С этим словом надо разобраться индивидуально. (Проделайте эту работу!) К сожалению, неравенства f(n) [(n + 4)/3] (3) недостаточно для доказательства теоремы 2. Нужно еще убедиться, что при n = 6k + 5, где k > 1, неравенство строгое. При n 17 это верно. Если n > 17, то рассмотрим начало n-буквенного слова первые его 6 букв. Будем считать, что слово начинается на букву А. Если начало можно разбить не более чем на 2 палиндрома, то все в порядке. Значит, осталось рассмотреть только те начала, которые в таблице были отмечены восклицательными знаками: 1) ААБАББ, 2) ААББАБ, 3) АБААББ, 4) АБАББА и 5) АББАБА. Начнем с третьего случая: АБААББ. Знак '' указывает место для разбиения во всех ситуациях, кроме той, когда после этого начала идут одни только буквы Б. (Это очень важное соображение, и потому я прошу задержаться взглядом на этом месте и хорошо все обдумать.) Поскольку слово АБААББ...ББ можно разбить на 3 палиндрома, что прекрасно согласуется с неравенством (3), третий случай разобран. Аналогично, в пятом случае: АББАБА. Знак '' указывает место для разбиения во всех ситуациях, кроме той, когда после этого начала идут только буквы А. Слово АББАБА...АА можно разбить на 3 палиндрома, и это согласуется с неравенством (3). В четвертом случае припишем к началу АБАББА всевозможными способами шестибуквенные слова: АБА+ББ+ААААААА А+БАБ+БААААААБ А+БАБ+БАААААБ+А ................ АБА+ББ+АБББББА А+Б+АББА+ББББББ

Многоточия стоят потому, что в журнале никак нельзя привести все слова, хотя для доказательства я перебирал все подряд! Аналогично рассматриваем второй случай: А+АББА+Б+АААААА А+АББА+БАААААБ АА+ББ+АБААААБА ................ АА+ББ+АББББББА А+АББА+БББББББ Осталось рассмотреть первый случай: АА+БАБ+Б+АААААА АА+БАБ+БАААААБ АА+БАБ+БААААБ+А А+АБА+ББААААББ АА+Б+АББА+ААБАА АА+БАБ+БАААБАБ АА+БАБ+БАААББА ................. АА+Б+АБББББББА АА+БАБ+БББББББ При этом обнаруживается, что все слова поддаются разбиению, кроме двух: ААБАБББАААБА и ААБАБББААБАБ. Если приписать к первому из них букву А, то получаем АА+Б+АБББА+ААБАА. Если же приписать букву Б, то получим слово ААБАБББАААБАБ, с которым надо разбираться всерьез: АА+БАБ+ББ+АААБАБААА+АА АА+БАБ+ББ+АААБАБААААБ ........................ АА+БАБ+Б+БАААБ+АБББББА АА+БАБ+Б+БАААБАББББББ Мы победили слово ААБАБББАААБА! Осталось (непобедимое!) слово ААБАБББААБАБ. Справиться с ним мешает периодически продолжаемое слово ААБАБББААБАББААБАББААБАББААБАБ... Как с ним быть не знаю. Но если удастся разобраться с этим, останется выписать для каждого натурального n слово длиной n, которое нельзя разбить менее чем на указанное в теореме 2 число палиндромов и доказательство будет закончено! К сожалению, я не представляб, как завершить это доказательство без крайне утомительного перебора.
Упражнения 12. Придумайте слово из букв А и Б, которое нельзя разбить менее чем на 3 палиндрома, но которое после приписывания к нему справа или слева любой из букв А и Б можно разбить на два палиндрома. 13. Для каждого n = 1, 2, 3, ..., 21 укажите слово длиной n из букв А и Б, которое нельзя разбить менее чем на f(n) палиндромов.

Примечание. Познакомившись с рукописью этой статьи, И.Акулич чистосердечно раскаялся в своих заблуждениях и поклялся в дальнейшем и близко не подходить к компьютерам. Он признал удивительную интуицию учителя физики В. Боева, который, едва ознакомившись с третьей задачей, сразу заявил, хотя и бездоказательно: 'Предел равен трем'. В заключение неисправимый грешник добавил: 'Представляете, чего мог бы достичь лорд Рэлей, если бы у него был 'Пентиум'?!'

Послесловие
Понятно, что цель 'компьютеризации' школьного образования поручить компьютеру решение скучных и трудоемких задач, сохраняя время для более важных дел. При этом открывается путь 'изучать (науку), обучая (компью-