Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

задача математическая, часть 3-я

Решение задачи, предложенной вчера.

Итак, пусть у нас есть алфавит из k символов; мы хотим доказать, что существует максимальная длина хорошей строки над этим алфавитом.

Предположим обратное: нет такой максимальной длины, то есть существуют сколь угодно длинные хорошие строки. Иными словами (ввиду конечности алфавита это одно и то же), существует бесконечно много хороших строк. Покажем вначале, что из этого следует существование хорошей строки бесконечной длины; т.е. строки x1x2...xn... бесконечной длины, такой, что в ней ни одна под-строка вида xi...x2*i не является под-последовательностью другой под-строки такого вида.

Как мы это покажем? Мы построим эту строку бесконечной длины по индукции следующим образом.

Начнём с пустой строки. Выберем такой символ x1 из нашего алфавита, что существует бесконечно много хороших строк, начинающихся с x1. Такой символ x1 обязан существовать, т.к. если бы его не было и для всех символов x из алфавита существовало бы только конечное кол-во хороших строк, начинающихся с x, то и вообще всего хороших строк было бы конечное кол-во (заметим, что в этом месте мы используем тот факт, что наш алфавит конечного размера), а это противоречит нашему первоначальному допущению. Поэтому такой символ x1 имеется; если есть несколько, отвечающих этому условию, выберем любой из них.

Далее, выберем такой символ x2, что существует бесконечное кол-во хороших строк, начинающихся с x1x2; опять-таки мы можем это сделать, т.к. в противном случае, суммируя кол-во хороших строк, начинающихся с x1x для всех x в алфавите, мы получили бы конечное кол-во хороших строк, начинающихся с x1, что противоречит выбору x1.

Далее, выбираем x3 так, что существует бесконечное кол-во хороших строк, начинающихся с x1x2x3... и так далее по индукции. В общем случае выбираем xn так, что существует бесконечное кол-во хороших строк, начинающихся с x1x2...xn-1xn.

Таким образом мы получаем строку бесконечной длины x1x2...xn... . Более того, это - хорошая строка. Действительно, если есть какие-то под-строки вида xi...x2*i и xj...x2*j, то выберем какой-то n больше, чем 2*i и 2*j; тогда согласно построению, есть бесконечно много хороших строк, начинающихся с x1x2...xn, значит, есть хотя бы одна; и из этого следует, что внутри этой строки xi...x2*i не является под-последовательностью xj...x2*j; значит, и в нашей бесконечной строке это так.

Итак, у нас есть бесконечная хорошая строка. Осталось доказать, что это невозможно, и мы получим желаемое противоречие. Для этого, однако, необходимо от рассмотрения последовательностей символов перейти к рассмотрению последовательностей строк символов.

Расставим символы из нашей строки в виде следующей бесконечной последовательности:

x1x2
x2...x4
x3...x6
x4...x8
x5...x10
...
xn...x2*n
...

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

Лемма: не существует бесконечной последовательности строк y1,y2,... над алфавитом из k символов, такой, что в ней для любых i<j строка yi не является под-последовательностью строки yj.

Доказательство леммы: Назовём свойство, которое отрицает лемма, "удобностью" последовательности: последовательность строк "удобна", если ни одна строка в ней не является под-последовательностью более поздней строки.

Предположим обратное тому, что хотим доказать: предположим, что существует хотя бы одна бесконечная "удобная" последовательность строк. Тогда выберем из всех таких последовательностей какую-нибудь одну с минимальной возможной длиной первой строки. Пусть первая строка в ней будет какая-то y1. Теперь из всех возможных "удобных" последовательностей, начинающихся с y1 (а есть хотя бы одна такая), выберем одну с минимальной возможной длиной второй строки, и пусть эта вторая строка будет y2. Затем... и так далее по индукции мы строим последовательность y1,y1,...yn... , которая минимальна в том смысле, что каждый yi был выбран в качестве элемента минимальной длины из всех, которые могут продолжить, не нарушая "удобства", уже выбранные y1...yi-1.

Легко видеть, что полученная таким образом "минимальная" последовательность y1,y2,...yn... в свою очередь "удобна": ни одна yi не является под-последовательностью yj при i<j, т.к. существуют "удобные" последовательности, начинающиеся с y1...yj (что напрямую следует из выбора yj во время построения).

Далее, ясно из определения, что любая под-последовательность "удобной" последовательности в свою очередь "удобна". Возьмём нашу последовательность y1,y2... и найдём в ней бесконечную под-последовательность строк, начинающихся на один и тот же символ. Это всегда возможно, т.к. не может быть, чтобы из всего бесконечного кол-ва строк последовательности на каждый из k символов начиналось только конечное кол-во строк. Пусть тот одинаковый символ, с которого они все начинаются, будет какой-то x, а сама бесконечная под-последовательность пусть будет yi_1,yi_2,...,yi_n,... Она расположена "внутри" нашей минимальной последовательности, начиная с какого-то индекса i_1, и вовсе необязательно "подряд".

Эта под-последовательность в свою очередь "удобна". Каждый yi_n можно записать в виде xy'i_n, т.е. начального символа x и остатка y' . Если мы теперь отбросим начальные символы сразу у всех членов под-последовательности, то получим
y'i_1,y'i_2,...,y'i_n,... ,
и эта последовательность тоже будет "удобной" (действительно, если бы в ней какая-то строка была под-последовательностью более поздней строки, то при восстановлении начальных x-ов это свойство сохранилось бы).

Теперь посмотрим на ряд
y1,y2,...,yi_1-1,y'i_1,y'i_2,.....

Иными словами, сначала мы ставим в него все строки из нашей "минимальной" последовательности вплоть до первой строки нашей под-последовательности, в которой все строки начинаются с одного символа; а потом мы продолжаем вставлять все члены этой под-последовательности, только уже с удалённым первым символом x, и так до бесконечности (при этом все yn, которые были в "минимальной" последовательности между членами под-последовательности, не попадая в неё, мы просто забываем).

Этот ряд, в свою очередь, "удобен". Как это доказать? Начиная с члена y'i_1, он полностью повторяет нашу "укороченную" под-последовательность, к-я, как мы показали, удобна. Значит, надо показать только, что ни один из членов рядa y1...yi_1-1 не является под-последовательностью более позднего; но если бы это было так, если бы какая-то yi была под-последовательностью какой-то y', это свойство сохранилось бы и при восстановлении удалённого первого x в такой строке y', и тогда "неудобной" была бы и первоначальная "минимальная" последовательность -- противоречие.

Итак, этот ряд "удобен". Но его член y'i_1 на единицу меньше по длине, чем yi_1 (т.к. в нём удалён первый символ x); в то же время мы выбрали yi_1 так, чтобы он был минимален по длине из всех возможных продолжений y1...yi_1-1, приводящих к "удобным" рядам. Мы получаем противоречие минимальности длины yi_1, следовательно наше первоначальное предположение о существовании "удобных" рядов неверно, что и требовалось доказать.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 7 comments