Пусть а_1 <a_2 <... <a_k -- алфавит племени Мумба, а b_1<b_2<...<b_m -- алфавит племени Юмба (запись "х<y" означает что буква "х" стоит раньше чем "у"). Эти алфавиты (обозначим как А и В) не имеют ни одной общей буквы. Оба племени решили соединиться и создать новый язык. Словом племени Мумба-Юмба будет считаться последовательность c_1c_2c_3...c_n, c_i∈A ⋃ B, 1<=i<=n, которая удовлетворяет такие условия: а) если для i<j c_j∈A и c_iA, то c_i<c_j или c_i=c_j б) если для i<j c_j∈В и c_i∈В, то c_i<c_j или c_i=c_j в) с_і не= с_і+1, для всех і, 1<=i<=n-1 г)с_і не= с_і+2, для всех і, 1<=i<=n-2 Какую максимальную длину могут иметь слова нового языка?

задан 18 Окт '13 18:18

изменен 19 Окт '13 20:09

Исправьте, пожалуйста, текст условия. Там встречается много символов, которые не читаются. Вместо них наличествуют пустые "квадратики".

(18 Окт '13 20:56) falcao

Текст по-прежнему не исправлен до конца.

(18 Окт '13 23:43) falcao

Теперь всё видно? Если нет, то где именно?

(19 Окт '13 23:06) vovax700

Да, теперь условие я понял! Постараюсь вскоре написать идею решения -- надо только ещё раз проверить все рассуждения.

(19 Окт '13 23:26) falcao
10|600 символов нужно символов осталось
2

Пусть $%f(k,m)$% -- наибольшая длина слова. Сначала рассмотрим случай, когда (хотя бы) одно из чисел $%k,m$% равно единице. Ввиду симметрии, можно считать, что $%k=1$%. Тогда буквы алфавита $%B$% не могут повторяться, а буква $%a_1$% может повторяться только через две различные буквы алфавита $%B$%, то есть таких повторений можно создать не более $%\lfloor\frac{m}2\rfloor$%. Вместе с общим количеством букв алфавитов это даёт ещё $%m+1$% букв слова, то есть $%f(1,m)=m+1+\lfloor\frac{m}2\rfloor$%. Пример слова "рекордной" длины таков: $%a_1b_1b_2a_1b_3b_4a_1\ldots b_{2t-1}b_{2t}a_1$% при $%m=2t$%, и такое же слово с дополнительной буквой $%b_{2t+1}$% на конце при $%m=2t+1$%. Для $%f(k,1)$% ответ аналогичный.

Пусть далее $%k > 1$%, $%m > 1$%. Пусть оба числа чётны: $%k=2s$%, $%m=2t$% (здесь и далее $%s\ge1$%, $%t\ge1$%). Тогда слово $$w=a_1b_1b_2a_1\ldots b_{2t-1}b_{2t}a_1a_2b_{2t}\ldots a_{2s-1}a_{2s}b_{2t}$$ является допустимым, откуда следует неравенство $%f(2s,2t)\ge3s+3t$%. Далее, пусть одно число чётно, а другое нечётно. Без ограничения общности положим $%k=2s$%, $%m=2t+1$%. Тогда в качестве допустимого можно рассмотреть слово $%wb_{2t+1}a_{2s}$%, откуда $%f(2s,2t+1)\ge3s+3t+2$%. Наконец, пусть оба числа нечётны: $%k=2s+1$%, $%m=2t+1$%. Тогда предыдущее слово можно удлинить ещё на две буквы, получая слово $%wb_{2t+1}a_{2s}a_{2s+1}b_{2t+1}$%. Из этого вытекает неравенство $%f(2s+1,2t+1)\ge3s+3t+4$%. Все полученные неравенства (для случая $%k,m > 1$%) можно записать в едином виде $%f(k,m)\ge k+m+\lfloor\frac{k+1}2\rfloor+\lfloor\frac{m+1}2\rfloor$%.

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

ссылка

отвечен 20 Окт '13 0:22

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×790

задан
18 Окт '13 18:18

показан
362 раза

обновлен
20 Окт '13 0:22

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru