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

[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

[signamax.livejournal.com]

пожалуйста, прячте по pjnz ,хотя бы часть

[avva.livejournal.com]

По чему прятать??

Re:

[signamax.livejournal.com]

длинный

Re:

[avva.livejournal.com]

Не "почему", а "по чему". Что такое "прятать по pjnz"? Я такого не знаю.

А во-вторых, нет, не слишком длинный.

Re:

[signamax.livejournal.com]

что-то не так перекодировалось
я имел ввиду -

много ваших friends - не математики и не увлекающиеся мат задачками.
если спрятать - откроют те, кому интересно
зы
это, ессно, просто комент - ни к чему не обязывает. просто для удобства

[leovas.livejournal.com]

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

[avva.livejournal.com]

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

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

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

[khatul.livejournal.com]

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

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

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

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

[avva.livejournal.com]

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

Excuse my french, но...

[dizel.livejournal.com]

Почему строка 12221111111 является хорошей?

Берем строку x3...x6 (то-есть, 2211)

Берем строку x1...x2 (то-есть 12)

По-моему, 2-я строка явно является под-последовательностью первой (если 121 под-последовательность 1221 )

Стало быть, исходная строка плохая.

Я тоже решил эту задачу перебором, но у меня максисальная длина строкм - 7

Где ошибка?

Re: Excuse my french, но...

[avva.livejournal.com]

Нет, "подпоследовательность" означает наличие тех же символов, в том же порядке, но необязательно подряд.

"121" последовательность "1221", потому что можно выделить 121 внутри 1221 по порядку, вот так: 1221.

А 12 - не подпоследовательность 2211, т.к. в "2211" нет сначала единицы, а потом двойки (пусть даже не подряд).

Re: Excuse my french, но...

[avva.livejournal.com]

Погоди секунду. Дима, это ты?
А рассказать вообще, что ты в ЖЖ? :(

Re: Excuse my french, но...

[dizel.livejournal.com]

Здравствуй, Толик,
Да, Дима - это я :)

Но, пожалуйста, не обижайся. Я не совсем в ЖЖ, поскольку "чукча не писатель",
а чукча. То есть, сам ничего не пишу, только других читаю.

Давно я тебя не видел...Ты бываешь в Хайфе?

Re: Excuse my french, но...

[dizel.livejournal.com]

Будешь в Хайфе - обязательно позвони (055-581001) и заходи

Будем очень рады тебя (вас) видеть

Re: Excuse my french, но...

[avva.livejournal.com]

Обязательно.
Я давно хотел тебе позвонить, но не было твоего телефона.
Сотри этот коммент, если не хочешь оставлять его в публичном доступе, у меня в почте сохранился.