задачка (математическая)

[avva]

Вот не очень сложная математическая задачка примерно олимпиадного типа для тех, кому это интересно. Постараюсь описать её в как можно более элементарных терминах.

Возьмём какой-нибудь алфавит из двух символов; для наглядности пусть это будет {1,2}, т.е. разрешённые символы - единица и двойка. Конкретный выбор символов роли не играет.

Рассмотрим какую-нибудь последовательность x₁, x₂, ... , x_n , где каждый член последовательности - символ из нашего алфавита. Например, n может быть 10,
а последовательность может быть 2221112221 . Вместо "последовательности" может оказаться удобным говорить просто о строках, построенных на данном алфавите - это одно и то же.

Рассмотрим все строки вида x_i, x_i+1, ... , x_2*i внутри нашей последовательности (i двигается от единицы и выше; если 2*i > n, то строка заканчивается на n-ном месте). В приведенном выше примере такими будут: x₁...x₂ (то есть "22"); x₂...x₄ (то есть "221"); x₃...x₆ (то есть "2111"); x₄...x₈ (то есть "11122"); и, наконец, x₅...x₁₀ (то есть "112221") (ещё на самом деле x₆...x₁₀ итп., но они неинтересны, как будет ясно из нижеизложенного).

Может случиться так, что какая-то из этих строк такого вида окажется под-последовательностью другой, более длинной строки такого вида. Под под-последовательностью здесь подразумевается то, что первая строка будет заключена "внутри" второй под-строки, но необязательно в идущих подряд местах. Например, "121" - подпоследовательность "1121", очевидно, но кроме того, "121" -- под-последовательность "1221", потому что члены "121" можно найти по порядку внутри "1221", хоть и не подряд.

Если для нашей строки x₁...x_n длиной n окажется, что какая-то из строк вида x_i, x_i+1, ... , x_2*i является под-последовательностью другой более длинной строки вида x_к, x_к+1, ... , x_2*к, то мы скажем, что строка x₁...x_n является плохой. Если же никакая строка такого вида не является под-последовательностью другой строки такого вида, то исходная строка x₁...x_n называется хорошей. Например, приведенная в качестве примера строка из 10 символов, очевидно, плохая.

Требуется: доказать, что существует максимальная длина хорошей строки. Найти хорошую строку максимальной длины.

Comments

[leovas.livejournal.com]

Max. строка - 12221111111 (11 знаков). Доказательство - подбором (точнее, перебором дерева последовательностей), что несложно, но скучно.. Или есть красивое доказательство?

[avva.livejournal.com]

Да, верно. Или зеркальная ей, естественно.

Док-во более красивое есть, но не дающее конкретную строку. Можно доказать, что есть максимальная длина для любого (конечного) алфавита, необязательно из двух букв. Я это сегодня запощу в виде продолжения этой темы (а ещё более интересное будет в третьей части).

Мы с приятелем...

[khatul.livejournal.com]

...решили эту задачу нынче за обедом. Тоже перебором дерева последовательностей - но, почему-то, скучным не показалось; философический смысл извлекли.

Но все время, пока решали, нам думалось: вот придет кто-то и скажет "а на самом деле это ВОТ ТАК решается" - без перебора (но не длиннее, чем с перебором!). А мы скажем "ааааа....".

Вот и интересно: как?

Re: Мы с приятелем...

[avva.livejournal.com]

Есть общее доказательство того, что существует максимальная длина, не дающее собственно саму длину или максимальную строку. Довольно элегантное. См. мою последнюю запись.