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

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

Условие

Можно ли разбить все целые неотрицательные числа на 1968 непустых классов так, чтобы в каждом классе было хотя бы одно число и выполнялось бы следующее условие: если число m получается из числа n вычёркиванием двух рядом стоящих цифр или одинаковых групп цифр, то и m, и n принадлежат одному классу (например, числа 7, 9339337, 93223393447, 932239447 принадлежат одному классу)?


Решение

Первый способ. Обозначим знаком ≈ принадлежность одному классу.  MabNMbbabNMbaababNMbaN.  Таким образом, числа, получающиеся перестановкой соседних цифр, принадлежат одному классу. Так как любую перестановку можно представить в виде последовательности перестановок соседних цифр, то любые два числа, запись которых отличается только перестановкой цифр, принадлежат одному классу. Следовательно, если цифра входит в запись не менее двух раз, то любые два её вхождения можно вычеркнуть, то есть информация о том, какие цифры входят в запись числа нечётное число раз, полностью определяет класс, к которому принадлежит число. Итак, число классов не превосходит  210 = 1024.

Второй способ. Рассмотрим полугруппу последовательностей цифр с операцией конкатенации (приписывания) и нейтральным элементом Λ (пустым словом). После факторизации по описанному в условии отношению эквивалентности получается полугруппа с образующими 0, 1, ..., 9 и соотношениями вида   X² = Λ  для каждого X. В силу этого соотношения полученная полугруппа будет группой. Так как все группы индекса 2 коммутативны, то полученная группа коммутативна. Таким образом, получаем коммутативную группу индекса два с десятью образующими. Число элементов в ней равно 1024, то есть у описанного в условии отношения эквивалентности не более 1024 классов эквивалентности.


Ответ

Нельзя.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 31
Год 1968
вариант
1
Класс 10
Тур 1
задача
Номер 3

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

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