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 символов, очевидно, плохая.

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

Flat | Top-Level Comments Only

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

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

длинный

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Где ошибка?

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

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

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

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

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

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

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

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

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

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

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

no subject

no subject

Re:

Re:

Re:

no subject

no subject

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

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

Excuse my french, но...

Re: Excuse my french, но...

Re: Excuse my french, но...

Re: Excuse my french, но...

Re: Excuse my french, но...

Re: Excuse my french, но...