Задача
Можно ли разбить все целые неотрицательные числа на 1968 непустых классов так, чтобы в каждом классе было хотя бы одно число и выполнялось бы следующее условие: если число m получается из числа n вычёркиванием двух рядом стоящих цифр или одинаковых групп цифр, то и m, и n принадлежат одному классу (например, числа 7, 9339337, 93223393447, 932239447 принадлежат одному классу)?
Решение
Первый способ. Обозначим знаком ≈ принадлежность одному классу. MabN ≈ MbbabN ≈ MbaababN ≈ MbaN. Таким образом, числа, получающиеся перестановкой соседних цифр, принадлежат одному классу. Так как любую перестановку можно представить в виде последовательности перестановок соседних цифр, то любые два числа, запись которых отличается только перестановкой цифр, принадлежат одному классу. Следовательно, если цифра входит в запись не менее двух раз, то любые два её вхождения можно вычеркнуть, то есть информация о том, какие цифры входят в запись числа нечётное число раз, полностью определяет класс, к которому принадлежит число. Итак, число классов не превосходит 210 = 1024. Второй способ. Рассмотрим полугруппу последовательностей цифр с операцией конкатенации (приписывания) и нейтральным элементом Λ (пустым словом). После факторизации по описанному в условии отношению эквивалентности получается полугруппа с образующими 0, 1, ..., 9 и соотношениями вида X² = Λ для каждого X. В силу этого соотношения полученная полугруппа будет группой. Так как все группы индекса 2 коммутативны, то полученная группа коммутативна. Таким образом, получаем коммутативную группу индекса два с десятью образующими. Число элементов в ней равно 1024, то есть у описанного в условии отношения эквивалентности не более 1024 классов эквивалентности.
Ответ
Нельзя.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь