Как решать задачи на разбиение фигуры на сектора по цветам?

Question

[Sunter]

Круг разбит на 42 секторов каждый из которых покрашен в один из 6 цветов. Сколькими способами можно составить такую мозаику (с точностью до поворотов круга)?

Comments

[Alexandroppolus]

на всякий: если одну раскраску можно превратить в другую поворотом круга - это одна и та же раскраска?

[Everything_is_bad]

как насчет погуглить?

[Sunter]

Alexandroppolus, да

Answer 1

[Wataru]

Лемма бернсайда. Гуглите. Но суть в том, что надо подсчитать количество раскрасок, которые не меняются при повороте на какой-то угол. Для всех углов сложить и поделить на количество поворотов.

Поворот на 1<=i<=42 секторов создает gcd(i,42) циклов, каждый из которых должен быть окрашен целиком в один из 6 цветов. Т.е. получается 6^gcd(i,42) раскрасок, инвариантных для поаорота на i секторов.

Отсюда ответ к задаче: sum i=1..42 6^gcd(i,42)/42.

Comments

[Sunter]

Можете, пожалуйста, объяснить почему поворот секторов создает gcd(i,42) циклов

[Wataru]

Каждый сектор должен быть равен сектору +i. Если идти по секторам с шагом +i, то рано или подзно мы вернемся туда, откуда начали - это и есть цикл.

Его длина (в секторах) делится на i, потому что мы по i секторов скачем. И к тому же она делится на 42, ведь мы прошли сколько-то полных кругов, чтобы вернуться в начало. Итого, эта длина НОК(i, 42). Но это длина в секторах, считая пропущенные i-1. Всего цикл посетит НОК(i, 42)/i секторов. А, поскольку все циклы одинаковые, то их всего 42/длина-цикла-в-посещенных-секторах, т.е. 42*i/НОК(i,42). И это получится GCD(i, 42).