|
|
 |
Условие
Имеется 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начала к цифрам, стоящим на позициях m, m + 1, ..., m + 9, а потом к цифрам на позициях m + 1, ..., m + 10, то в результате мы получим циклическую перестановку цифр на позициях m, m + 5 и m + 10. Таким образом, мы можем сделать циклическую перестановку цифр на любых трёх соседних позициях в любой из последовательностей αr. Но среди любых трёх цифр, каждая из которых равна 1 или 2, есть хотя бы две одинаковых. Значит, мы можем сделать любую перестановку соседних трёх цифр в последовательностях αr – она всегда эквивалента циклической перестановке. Из этого уже нетрудно заключить, что мы можем сделать любую перестановку цифр в каждой из последовательностей αr.
Ответ
215 чисел.Замечания
1. Неверно, что максимальное количество попарно непохожих 5k-значных чисел равно (k + 1)5: например, при k = 2 оно равно 16·33 ≠ 35.2. В Задачнике "Кванта" задача предлагалась в следующей формулировке:
Рассмотрим последовательности, состоящие из 3000 цифр 1 и 2. В такой последовательности разрешено поменять местами любые две соседние тройки цифр. Две последовательности называем эквивалентными, если одну из них можно перевести в другую несколькими такими перестановками. Сколько существует неэквивалентных последовательностей?
