Один блогер-художник провёл конкурс в своём инстаграме и выбрал 35 победителей. Каждому из них он пообещал раскрашенный дизайнерский куб с уникальной окраской. Всего у художника 6 цветов, смешивать цвета он не любит и каждую грань он окрашивает в свой цвет.
Сможет ли блогер сдержать обещание и сделать 35 уникальных раскрасок кубиков? Помните, что если два кубика можно повернуть так, чтобы у них совпали по цветам все грани, это считается одинаковой окраской.
Сначала посчитаем, сколько вообще вариантов раскраски кубика можно сделать даже с повторениями. Для этого представим, что мы взяли кубик и он никак не вращается. Тогда получается так:
- Переднюю грань мы можем раскрасить в 6 разных цветов.
- Заднюю грань — в 5 цветов (потому что один цвет уже ушёл на переднюю грань).
- Верхнюю — в 4 цвета.
- Нижнюю — в 3 цвета.
- Левую — в 2 цвета.
- И на правую грань у нас останется какой-то один цвет.
Чтобы найти общее количество таких вариантов раскрасок, нужно перемножить эти числа: 1 × 2 × 3 × 4 × 5 × 6 = 720. Это максимальное количество всех вариантов покраски. Среди них обязательно будут неуникальные варианты, когда мы, например, развернём кубик и получим точно такой окрас, как и в другом случае.
Теперь посчитаем, сколько различных положений на старте может принимать куб. Благодаря этому мы узнаем количество повторов, которые получатся при окраске.
Когда мы берём куб в руки лицом к себе, мы можем это сделать шестью разными способами, потому что у куба 6 граней. Ещё мы можем 4 раза вращать его по часовой стрелке, глядя на ту же лицевую сторону. Получается, у нас есть 24 варианта, чтобы зафиксировать куб в одной позиции на старте. Это и есть количество повторов при окраске, потому что мы можем повернуть куб так, как нам нужно, чтобы найти дубль.
В итоге у нас есть 720 вариантов окраски и 24 положения на старте. Теперь мы можем узнать количество уникальных окрасов, разделив одно на другое: 720 / 24 = 30.
Получается, что блогер-художник сможет отправить уникальные кубики только 30 победителям, а 5 остальных получат уже неуникальную раскраску. А всё потому, что блогер плохо знал математику и не дружил с алгоритмами.
А зачем мне это?
Умение сокращать варианты и находить минимально достаточные действия — важное качество для программиста. Благодаря ему у нас появляются короткие оптимальные алгоритмы, а не раздутые на сотни строк кода, которые постоянно проверяют одно и то же и зря тратят машинное время.
