ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 79258
Темы:    [ Процессы и операции ]
[ Разложение в произведение транспозиций и циклов ]
[ Теория алгоритмов (прочее) ]
[ Правило произведения ]
Сложность: 5
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Имеется 100-значное число, состоящее из единиц и двоек. Разрешается в любых десяти последовательных цифрах поменять местами первые пять с пятью следующими. Два таких числа называются похожими, если одно из них получается из другого несколькими такими операциями. Какое наибольшее количество попарно непохожих чисел можно выбрать?


Решение

  Ниже мы докажем, что два числа похожи тогда и только тогда, когда для каждого  r = 1, 2, 3, 4, 5  у них совпадает количество единиц на позициях вида
5k + r  (0 ≤ k ≤ 19).   Из этого следует, что класс похожих чисел однозначно определяется упорядоченной пятёркой  (x1, ..., x5),  где xr – количество единиц на позициях вида  5k + r.  Эти числа могут принимать любые значения от 0 до 20. Следовательно, число таких пятёрок равно 215.
  Докажем необходимость приведённого условия. Пусть αr – последовательность цифр, расположенных на местах с номерами  5k + r.  Если мы применяем нашу операцию к последовательным 10 цифрам, то в каждой из последовательностей αr меняется местами пара соседних цифр. В частности, число единиц в этих последовательностях не меняется.
  Докажем достаточность условия. Пусть у двух чисел совпадают количества единиц в каждой из последовательностей αr. Докажем, что эти числа похожи. Для этого достаточно доказать, что с помощью нашей операции мы можем реализовать любую перестановку цифр исходного числа (именно цифр, а не позиций, в которых они стоят). Заметим, что применяя последовательно нашу операцию cначала к цифрам, стоящим на позициях   mm + 1,  ...,  m + 9,   а потом к цифрам на позициях   m + 1,  ...,  m + 10,   то в результате мы получим циклическую перестановку цифр на позициях mm + 5  и  m + 10.  Таким образом, мы можем сделать циклическую перестановку цифр на любых трёх соседних позициях в любой из последовательностей αr. Но среди любых трёх цифр, каждая из которых равна 1 или 2, есть хотя бы две одинаковых. Значит, мы можем сделать любую перестановку соседних трёх цифр в последовательностях αr – она всегда эквивалента циклической перестановке. Из этого уже нетрудно заключить, что мы можем сделать любую перестановку цифр в каждой из последовательностей αr.


Ответ

215 чисел.

Замечания

1. Неверно, что максимальное количество попарно непохожих 5k-значных чисел равно  (k + 1)5:  например, при  k = 2  оно равно  16·33 ≠ 35.
2. В Задачнике "Кванта" задача предлагалась в следующей формулировке:
  Рассмотрим последовательности, состоящие из 3000 цифр 1 и 2. В такой последовательности разрешено поменять местами любые две соседние тройки цифр. Две последовательности называем эквивалентными, если одну из них можно перевести в другую несколькими такими перестановками. Сколько существует неэквивалентных последовательностей?

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 36
Год 1973
вариант
Класс 10
Тур 2
задача
Номер 4
олимпиада
Название Московская математическая олимпиада
год
Номер 36
Год 1973
вариант
Класс 9
Тур 2
задача
Номер 1
журнал
Название "Квант"
год
Год 1973
выпуск
Номер 6
Задача
Номер М210

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .