?

Log in

задачка (математическая) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка (математическая) [окт. 8, 2002|10:31 am]
Anatoly Vorobey
Вот не очень сложная математическая задачка примерно олимпиадного типа для тех, кому это интересно. Постараюсь описать её в как можно более элементарных терминах.

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

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

Рассмотрим все строки вида xi, xi+1, ... , x2*i внутри нашей последовательности (i двигается от единицы и выше; если 2*i > n, то строка заканчивается на n-ном месте). В приведенном выше примере такими будут: x1...x2 (то есть "22"); x2...x4 (то есть "221"); x3...x6 (то есть "2111"); x4...x8 (то есть "11122"); и, наконец, x5...x10 (то есть "112221") (ещё на самом деле x6...x10 итп., но они неинтересны, как будет ясно из нижеизложенного).

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

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

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

Comments:
[User Picture]From: signamax
2002-10-08 03:01 am
пожалуйста, прячте по pjnz ,хотя бы часть
(Ответить) (Thread)
[User Picture]From: avva
2002-10-08 03:03 am
По чему прятать??
(Ответить) (Parent) (Thread)
[User Picture]From: signamax
2002-10-08 03:20 am

Re:

длинный
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-10-08 03:23 am

Re:

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

А во-вторых, нет, не слишком длинный.
(Ответить) (Parent) (Thread)
[User Picture]From: signamax
2002-10-08 03:28 am

Re:

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

много ваших friends - не математики и не увлекающиеся мат задачками.
если спрятать - откроют те, кому интересно
зы
это, ессно, просто комент - ни к чему не обязывает. просто для удобства
(Ответить) (Parent) (Thread)
[User Picture]From: leovas
2002-10-08 04:07 am
Max. строка - 12221111111 (11 знаков). Доказательство - подбором (точнее, перебором дерева последовательностей), что несложно, но скучно.. Или есть красивое доказательство?
(Ответить) (Thread)
[User Picture]From: avva
2002-10-08 05:25 am

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

Док-во более красивое есть, но не дающее конкретную строку. Можно доказать, что есть максимальная длина для любого (конечного) алфавита, необязательно из двух букв. Я это сегодня запощу в виде продолжения этой темы (а ещё более интересное будет в третьей части).
(Ответить) (Parent) (Thread)
[User Picture]From: khatul
2002-10-08 09:30 am

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

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

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

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

(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-10-08 10:00 am

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

Есть общее доказательство того, что существует максимальная длина, не дающее собственно саму длину или максимальную строку. Довольно элегантное. См. мою последнюю запись.
(Ответить) (Parent) (Thread)
[User Picture]From: dizel
2002-10-08 02:44 pm

Excuse my french, но...

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

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

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

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

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

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

Где ошибка?
(Ответить) (Thread)
[User Picture]From: avva
2002-10-08 02:47 pm

Re: Excuse my french, но...

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

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

А 12 - не подпоследовательность 2211, т.к. в "2211" нет сначала единицы, а потом двойки (пусть даже не подряд).
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-10-08 02:48 pm

Re: Excuse my french, но...

Погоди секунду. Дима, это ты?
А рассказать вообще, что ты в ЖЖ? :(
(Ответить) (Parent) (Thread)
[User Picture]From: dizel
2002-10-08 03:24 pm

Re: Excuse my french, но...

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

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

Давно я тебя не видел...Ты бываешь в Хайфе?
(Ответить) (Parent) (Thread)
[User Picture]From: dizel
2002-10-08 03:42 pm

Re: Excuse my french, но...

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

Будем очень рады тебя (вас) видеть
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-10-08 04:13 pm

Re: Excuse my french, но...

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