Математичні загадки кубика Рубіка
Дивовижна математика кубика Рубіка
У минулому році виповнюється 40 років з тих пір, як кубик Рубіка вперше з'явився на полицях магазинів іграшок. Спочатку над ним сміялися, говорили, що це дуже проста головоломка. Але згодом більшість охочих розгадати загадку кубика опинялися в глухому куті - зібрати іграшку, виявляється, не так-то просто.
Варто визнати, що ця головоломка дійсно зводить з розуму. Тому потрібно розкрити її секрети. А криються вони в сфері математичних розрахунків. Не варто звертати уваги на пластикове втілення кубика Рубіка, його суть - це числа.
Особливості пристрою кубика Рубіка
Біля кубика шість граней, центр кожної з них прикріплений до несучого каркасу, який утримує куб. Вони обертаються тільки навколо своєї осі. У результаті одні й ті самі кольори завжди виявляються протилежними один одному. На стандартному кубі формуються такі пари кольорів:
- білий - жовтий;
- червоний - помаранчевий;
- синій - зелений.
Кубик Рубіка складається з трьох типів блоків. Це центральний каркас, що з'єднує центр кожної межі, на якій закріплений одноколірний квадрат. Кутові блоки, які мають три кольорові сторони, а розташовані по краях елементи - дві. Так, структура кубика Рубіка включає одне ядро, 8 кутових і 12 елементів, розміщених по краях.
Загальна кількість способів, якими можна «зашифрувати» кубик Рубіка: 43 252 003 274 489 856 000. Це значення з'являється в результаті виконання обчислень за наступним математичним виразом: (388)(21212)/12.
Перша «цифра» - 38 - це кількість способів повороту восьмикутних кубів. При цьому кутовий блок може розміщуватися на своєму місці трьома різними способами. Це фактор 3 для кожного з восьми кутових кубів, тому вони множаться на 38.
Є 8 кутових слотів, тому у першого кутового блоку є 8 варіантів розташування. У другого кутового кубика залишилося 7 варіантів, у третього - 6 і так далі, до останнього кутового блоку, який розміщується в останньому кутовому слоті. Це дає таке обчислення: 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1, що дорівнює 8, або «вісім факторіалів».
Таким чином, перший фрагмент виразу (388) враховує кожен варіант розміщення кутових блоків, де 38 - їх загальна кількість способів повороту, а 8 - це їх місця.
Наступна частина виразу (21212) - це такий самий розрахунок, але тільки для крайніх елементів. Вони мають лише 2 способи повороту, тому 12 блоків мають загалом 212 варіантів розташування.
Операція, що залишилася - поділ на 12 - є фактором, який не завжди розуміють охочі скласти головоломку. Для його усвідомлення необхідно подумки виконати певний алгоритм дій. Потрібно повністю розібрати кубик Рубіка, а потім помістити всі блоки у випадкові слоти. З кутовими елементами розташувати тільки по кутах, а з елементами ребер - по краях. Так виходить «зашифрована» головоломка.
І тут потрібно врахувати, що до цього за допомогою математичного виразу враховувався кожен спосіб, яким можна було зробити те ж саме. А тепер слід відповісти на питання: чи можна зібрати кубик Рубіка в такому випадку, не розбираючи його? І правильна відповідь буде - ні.
У цю пастку потрапляли багато фанатів головоломки. Якщо розібрати кубик на частини і зібрати блоки у випадковому порядку, то існує тільки 1 спосіб з 12 повного рішення головоломки.
Секрет криється в алгоритмах
Описаний вище експеримент добре видно на фото нижче. Воно дає розуміння, чому зібраний випадковим чином кубик Рубіка надає лише 1 шанс з 12 вирішити головоломку. Тут є зв'язок з тим, що можна і чого не можна зробити, переміщуючи елементи куба. Послідовність ходів фанати головоломки називають «алгоритмами». Найчастіше використовуються ті, які передбачають переміщення декількох блоків, залишаючи інші недоторканими. Обмеження алгоритмів є ключем до цифри «12» у вираженні. Вона формується з двох і трьох факторів.
Фактор 3 зводиться до наступного: є алгоритм, за яким повертається кожен з двох різних кутів, але немає алгоритму, що дозволяє прокручувати тільки один кут, залишаючи всі інші недоторканими. Тому якщо взяти нормальний кубик Рубіка, видалити один кут і замінити його іншим, вирішити головоломку буде неможливо.
Але якщо повторити процедуру, повернути ще один кут, то другий коефіцієнт 3 не додасться. Тепер, коли 2 кути прокручені, можна застосувати алгоритм, який дозволяє переміщати два кутових елементи, поки хоча б один з них не встане на місце. Якщо так трапиться, що інший займе своє місце, то фанат головоломок отримає «вирішуваний» кубик. Загалом розташовуватися кутові блоки можуть одним із трьох способів.
Є алгоритм збору кубика Рубіка, який передбачає переміщення двох пар кутових блоків і ребер. Але не існує механізму, який дозволяв би рухати тільки одну пару кутових блоків і ребер. Є алгоритм, що дозволяє працювати тільки з парою ребер, але неможливо зібрати головоломку, переміщуючи тільки одну межу. Якщо «вирвати» 2 ребра або 2 кутових блоки і поміняти їх місцями, то вони взаємно замінять один одного.
Виходить, математичний вираз (388) (21212 )/12 показує, скількома варіантами може шифруватися кубик Рубіка. Тут цифра «12» - це фактори, що дозволяють зібрати головоломку, і тільки один з них дозволить зробити це повністю без розбирання «чарівного кубика».
Математичний доказ алгоритму кубика Рубіка
Чи можна довести, що не існує алгоритму, який дозволяє перевертати один крайній кубик, не переміщуючи інший блок? Так, такий доказ існує і виглядає наступним чином.
Коли межа повертається, 4 крайні блоки пересуваються. Тепер потрібно зробити 10 переміщень для кожного елемента. При цьому потрібно підрахувати кількість дій. Потім треба скласти числа для кожного блоку на краю. Загальна кількість ходів має дорівнювати 40, так як кожне з 10 переміщень збільшує їх загальну кількість на 4.
Відповідно, сума ходів для елементів, розташованих на краях, повинна бути кратною чотирьом.
При цьому якщо блок на краю переміщується парну кількість разів і повертається на своє місце, він буде мати ту ж орієнтацію. І навпаки, якщо елемент переміщується непарна кількість разів і поміщається на місце, він буде перевернутий. Всі наведені вище алгоритми можна без зусиль перевірити на практиці.
Тепер варто розглянути схему, яка передбачає поворот одного елемента на місці, без задіяння інших. При цьому один блок переміщувався парну кількість разів, в той час як кожен з інших 11 елементів - непарне. Сума з 11 парних чисел і одного непарного завжди непарна. І раніше встановлено, що вона повинна бути кратна 4. Але це абсурд, такого не може бути. Ось доказ відсутності алгоритму, описаного вище.
Як прискорювалося рішення головоломки і «число Бога»
Ерно Рубік зробив свій перший прототип головоломки в 1974 році. Але його серійне виробництво почалося через 6 років - у 1980 році. Закономірно, що творець хитромудрого кубика першим його і зібрав.
Цікаво, що математики почали шукати рішення головоломки ще до старту її масового виробництва. Один з них, доктор Девід Сінгмастер, навіть написав керівництво під назвою «Нотатки про» магічний кубі «Рубіка». Саме він розробив метод листа для опису поворотів граней, який став стандартом і отримав назву Singmaster. Але йшов час, і метод неухильно застарівав. А в наш час на YouTube можна знайти безліч відеоруководств зі збору головоломки більш просунутими способами.
Закономірно, що час, за який вирішувалося завдання, стрімко скорочувався. Світовий рекорд зі швидкості збирання кубика Рубіка на даний момент становить 3,47 секунди. Прорив тут зробила доктор Джессіка Фрідріх. У 1997 році вона розробила алгоритм найбільш швидкого рішення головоломки. І сьогодні елементи цієї методики використовуються для встановлення нових світових рекордів.
Робота з вирішення головоломки ведеться в двох напрямках:
1. Розвиток швидкості, відточування моторики.
2. Математичні розрахунки.
Але досі невідомий мінімум ходів, необхідних для того, щоб скласти кубик Рубіка. Не визначено кількість рухів, яка дозволяла б вирішувати будь-який варіант головоломки. Багато хто вважає, що без божественного втручання тут не обійтися, тому назвав «числом Бога» кількість ходів, що дозволяє збирати кубик Рубіка в усіх можливих комбінаціях.
У 1981 році доктор Морвен Тістлетвейт довів, що на рішення будь-якого варіанту головоломки потрібно не більше 52 рухів. Так він наблизився до обчислення «числа Бога». Але дослідження продовжилися. У червні 2010 року команда з чотирьох вчених довела, що за 20 ходів можна вирішити будь-який варіант «шифрування» кубика Рубіка. Організований цими ентузіастами сайт містить передові алгоритми вирішення головоломки.
Залишилося тільки обчислити, скільки із загальної кількості комбінацій (43 252 003 274 489 856 000) розплутується певною кількістю ходів. Наприклад, число позицій, для вирішення яких потрібен один хід, - 18. Це легко підрахувати: є 6 граней і 3 способи скручування кожної.
Також неважко обчислити, скільки варіантів вирішується за допомогою двох або трьох ходів. Але в міру збільшення їх кількості ускладнюється підрахунок. На сьогоднішній день математики зупинилися на 16 ходах. До 20 залишилося небагато. І це останні невирішені моменти для кубика Рубіка.