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

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

Условие

Скажем, что колода из 52 карт сложена правильно, если каждая пара лежащих рядом карт совпадает по масти или достоинству, то же верно для верхней и нижней карты, и наверху лежит туз пик. Докажите, что число способов сложить колоду правильно
  а) делится на 12!;
  б) делится на 13!.


Решение

  Очевидно, правильному расположению карт в колоде соответствует кольцевой обход ладьей доски 4×13 (горизонтали соответствуют мастям, а вертикали – достоинствам), начинающийся и кончающийся в клетке, соответствующей тузу пик (отметим её). Такой обход удобно закодировать, занумеровав клетки от 1 до 52, где 1 стоит в отмеченной клетке, а любая пара соседних номеров (включая 1 и 52) стоит в одной строке или в одном столбце.

  а) Совершив любую из  12! – 1  нетривиальных перестановок 12 правых вертикалей, мы из данного обхода получим новый (другая нумерация!). Таким образом, все обходы разбиваются на группы по 12! обходов.

  б) Достаточно доказать, что это число делится на 13. Свернём доску в цилиндр, склеив вертикальные стороны. Любой из 12 возможных поворотов цилиндра переводит данный обход в другой, начинающийся уже не с "туза пик". Но поскольку он проходит через эту клетку, то его можно рассматривать как "правильный обход" (соответствующую нумерацию можно получить, сдвинув все номера на одно и то же число по модулю 52 так, чтобы в левом нижнем углу оказалась единица). Ниже мы покажем, что этот обход отличается от первоначального. Таким образом, все обходы разбиваются на группы по 13 обходов.
  Восстановим пропущенный момент. Пусть при повороте некоторый обход переходит в себя. Рассмотрим любой горизонтальный ход (он должен быть). Повторив поворот 13 раз, видим, что из каждой клетки этой горизонтали мы выходили по горизонтали, то есть сменить эту масть нельзя. Противоречие.

Замечания

Баллы: 3 + 5.

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

олимпиада
Название Турнир городов
Турнир
Номер 28
Дата 2006/2007
вариант
Вариант осенний тур, основной вариант, 10-11 класс
задача
Номер 6

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

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