Таблицы Брадиса

Это можно сделать 37 способами.

Это можно сделать 37 способами.

Элементы математики в задачах - Г. А. Мерзон

Решение. а) Зафиксируем сначала колесо и раскрасим его. Это можно сделать 37 способами. Теперь посчитаем, сколько раз мы учли каж­дую раскраску вращающегося колеса. Любая раскраска, которая не

96                                     Комбинаторика 1

переходит в себя ни при каком вращении колеса, посчитана 7 раз. Поскольку число 7 —простое, в себя при вращении колеса переходят только одноцветные раскраски. Итак, все раскраски, кроме трех, по­считаны по 7 раз, а эти три — по одному разу. Отсюда легко находим

37 — 3 . 0

число раскрасок —-—1-3.

б)  Будем действовать аналогично предыдущему пункту. При этом возникнет новая трудность: не только одноцветные раскраски пере­ходят в себя при повороте. Посчитаем сначала (кроме одноцветных), сколько раскрасок переходят в себя при хоть каком-нибудь повороте. При повороте на 1, 3, 7 и 9 в себя переходят только одноцветные рас­краски. При повороте на 2, 4, 6 и 8 в себя переходят еще и раскраски, в которых цвета чередуются (у зафиксированной карусели есть две такие неодноцветные раскраски). При повороте на 5 в себя переходят симметричные раскраски (кроме одноцветных, их 25 — 2 = 30). Сле­довательно, по 10 раз мы посчитали 210 — 2 — 2 — 30 = 990 раскрасок. Итак, общее число раскрасок вращающегося колеса равно ^ +

30 2

+ у +=+2 = 99 + 6 + 1+2 = 108.

Ш Далеким обобщением этого метода подсчета является лемма Берн­сайда из листочка «Теория групп 2».

Задача 14. Кто-то режет правильный: а) шестиугольник; б*) семи­угольник; в*) восьмиугольник на треугольники, проводя разрезы по непересекающимся диагоналям. Сколько разных наборов треуголь­ников может получиться?

Решение. а) Разрезания шестиугольника мы можем разбить на два класса: те, в которых есть разрез по главной диагонали, и те, в кото­рых его нет. Заметим, что если шестиугольник разрезан по главной диагонали, то как бы мы ни разрезали получившиеся четырехуголь­ники (трапеции), мы будем получать один и тот же набор треуголь­ников.