Задача про цветной кубик

Один блогер-художник про­вёл кон­курс в сво­ём инста­гра­ме и выбрал 35 побе­ди­те­лей. Каж­до­му из них он пообе­щал рас­кра­шен­ный дизай­нер­ский куб с уни­каль­ной окрас­кой. Все­го у худож­ни­ка 6 цве­тов, сме­ши­вать цве­та он не любит и каж­дую грань он окра­ши­ва­ет в свой цвет. 

Смо­жет ли бло­гер сдер­жать обе­ща­ние и сде­лать 35 уни­каль­ных рас­кра­сок куби­ков? Помни­те, что если два куби­ка мож­но повер­нуть так, что­бы у них сов­па­ли по цве­там все гра­ни, это счи­та­ет­ся оди­на­ко­вой окраской.

Решение

Сна­ча­ла посчи­та­ем, сколь­ко вооб­ще вари­ан­тов рас­крас­ки куби­ка мож­но сде­лать даже с повто­ре­ни­я­ми. Для это­го пред­ста­вим, что мы взя­ли кубик и он никак не вра­ща­ет­ся. Тогда полу­ча­ет­ся так:

  1. Перед­нюю грань мы можем рас­кра­сить в 6 раз­ных цветов.
  2. Зад­нюю грань — в 5 цве­тов (пото­му что один цвет уже ушёл на перед­нюю грань).
  3. Верх­нюю — в 4 цвета.
  4. Ниж­нюю — в 3 цвета.
  5. Левую — в 2 цвета.
  6. И на пра­вую грань у нас оста­нет­ся какой-то один цвет.

Что­бы най­ти общее коли­че­ство таких вари­ан­тов рас­кра­сок, нуж­но пере­мно­жить эти чис­ла: 1 × 2 × 3 × 4 × 5 × 6 = 720. Это мак­си­маль­ное коли­че­ство всех вари­ан­тов покрас­ки. Сре­ди них обя­за­тель­но будут неуни­каль­ные вари­ан­ты, когда мы, напри­мер, раз­вер­нём кубик и полу­чим точ­но такой окрас, как и в дру­гом случае.

Теперь посчи­та­ем, сколь­ко раз­лич­ных поло­же­ний на стар­те может при­ни­мать куб. Бла­го­да­ря это­му мы узна­ем коли­че­ство повто­ров, кото­рые полу­чат­ся при окраске.

Когда мы берём куб в руки лицом к себе, мы можем это сде­лать шестью раз­ны­ми спо­со­ба­ми, пото­му что у куба 6 гра­ней. Ещё мы можем 4 раза вра­щать его по часо­вой стрел­ке, гля­дя на ту же лице­вую сто­ро­ну. Полу­ча­ет­ся, у нас есть 24 вари­ан­та, что­бы зафик­си­ро­вать куб в одной пози­ции на стар­те. Это и есть коли­че­ство повто­ров при окрас­ке, пото­му что мы можем повер­нуть куб так, как нам нуж­но, что­бы най­ти дубль.

В ито­ге у нас есть 720 вари­ан­тов окрас­ки и 24 поло­же­ния на стар­те. Теперь мы можем узнать коли­че­ство уни­каль­ных окра­сов, раз­де­лив одно на дру­гое: 720 / 24 = 30.

Полу­ча­ет­ся, что блогер-художник смо­жет отпра­вить уни­каль­ные куби­ки толь­ко 30 побе­ди­те­лям, а 5 осталь­ных полу­чат уже неуни­каль­ную рас­крас­ку. А всё пото­му, что бло­гер пло­хо знал мате­ма­ти­ку и не дру­жил с алгоритмами.

А зачем мне это?

Уме­ние сокра­щать вари­ан­ты и нахо­дить мини­маль­но доста­точ­ные дей­ствия — важ­ное каче­ство для про­грам­ми­ста. Бла­го­да­ря ему у нас появ­ля­ют­ся корот­кие опти­маль­ные алго­рит­мы, а не раз­ду­тые на сот­ни строк кода, кото­рые посто­ян­но про­ве­ря­ют одно и то же и зря тра­тят машин­ное время.

Текст:

Миха­ил Полянин

Редак­тор:

Мак­сим Ильяхов

Худож­ник:

Даня Бер­ков­ский

Кор­рек­тор:

Ири­на Михеева

Вёрст­ка:

Мария Дро­но­ва

Соц­се­ти:

Олег Веш­кур­цев