Винтик, Шпунтик и Кубик Рубика
Я давно подозревал, что между задачей про Винтика и Шпунтика и кубиком Рубика есть определенная связь. И вот только сейчас придумал простую аналогию. Представьте, что у нас есть грань размера 3x3 и нам надо покрасить 9 ячеек в три цвета. 3 - в красный, 3 - в желтый, и 3 - в зеленый. Сколько существует раскрасок при которых ни одна строка и ни один столбец не закрашены одним цветом?
Картинка ниже дает примеры возможных и невозможных раскрасок
У задачки есть три уровня сложности
Написать код, который считает число возможных раскрасок.
Посчитать то же самое число аналитически (то есть "на бумажке"🧐)
Очевидно, что задача обладает некоторым набором симметрий. Иными словами перестановка строк (эта группа изоморфна S3) переводит решение в решение. То же самое с перестановкой столбцов (тоже S3). Также "перекрашивание" (красные в желтые, желтые в зеленые и тп) дает еще одно S3. Ну и наконец транспонирование матрицы или поворот на 900 (2700) также переводит решение в решение. Вопрос "со звездочкой" - сколько существует орбит решений относительно действия этой группы?
Маленькая подсказка - можно воспользоваться теоремой Редфилда-Пойа. Но окончательного ответа я с ее помощью получить не смог...😒
