задача математическая, часть 3-я
Oct. 10th, 2002 01:12 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaРешение задачи, предложенной вчера.
Итак, пусть у нас есть алфавит из 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, следовательно наше первоначальное предположение о существовании "удобных" рядов неверно, что и требовалось доказать.
Итак, пусть у нас есть алфавит из 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, следовательно наше первоначальное предположение о существовании "удобных" рядов неверно, что и требовалось доказать.
