задача математическая, часть 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, следовательно наше первоначальное предположение о существовании "удобных" рядов неверно, что и требовалось доказать.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
Re: Как симпатично!
Date: 2002-10-10 07:43 am (UTC)sub IsSubSeq
{
local $first = join('.*',@{shift @_});
local $second = join('',@{shift @_});
return 1 if $second =~ $first;
return 0;
}
Если n>10 (правда, мощности моего компа и на троечку не хватает), можно сделать такой трюк:
sub Pad
{
return "x".join('xx',@_)."x";
}
sub SubPad
{
return "x".join('x.*x',@_)."x";
}
sub IsSubSeq
{
local $first = &SubPad(@{shift @_});
local $second = &Pad(@{shift @_});
return 1 if $second =~ $first;
return 0;
}
И хоть мульон символов в алфавите - все едино.
Дальше - как нам узнать, "хороша" ли строка? (Внимание - эта функция НЕ будет использована, я ее привожу только для объяснения образа мышления):
sub IsGood
{
local $Seq = shift @_;
foreach $i (0..((scalar @$Seq)/2 - 2))
{
local @inner = @$Seq[$i..(2*$i + 1)];
foreach $j (($i+1)..((scalar @$Seq)/2 - 1))
{
local @outer = @$Seq[$j..(2*$j + 1)];
return 0 if &IsSubSeq(\@inner,\@outer);
}
}
return 1;
}
Но нам-то надо не выяснить, какая строка хорошая. Нам надо ПОСТРОИТЬ хорошую строку максимального размера. Поэтому мы будем ДОСТРАИВАТЬ строку, удлиняя ее на ДВА новых элемента, и проверять только, ОСТАЁТСЯ ли она хорошей, т.е. не включена ли одна из последовательностей в НОВУЮ подпоследовательность. Это делается так:
sub IsStillGood
{
local $Seq = shift @_;
local $j = (scalar @$Seq)/2 - 1;
local @outer = @$Seq[$j..(2*$j + 1)];
foreach $i (0..((scalar @$Seq)/2 - 2))
{
local @inner = @$Seq[$i..(2*$i + 1)];
return 0 if &IsSubSeq(\@inner,\@outer);
}
return 1;
}
Теперь мы можем спокойно допустить, что ПЕРВЫЙ элемент строки - 0 (ясно). Второй может быть любым, и каждый раз мы попробуем достроить строку до максимальной.
sub FindMax
{
local $n = shift @_;
local $MaxLength = 2;
local @sequence = (0); # FIRST element can be preset as 0 - automorphism!
foreach $second (0..($n-1)) # SECOND element
{
push (@sequence,$second); # NOW we start!
&MaxCont;
pop @sequence;
}
return $MaxLength;
}
Здесь @sequence и $MaxLength передаются через область определения в функцию MaxCont, которая попытается продолжить последовательность рекурсивно, следующим макаром:
sub MaxCont
{
foreach $odd (0..($n-1))
{
push (@sequence,$odd);
foreach $even (0..($n-1))
{
push (@sequence,$even);
if (&IsStillGood(\@sequence))
{
if ((scalar @sequence) > $MaxLength)
{
$MaxLength = scalar @sequence;
}
&MaxCont;
}
pop @sequence;
}
pop @sequence;
}
}
Разумеется, тут стОит порассыпать разные print-ы, а то компутер молчать будет часами - уж слишком это сложно: проверять вложенность подпоследовательности длиной 15 в подпоследовательность длиной 30...
И, наконец, "мэйн" может выглядеть так:
print "Enter n: ";
$n = <>;
chomp $n;
print "\n\nA($n) = ",1+&FindMax($n),"\n";
Почему "1 плюс"? Потому что ясно, что мы можем удлинить нашу ЧЁТНУЮ последовательность на один элемент без вреда для "хорошести".
* * *
...Так чему же равно А(3)? Пока не знаю, потому что два компа (виндовый и линукс), которые я запустил под это, еще пашут. Застряли оба после 74, так что А(3) явно не меньше 75.
Хорошая последовательность размером 75 выглядит так:
0,0,1,1,0,1,2,2,2,2,
0,2,2,2,2,2,2,2,1,2,
2,2,1,1,1,1,1,1,1,1,
1,1,1,1,1,0,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,1,
2,2,0,1, кто угодно.
С уважением.
---
PS: оффтопик - загляни вот сюда: The Catherine Jones Memoirs. К тебе имеет отношение... :)
Re: Как симпатично!
Date: 2002-10-10 07:47 am (UTC)no subject
Date: 2002-10-11 12:02 pm (UTC)Решение: вместо цикла в FindMax делаем только проверку на 00 и 01 (второй элемент, если есть, всегда 1), а вместо цикла в MaxCont делаем так: в FindMax заводим еще список @alphabet, и дополняем его новым элементом только тогда, когда нужно, и только тогда, когда scalar @alphabet < $n . Еще для полного благолепия надо ВЫТАСКИВАТЬ из @alphabet элементы там, где в результате серии pop @sequence -ов они исчезают вообще из последовательности. Тогда сократится время поиска - причем не как-нибудь, а в (n!/2) раз по сравнению с кодом, к-рый я привел. Вона как. (Для многострадальной тройки - соответственно, еще в 3 раза сокращает вычисления.
______
Опять оффтопик: ты было собрался недельные главы комментировать... и как? :)
Я-то свои продолжаю выдавать там, где обычно: http://kor.mk.ru/yeshiva
Re:
Date: 2002-10-11 12:04 pm (UTC)Недельные главы: всё ещё очень хочу, просто рутина заела. Собираюсь к следующим выходным начать.
Lower bound
Date: 2002-10-12 11:37 pm (UTC)Вот она:
0,0,1,1,0,1,2,2,2,2,
0,2,2,2,2,2,2,2,1,2,
2,2,1,1,1,1,1,1,1,1,
1,1,1,1,1,0,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,1,
2,2,1,1,1,0,2,2, что угодно.
Интуиция, впрочем, говорит мне, что настоящее значение намного больше. (Наверное, это даже доказуемо на бумаге).
А комментарий - интересно было бы твой комментарий как раз к "Берешит" и "Ноах" увидеть.