На самом деле это известная (но не очень широко) лемма. Для тех, кому интересно слегка поломать мозги.
Есть конечное множество и бесконечная последовательность, составленная из элементов этого множества.
Верно ли, что для любого числа N в последовательности присутсвует подпоследовательность длины N, встречающаяся бесконечное число раз?
Заранее знающим ответ с доказательством — молчать.
Здравствуйте, Lexey, Вы писали:
L>На самом деле это известная (но не очень широко) лемма. Для тех, кому интересно слегка поломать мозги.
L>Есть конечное множество и бесконечная последовательность, составленная из элементов этого множества.
L>Верно ли, что для любого числа N в последовательности присутсвует подпоследовательность длины N, встречающаяся бесконечное число раз?
L>Заранее знающим ответ с доказательством — молчать.
От противного.
Берем всевозможные варианты подпоследовательностей (ПП) длины N.
Их конечное число.
Если количество вхождений каждой ПП_i конечно, значит для каждой из них существует индекс M_i, указывающий позицию последнего вхождения.
Отсюда получаем, что длина исходной последовательности не может превышать max M_i + N, что тоже есть конечное число.
--
Владимир.
Здравствуйте, _vovin, Вы писали:
L>>На самом деле это известная (но не очень широко) лемма. Для тех, кому интересно слегка поломать мозги.
L>>Есть конечное множество и бесконечная последовательность, составленная из элементов этого множества.
L>>Верно ли, что для любого числа N в последовательности присутсвует подпоследовательность длины N, встречающаяся бесконечное число раз?
L>>Заранее знающим ответ с доказательством — молчать.
V>От противного.
Логично.
V>Берем всевозможные варианты подпоследовательностей (ПП) длины N.
V>Их конечное число.
V>Если количество вхождений каждой ПП_i конечно, значит для каждой из них существует индекс M_i, указывающий позицию последнего вхождения.
V>Отсюда получаем, что длина исходной последовательности не может превышать max M_i + N, что тоже есть конечное число.
ОК. Есть еще как минимум одно немного другое решение, не оперирующее индексами вхождения.
Здравствуйте, _vovin, Вы писали:
V>Здравствуйте, Lexey, Вы писали:
L>>ОК. Есть еще как минимум одно немного другое решение, не оперирующее индексами вхождения.
V>Действительно, можно проще.
V>Каждому варианту подпоследовательности из N элементов нужно поставить в сответствие его порядковый номер K (их конечное число). Теперь просто разбиваем исходную последовательность на отрезки длины N и пишем напротив каждого из них его число К.
V>Далее уже очевидно...
А так:
Пусть К — такое число, что любая последовательность длины N встречается меньше К раз. Тогда результирующая последовательность не длиннее L = P^N * K, где Р — мощность алфавита. Если L -> inf (при P,N = const), то и К -> inf.
Собственно, это уже тавтология.
Евгений
