Олимпиадная задача Гуревича — максимальное множество непохожих 100-зна

  Ниже мы докажем, что два числа похожи тогда и только тогда, когда для каждого  r = 1, 2, 3, 4, 5  у них совпадает количество единиц на позициях вида

5k + r  (0 ≤ k ≤ 19).   Из этого следует, что класс похожих чисел однозначно определяется упорядоченной пятёркой  (x₁, ..., x₅),  где x_r – количество единиц на позициях вида  5k + r.  Эти числа могут принимать любые значения от 0 до 20. Следовательно, число таких пятёрок равно 21⁵.

  Докажем необходимость приведённого условия. Пусть α_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.