Дивовижна математика всередині кубика Рубіка

Минулого року виповнилося 40 років з того часу, як людство дізналося про кубик Рубіка. Ця головоломка відразу збентежила уми майже півмільярда ентузіастів, які вважали, що можуть розкрити божевільні секрети цього дивовижного кубика, якщо його розберуть на складові.

Напередодні ювілею кубика Рубіка (так, ювілею!) та стартів нових потоків курсів Математика для Data Science та його розширеної версії Математика та Machine Learning для Data Science, настав час раз і назавжди розгадати цю головоломку, цього разу за допомогою досить складної математики. Фізичні начинки кубика можуть бути виготовлені з пластику, але його віртуальними начинками, звичайно ж, є числа. Давайте ж поринемо в цей світ чисел.

Розбір кубика Рубіка на блоки

Почнемо із базових знань. Кубик Рубіка розміром 3x3x3 має шість граней, кожен свого кольору. Центральний кубик кожної грані прикріплений до внутрішньої хрестовини, що скріплює всі елементи куба. Центральні кубики можуть лише обертатися довкола своєї осі. Одні й самі кольори завжди розташовуються навпроти один одного; на стандартному кубі білий колір знаходиться навпроти жовтого, червоний – навпроти помаранчевого, синій – навпроти зеленого.

Якщо розібрати кубик Рубіка, то можна побачити, що він складається з трьох типів складових блоків. Перший тип: центральна хрестовина, де утримуються центральні кубики кожної грані. Другий тип – малі кубики розміром 1x1x1. Кутові кубики мають три кольорові сторони, бортові кубики – дві. Кубик Рубика має одну хрестовину, вісім кутових кубиків та дванадцять бортових кубиків.

За допомогою математики ми можемо дізнатися загальну кількість способів, якими можна перемішати кубик Рубіка: 43252003274489856000. У вигляді математичної формули це число можна представити таким чином: (3 8 8!) (2 12 12!) / 12. Ось як виходить ця формула.

Перший елемент, 3 8 визначає кількість можливих варіантів обертання восьми кутових кубиків. Кутовий кубик можна вставити в паз, який може повертатись трьома різними способами. Тобто для кожного з восьми кутових кубиків множник дорівнює 3 тому відбувається множення до 3 8 .

Далі враховуємо переміщення кожного кутового кубика. Усього кутових пазів вісім, тому перший кутовий кубик має вісім варіантів. У другого кутового кубика залишається сім варіантів, у наступного ліворуч кубика – шість варіантів і так далі, аж до останнього кутового кубика, який має увійти до останнього кутового пазу. Це дає факторіал 8!

Таким чином, перша частина формули (3 8 8!) Здійснює підрахунок всіх способів, якими кутові кубики можуть розміщуватися в кубі. Значення 3 8 – це їхня орієнтація, а 8! - Їхнє становище.

У наступній частині формули (21212!) застосовується той же принцип, але тепер для ребер. Ребра мають лише дві орієнтації, тому 12 ребер можуть мати загалом 2 12 орієнтацій. Усього є 12 положень, тому 12! є кількість способів, якими кубики можуть бути розміщені в таких положеннях.

Що ще залишилося у формулі (3 8 8!) (2 12 12!) / 12? Залишилося розподіл на 12. Поділ на 12 пов'язане з однією особливістю кубика Рубика, про яку багатьом відомо, але яку не до кінця розуміють. Проведемо уявний експеримент (який, можливо, ви вже проводили наживо!):

Припустимо, ви розібрали кубик Рубіка, витягли з нього всі кубики, а потім вставили всі кубики назад у випадкові пази (при цьому кутові кубики можна встановити лише у кути, а бортові кубики – лише на ребра). Ви отримаєте конструкцію, яка виглядає як звичайний перемішаний кубик, і зараз ми підрахували всі можливі комбінації створеного таким чином куба: (3 8 8!)(2 12 12!). Тепер запитаємо, чи завжди можна зібрати такий перемішаний кубик, не розбираючи його на частини?

Тут криється пастка, в яку потрапляло безліч любителів-початківців розгадувати цю головоломку. Якщо ви тренуєтеся і хочете перемішати вже зібраний куб, необхідно зберегти в цілості і зібрати його вручну. Якщо розібрати куб на частини і зібрати кубики випадково, ймовірність того, що головоломку можна буде вирішити, складе всього 1 до 12.

Відповідь криється в алгоритмах

Хочете зрозуміти, чому ймовірність становитиме лише 1 до 12? Є добрий візуальний спосіб зрозуміти, чому ймовірність саме така. Шанс зібрати розібраний на складові кубики і знову випадково перемішаний великий куб дорівнюватиме шансам зібрати куб із наступними зразками граней:

Помаранчева, жовта та зелена сторони грані (не показані) збираються як завжди.

Ми розмістили їх таким чином, щоб було зрозуміло, як виходить коефіцієнт 12. Ряд 1 має нормальні кути. У рядів 2 та 3 один кут повернутий. Стовпець 1 має нормальні ребра. У стовпців 2 та 3 одне ребро повернуто. У стовпця 3 два ребра поміняні місцями. І, нарешті, в стовпці 4 одне ребро повернене і два ребра поміняні місцями.

Таким чином, 12 кубів, представлених вище на фотографіях, не можуть бути перетворені один на одного.13-го варіанта, який не можна перетворити в жодний із таких 12 кубів, не існує. Звідки це може бути відомо?

Тим часом, що може і що не може бути зроблено шляхом переміщення граней куба, є зв'язок. Послідовність переміщень граней куба ентузіасти збирання часто називають "алгоритмом". Популярними алгоритмами є ті, які переміщують лише кілька кубиків, залишаючи інші недоторканими. Число 12 виникло з тієї причини, що такі алгоритми накладаються обмеження.

Число 12 складається з трьох множників: 12 = 3 * 2 * 2. Звідки беруться множник 3 і два множники 2?

Множник 3: існує алгоритм, який повертає кожен із двох різних кутів, але немає алгоритму, який повертає один кут (залишаючи всі інші недоторканими). Іншими словами, якщо взяти звичайний кубик Рубіка, вийняти один з його кутів і замінити його на повернутий, такий куб зібрати буде неможливо, тобто ви переміститеся з лівого верхнього кута нашої діаграми в одну з клітин прямо під ним.

Однак, якщо повторити цю операцію та повернути ще один кут, другий множник 3 не додасться. Тепер, коли в кубі повернуто два кути, ми можемо послідовно застосовувати алгоритм, що повертає два кути, доки не зафіксується принаймні один з кутів. Якщо інший кут випадково стане на своє місце, можемо вважати, що нам пощастило і такий куб можна зібрати. Орієнтація кутів може бути троякою.

Міркування щодо першого множника 2 аналогічні. Існує алгоритм, що повертає на своє місце кожне з двох різних ребер, але алгоритму, здатного повернути на своє місце лише одне ребро, не існує.Таким чином, будь-яка кількість повернутих ребер може бути зведена до одного ребра, яке в результаті або виявиться, або не виявиться повернутим - варіанти всього два.

Останній множник 2 фактично відноситься до граней та кутів, хоча на діаграмі ми показали його з гранями. Існує алгоритм, що змінює місцями два кути, одночасно змінюючи місцями два ребра. Але немає жодного алгоритму, який був би здатний міняти місцями не тільки пару кутів, не тільки пару ребер.

Візьміть куб, витягніть два ребра і поміняйте їх місцями - на діаграмі ви потрапите на стовпець, розташований між стовпцями 1 і 3, або між стовпцями 2 і 4. Аналогічні міркування можна застосувати, якщо поміняти місцями пару кутів. Проте зміна подекуди пари ребер і пари кутів врівноважує баланс, оскільки алгоритм виходу з таких станів існує.

Отже, після того, як ми пояснили, звідки взялися всі множники в коефіцієнті 12, можна зрозуміти, звідки взялася формула (3 8 8!) (2 12 12!)/12. Число всіх можливих положень кубиків у кубі становить (3 8 8!) (2 12 12!), але тільки дванадцята частина таких положень годиться для збирання куба. Таким чином, число (3 8 8!) (2 12 12!)/12 позначає кількість способів, якими можна перемішати кубик Рубика, не розбираючи його частини.

Доказ Популярної механіки

Якщо ви досить цікаві, то, напевно, захочете перевірити, чи вірні зроблені вище затвердження. Чи існують складніші математичні прийоми, які можуть довести, що "алгоритму, здатного повернути на своє місце лише один бортовий кубик, не повертаючи будь-який інший кубик, не існує"? Так, такі математичні прийоми є.Ось як приблизно будується такий математичний доказ:

При перевертанні грані куба відбувається переміщення чотирьох бортових кубиків. Розглянемо, наприклад, алгоритм із десяти переміщень. Для кожного кубика виконайте алгоритм і порахуйте скільки разів переміщався кубик, і назвіть цю кількість "числом переміщень кубика". Складіть ці числа для кожного бортового кубика, всього має вийти 40 переміщень кубиків, тому що кожне з 10 переміщень додає до суми четвірку.

У загальному випадку для будь-якого алгоритму загальна кількість переміщень бортових кубиків має бути кратна 4. Тепер пара важливих фактів: якщо бортовий кубик переміщати парну кількість разів і повернути його назад у той самий паз, він матиме таку саму орієнтацію. І навпаки, якщо бортовий кубик переміщатиме непарну кількість разів і повернути його назад у той самий паз, він матиме перевернуту орієнтацію.

Звичайно, сказане вище можна довести з використанням складніших математичних методів, але ми не збираємося сильно заглиблюватися в математику, інакше обсяг цієї статті перевершить усі мислимі та немислимі межі. Ці два факти можна перевірити експериментально, щоб зрозуміти, що все відбувається саме так. (У цьому доказі поворот на 180 градусів вважається двома переміщеннями кожного відповідного кубика.)

Тепер давайте розглянемо гіпотетичний алгоритм, що досягає мети, що повертає один бортовий кубик, залишаючи при цьому недоторканності інший кубик. Одне повернене ребро було переміщено алгоритмом непарну кількість разів, а кожне з 11 інших ребер було переміщено парну кількість разів.Сума 11 парних чисел і одного непарного числа завжди непарна, але ми показали раніше, що така сума має бути кратною 4. Чи може непарне число бути кратним 4? Ні, не може. Отже, такого алгоритму немає.

Тепер ви розумієте, що число (3 8 8!) (2 12 12!)/12 є кількістю можливих станів куба. Але для математики, що вивчає куб, це лише попередня інформація. Перед тим як починати застосовувати складніші математичні методи, задайте собі головне питання: "Чи існують у цій темі математичні питання, що залишилися без відповідей?"

Число Бога та багато іншого

Головним завданням, поставленим винахідником головоломки, природно, було збирання куба. Ерно Рубік (Ernő Rubik) створив перший прототип головоломки у 1974 році, і через шість років вона надійшла до масового продажу. Звичайно, він був першим, якому вдалося зібрати куб.

1980 року кубик Рубіка став хітом продажів у магазинах іграшок. Але деякі математики вже кілька років експериментували з ранніми версіями. Одним із них був доктор Девід Сінгмастер (David Singmaster) – упорядник знаменитого путівника "Записки про Чарівний кубик Рубіка" і розробив нотацію для запису операцій повороту граней куба. Ця нотація стала стандартом і відома як нотація Сінгмастера.

Якби це була стаття писалася у 1980-х роках, то, можливо, варто було б докладніше пояснити читачам, що таке нотація Сінгмастера, та використовувати її при описі алгоритмів збирання куба. Безліч авторів статей так і робили. Але сьогодні на Youtube викладено безліч відеоінструкцій, тому в цій статті ми не відволікатимемося на опис нотації.

За останні кілька десятиліть рекорд збірки кубика Рубіка на якийсь час постійно оновлювався. На сьогодні світовий рекорд збирання кубика Рубіка людиною становить 3,47 секунди. У 1997 році доктор Джесіка Фрідріх розробила найвідоміший, найшвидкісніший і найгнуткіший метод швидкого збирання кубика Рубіка Найшвидші збирачі кубика Рубіка сьогодні користуються різними варіантами збирання від доктора Фрідріх.

У міру того, як одні користувачі відточували майстерність збірки, інші намагалися вирішувати важливі математичні питання, пов'язані з цією головоломкою. За скільки ходів можна зібрати куб незалежно від того, в якому стані він спочатку був? Якщо хтось перемішав куб за 500 ходів, то, природно, зібрати його можна за 500 ходів. Наскільки саме менше ходів?

Відповідно, було поставлено головне математичне завдання: чи існує магічне число, що дозволяє сказати: "будь-який перемішаний куб може бути зібраний саме за таку кількість ходів [або менше]"? Завдяки дотепному зауваженню, що для набуття почуття впевненості потрібне божественне втручання, це число отримало назву "Кількість Бога".

Перша гіпотеза про існування Числа Бога була висунута доктором Морвеном Тістлетвейтом (Morwen Thistlethwaite) у 1981 році, який довів, що це число існує і не перевищує 52. Іншими словами, будь-який перемішаний куб може бути зібраний за 52 ходи або менше.

У 1990-2000-х роках математики пішли ще далі. У червні 2010 року група з чотирьох вчених довела, що Число Бога дорівнює 20. На цьому веб-сайті, який ведуть ці вчені, представлені останні знання про кубик Рубіка.

Іншими словами, хоч би який хаотичний первісний стан мав Кубик Рубика, його завжди можна зібрати за 20 або менше ходів.

Для математиків у темі кубика Рубіка залишилися лише невеликі ласі шматочки.

Кількість комбінацій, для збирання яких потрібно один хід, становить 18. Це значення легко розрахувати. Є шість граней і три способи повороту кожної з них. можна припустити, що зі збільшенням кількості ходів також буде збільшуватися складність обчислень. точно знаємо кількість комбінацій, для збирання яких потрібно рівно 15 ходів, але поки що не цілком точно представляємо кількість комбінацій для числа ходів від 16 до 20.

І це – остання невирішена задача в математичній темі кубика Рубіка. Будемо чекати, коли хтось її вирішить.

Отримайте потрібні знання та навички на курсі Математика для Data Science та його розширеної версії Математика та Machine Learning для Data ScienceА промокод HABR дасть знижку 50%.

Дізнайтеся, як прокачатися в інших спеціальностях або освоїти їх з нуля:

ПРОФЕСІЇ

• Професія Java-розробник
• Професія QA-інженер на JAVA
• Професія Frontend-розробник
• Професія Етичний хакер
• Професія C++ розробник
• Професія Розробник ігор на Unity
• Професія Веб-розробник
• Професія iOS-розробник з нуля
• Професія Android-розробник з нуля

Рекорди збирання кубика Рубіка

Більшість людей, які вже навчилися збирати кубик Рубіка, постійно продовжують покращувати свої навички: вчать нові алгоритми, доводять до ідеалу високошвидкісні рухи граней, переходять із 3х3 на 4х4, 5х5 тощо. Ці люди називаються «спідкубери», адже збірка кубика Рубіка вже давно стала професійною дисципліною. У цій статті ми розглянемо всі світові рекорди зі збирання кубика Рубіка 3х3 – найпопулярнішої дисципліни.

Спочатку ми списком покажемо Вам рекорди світу, а далі Ви можете почитати про їхню історію та самих спідкуберів:

• Світовий рекорд 2013 року (5,66 секунд).
• Світовий рекорд 2015 року (5,25 секунд).
• Світовий рекорд 2016 року (4,73 секунди).
• Світовий рекорд 2017 року (4,69 секунд).
• Світовий рекорд травень 2018 року (4,22 секунди).
• Поточний світовий рекорд - листопад 2018 року (3,47 секунди).

Перший рекорд світу

Першим рекордсменом кубика Рубіка 3х3 став 16-річний в'єтнамсько-американський студент Minh Thai. Його рекордне складання в 1982 році відбулося в рамках чемпіонату зі спідкубінгу World Rubik's Cube Championship 1982. Кубик він зібрав за 22.95 секунди. Варто зазначити, що рекорд встановлений не на сучасному кубі з магнітними гранями і неперевершеним крученням, а на пополярному «не дуже» кубику.

Перший світовий рекорд - Minh Thai: 22.95 секунд.

Після трапився період затишшя, але не тому, що чемпіонатів не проводилося або всі спідкубери розчарувалися у своїх вміннях, а просто тому, що не було організації, яка могла б чітко і правильно структурувати та впорядкувати результати спідкуберів.

У 2004 році з'являється організація WCA – World Cube Association (Всесвітня кубикова асоціація) та бере все під свій контроль.

З того часу багато чого змінилося: кубики, правила, дисципліни і, звичайно ж, рекордсмени.

Рекорди останнього десятиліття

У спідкубінгу є багато крутих хлопців, але, мабуть, найвидатнішим можна назвати австралійця Фелікса Земдегса. Він поставив 117 (тільки вдумайтеся!) світових рекордів і є рекордсменом світу зі збирання кубика Рубіка 3х3х3 в даний момент - 4.22 секунди за одну спробу та 5.8 секунд - Середній час за трьома спробами. Також, Фелікс світовий рекордсмен у дисциплінах: 4х4, 5х5, збиранні кубика 3х3 однією рукою.

У січні 2010 року він першим у світі зібрав кубик менш ніж за 10 секундд. У 17 років на чемпіонаті він встановив свій перший світовий рекорд і довів свою першість серед спідкуберів усього світу.

Якщо ви подумали, що Феліксу немає рівних – це не так. Один із головних його суперників - Макс Парк, американський спідкубер. На його рахунку вже 12 світових рекордів. У порівнянні з кількістю рекордів Фелікса це не дуже вражає, але якщо заглибитися в кожен рекорд - вони теж вражають.

Макс Парк став першим рекордсменом світу зі збирання кубика Рубіка 3х3 однією рукою за середнім часом із 5 спроб менш ніж за 10 секунд. Також Макс встановив рекорди світу у складанні кубиків 6х6 та 7х7.

Наступний чемпіон світу – американець Матс Фальк. Став він відомим спідкубером підписання контракту з QiYi MoFangGe, одним із найкращих світових брендів у сфері головоломок. На честь Матса названо одні з найкращих моделей кубика Рубіка, яку знають усі спідкубери.

На його рахунку 5 світових рекордів. Найприкріша ситуація сталася на чемпіонаті Jawa Timur Open 2016: там він поставив рекорд зі збирання кубика 3х3 – 4.74 секунди. Але трохи пізніше, на цьому ж турнірі Фелікс зібрав кубик за 4.73 секунди і випередив Матса.

Ще відомі рекордсмени (як світу, так і національні): Кевін Хайс (у нього багато рекордів забрав саме Матс Фальк, при тому як світові, так і національні обидва хлопці зі США), Дмитро Добряков (Росія), Владислав Шавельський (Росія) .

Топ 7 рекордів кубика Рубіка – у відео нижче.

І пам'ятайте, що рекорди встановлюються лише професійними кубиками. А вони є у нас у продажу за відмінними цінами, дивіться самі: