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

УМ

ХОРОШО,

А

ПЯТЬ



ЛУЧШЕ

15

зано с n следующим соотношением:

1 2 4 6 K 2m = . n 3 5 7 K 2m + 1

b

g

Тогда общее число накопленных чисел y m = m + 1 xm = m + 1. Но что из себя представляет y m ? Это количество чисел, которое получилось, если, стартовав от n чисел, мы последовательно вставили в них каждое n-е, затем каждое (n 1)-е, каждое (n 2)-е, ..., каждое 2-е число. Что получится? Конечно, an ! Итак, an = = y m = m + 1. Ну, а для нахождения искомого коэффициента k мы должны найти предел an n2 при n . Ясно, что при n будет и m , поэтому 2 a 1 k = lim n = lim m + 1 = 2 n n n n

b

g

b

= lim m + 1
m

b

gFGH

gFGH IJK

2 4 6 K 2m 3 5 7 K 2m +

b

I 1g J K

2

.

Наверняка значение этого предела можно найти в каком-нибудь толстом справочнике. Но мы можем вычислить его и сами, используя знаменитую формулу Стирлинга: m 2 m . Великое ее достоm! m e инство в том, что она асимптотическая: выполняется тем точнее, чем больше m, и, следовательно, как нельзя лучше подходит для вычисления пределов. Правда, числитель и знаменатель нашей дроби не являются факториалами, но могут быть очевидным образом к ним приведены. В числителе, например, достаточно каждый сомножитель поделить на 2, а в знаменателе между сомножителями вставить... сомножители числителя! И вот что из этого получается:

ния имеют немало огрехов, но искоренять их как-то не поднимается рука: не навредить бы! Куда приятней почивать на лаврах, но некогда, потому что нас ждет третья задача. Ее предысторией можно считать другую задачу, предложенную в 1995 году на конкурсе 'Математика 6 8': Из букв А и Б составлено 1995буквенное слово. Докажите, что его можно разбить менее чем на 800 более коротких слов, каждое из которых является палиндромом. (Палиндромом называется слово, которое не меняется при перестановке его букв в обратном порядке). Решение ее таково. Рассмотрим все возможные пятибуквенные слова, состоящие из букв А и Б, и убедимся, что каждое такое слово можно разделить не более чем на два палиндрома. Поскольку буквы А и Б равноправны, то достаточно рассмотреть слова, начинающиеся с буквы А. Поэтому перебор оказывается совсем невелик всего 16 слов:
ААААА ААААБ АААБА АААББ ААБАА ААБАБ ААББА ААБББ АБААА АБААБ АБАБА АБАББ АББАА АББАБ АБББА АББББ = = = = = = = = = = = = = = = = ААААА АААА + Б АА + АБА ААА + ББ ААБАА АА + БАБ А + АББА АА + БББ АБА + АА А + БААБ АБАБА АБА + ББ АББА + А АББА + Б АБББА А + ББББ

bg

k=
=

=

m

Прямо в яблочко! Конечно, и здесь наши рассужде4

F b2 4 6 K 2mg I limbm + 1gG GH1 2 3 4 K 2m b2m + 1gJJK F e2 m!j I = limbm + 1gG GH b2mg! b2m + 1g JJK = F e2 bmeg 2mj I G J limbm + 1gG b2meg 4m b2m + 1gJJK GH mbm + 1g = = lim b2m + 1g
2 m m 2 2 m m m 2 2m m 2

2

=

2

= 4

.

Возьмем произвольное 1995-бук венное слово и разобьем его сначала на 5-буквенные их будет всего 1995 : 5 = 399. Каждое из этих 5-буквенных слов, в свою очередь, может быть составлено не более, чем из двух палиндромов. Поэтому произвольное 1995-буквенное слово можно составить не более, чем из 399 2= = 798 палиндромов, т. е. меньше чем из 800, что и требовалось доказать. У въедливого читателя наверняка возник естественный вопрос: чем руководствовался автор задачи, разбивая длинное слово именно на пятибуквенные куски? Неужели только тем, что 1995 делится на 5? Конечно, нет. Число 1995 поначалу вообще не фи-

гурировало. Прежде всего, автор хотел произвести наибольшее впечатление на решающих чтобы при одной и той же длине исходного слова число кусков-палиндромов оказалось наименьшим. Поэтому он предварительно рассмотрел самые короткие слова, выясняя, на какое число палиндромов можно их разбить. Например, однобуквенное слово само по себе палиндром. Такие слова из двух букв, как АА и ББ также палиндромы, но АБ и БА нет, их приходится разбивать на 2 палиндрома каждое. С трехбуквенными словами тоже возни немного любое из них может быть составлено не более, чем из двух палиндромов. Несколько больше работы с четырехбуквенными словами, но несложно выяснить, что и здесь всегда хватает двух палиндромов. Для пятибуквенных слов перебор сделан выше тоже два палиндрома! На этом пока притормозим, и чтобы разбираться далее с большей научностью, введем в обращение функцию f(n). Определим ее так. Рассмотрим все возможные n-буквенные слова, состоящие из А и Б, и разобьем каждое такое слово на наименьшее возможное число кусков-палиндромов. Из полученных наименьших значений выберем наибольшее. Это и будет f(n). Нетрудно сообразить, что вычислением f(n) для наименьших n мы как раз только что занимались, и выяснили, что f(1) = 1, f(2) = f(3) = f(4) = = f(5) = 2. А чему равно f(6)? Оказывается, это значение можно найти и без перебора. Прежде всего заметим, что f(n + 1) f(n) + 1 для любого n. Действительно, возьмем (n + 1)-буквенное слово и отделим от него одну крайнюю букву (безразлично первую или последнюю). Получится nбуквенное слово, которое (по определению функции f) можно разбить не более, чем на f(n) палиндромов. А так как отрезанная крайняя буква сама по себе палиндром, то наименьшее число палиндромов, на которые можно разбить (n + 1)-буквенное слово, не превышает f(n) + 1. Вычислим, наконец, f(6). Из неравенства f(n + 1) f(n) + 1 следует, что f(6) f(5) + 1 = 2 + 1 = 3. С другой стороны, можно указать 6-буквенное слово, которое нельзя разбить на 2 палиндрома: например, АБААББ. Поэтому f(6) 3. Таким образом, f(6) = 3. Можно также убедиться, что и f(7) = 3, но здесь без

*