В двоичных последовательностях можно менять местами любые две рядом стоящие подпоследовательности длины $%10$%. Пара последовательностей эквивалентна, если одну из них можно перевести во вторую такими операциями.

Определить количество неэквивалентных последовательностей длины $%100$%.

задан 25 Ноя '19 23:05

10|600 символов нужно символов осталось
2

Получается $% 10$% блоков по $%10 $% элементов: $$(1, 11, ... , 91), \ ( 2, 12,..., 92),\ ..., \ (10, 20, ..., 100)$$ $%A_k $% - операция меняния местами $%(a_k\ -\ a_{k+9}) $% и $%(a_{k+10}\ -a_{k+19}) $%

Тогда после $% A_k\ , \ A_{k+1}$% элементы $% (a_k \rightarrow a_{k+20}\rightarrow a_{k+10} \rightarrow a_{k})$% циклически сдвинутся, а остальные останутся на своих местах.

Поэтому в рамках одного блока будет $% 11 $% неэквивалентных (число нулей), а всего неэквивалентных групп последовательностей $% 11^{10} $% ( $% 10 $% блоков)

ссылка

отвечен 26 Ноя '19 16:03

изменен 26 Ноя '19 16:52

@Sergic Primazon: в 3-й строке есть мелкая опечатка (в конце должно быть k+19 вместо k+9).

Вопрос собственно по решению такой: почему можно одновременно все блоки привести к "нормальной форме", то есть сделать каждый из них вида 0...01...1? Ведь когда мы "выправили" один блок, это может "испортить" другой?

(26 Ноя '19 16:43) falcao
1

@falcao так мы же другие блоки не изменяем , только циклический сдвиг внутри одного блока получается

(26 Ноя '19 16:50) Sergic Primazon

@Sergic Primazon: да, всё работает -- я не "расписал" композицию двух преобразований как следует, и не заметил, что там ровно один тройной цикл получается.

(26 Ноя '19 17:13) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,288

задан
25 Ноя '19 23:05

показан
185 раз

обновлен
26 Ноя '19 17:13

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

по почте:

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

по RSS:

Ответы

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

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