Скажем, что колода из 52 карт сложена правильно, если любая пара лежащих рядом карт совпадает по масти или по достоинству, то же верно для верхней и нижней карты, и наверху лежит туз пик. Докажите, что число способов сложить колоду правильно
а) делится на 12!;
б) делится на 13!.
Очевидно, правильному расположению карт в колоде соответствует кольцевой обход ладьей (которая может прыгать через клетки!) доски 4 × 13 (горизонтали соответствуют мастям, а вертикали — достоинствам), начинающийся и кончающийся в клетке, соответствующей тузу пик (будем считать, что это левый нижний угол). Такой обход удобно закодировать, занумеровав клетки от 1 до 52, где 1 стоит в левом нижнем углу, а любая пара соседних номеров (включая 1 и 52) стоит в одной строке или в одном столбце.
а) Совершив любую из (12! − 1) нетривиальных перестановок 12 правых вертикалей, мы из данного обхода получим новый (другая нумерация!). Таким образом, все обходы разбиваются на группы по 12! обходов.
б) Достаточно доказать, что это число делится на 13. Свернем доску в цилиндр, склеив вертикальные стороны. Любой из 12 возможных поворотов цилиндра переводит данный обход в другой, начинающийся уже не с «туза пик». Но поскольку он проходит через эту клетку, то его можно рассматривать как «правильный обход» (соответствующую нумерацию можно получить, сдвинув все номера на одно и то же число по модулю 52 так, чтобы в левом нижнем углу оказалась 1). Ниже мы покажем, что этот обход отличается от первоначального. Таким образом, все обходы разбиваются на группы по 13 обходов.
Восстановим пропущенный момент. Пусть при повороте некоторый обход переходит в себя. Рассмотрим любой горизонтальный ход (он должен быть). Повторив поворот 13 раз, видим, что из каждой клетки этой горизонтали мы выходили по горизонтали, то есть сменить эту масть нельзя. Противоречие.