Кубик Рубика

IX Региональная научно-практическая конференция

‹‹Колмогоровские чтения - 2013››

Конкурс исследовательских работ

                                        Секция ‹‹Математика»

Тема: Кубик Рубика

Выполнил: Восканян Давид Асатурович

МОУ ‹‹СОШ № 2 ст. Архонская›› 9 класс

Научный руководитель Уймина Татьяна Алексеевна учитель математики

МОУ ‹‹СОШ № 2 ст. Архонская››

Владикавказ, 2013

Содержание

1. Краткая историческая справка.

2. Комбинаторика

3. Нахождение оптимального решения.

4. Нижние и верхние оценки.

5. Скоростная сборка.

6. Текущие рекорды.

7. Компьютерные программы.

8.Соревнования в России.

9. Чемпионат Европы 2010,2012 г.

10.Другие фигуры.

11. Магия кубика.

Введение

   Одной из целей данной работы – рассказать о достоинствах этой замечательной головоломки,  в которую с удовольствием стали играть и школьники и академики,  находя в ней достоинства,  сообразные уровню учености,  образования и склонности к исследованиям.

   Работа рассказывает о кубике Рубика, о популярности этой головоломки и истории ее появления, рассматривается комбинаторика возможных состояний,  способы нахождения оптимального варианта сборки, самый традиционный алгоритм – «алгоритм Бога». Но универсальную схему бога для сборки кубиков Рубика знает только Чак Норрис. Оптимальная схема находится путём сложнейших вычислений.

   Рассказывается о рекордах, а также в работе также представлены различные «сородичи» кубика (его разновидности).  

   Самая главная часть работы – практическая, в которой будет продемонстрированы способы сборки и, конечно же, личные рекорды.

Комбинаторика

     Число всех достижимых различных состояний кубика Рубика 3x3x3 равно (8! × 38−1) × (12! × 212−1)/2 =43 252 003 274 489 856 000. Это число не учитывает то, что ориентация центральных квадратов может быть разной. С учётом ориентации центральных квадратов количество состояний возрастает в 46/2 = 2048 раз, а именно до 88 580 102 706 155 225 088 000 состо-яний. Однако при сборке кубика ориентацию центральных квадратов обычно не учитывают, поскольку на большинстве кубиков нет пометок, которые позволяли бы её отслеживать.

Нахождение оптимального решения

   Алгоритм, собирающий кубик Рубика за минимальное число ходов, традиционно называется «алгоритмом Бога». Максимальное возможное число ходов, которое такой алгоритм может сделать, называется «числом Бога». Долгое время о числе Бога были известны только нижние и верхние оценки. Однако последний анонсированный (хотя и не проверенный) результат утверждает, что число Бога равно 20. Простого описания «алгоритма Бога» при этом по-прежнему не найдено, оптимальная сборка кубика осуществляется с помощью трудоёмких вычислений.

Нижние и верхние оценки

   Известны конфигурации, требующие для сборки не менее 20 ходов, что является наибольшей известной нижней границей для числа Бога. В июле 2010 года было доказано, что число Бога в точности равно 20.

   Нахождение верхних оценок для числа Бога имеет богатую историю.

   Доказательство верхней границы в 26 ходов было сделано  исследователями Дэниелом Канклом и Джином  Куперманом (Kunkle and Cooperman).

   С помощью больших по объёму расчётов на компьютере (7,8 ядро-лет) математик Томас Рокицки (Tom Rokicki) доказал, что из любой начальной конфигурации кубик можно собрать не более чем за 23 хода.

Скоростная сборка

    Люди, увлекающиеся скоростной сборкой кубика Рубика, называются спидкуберами. А сама скоростная сборка — спидкубинг (англ. speedcubing).

    На данный момент одним из самых популярных методов скоростной сборки является метод Джессики Фридрих.

Официальные соревнования по скоростной сборке кубика Рубика регулярно проводятся всемирной ассоциацией кубика — en: World Cube Association (WCA). Каждый год проходит чемпионат Европы или чемпионат мира.

    Согласно правилам WCA, перед сборкой кубы должны быть перемешаны по алгоритму (scramble), сгенерированному компьютером с помощью программы Cube Explorer (для куба 3×3×3, для других головоломок есть отдельные программы генерации скрамблов). При этом у всех участников начальные позиции перемешанного кубика (скрамблы) должны быть одинаковыми.

    Победитель определяется не по результату единичной сборки, а по среднему времени из 5 попыток, при этом лучшая и худшая попытки не учитываются, а вычисляется среднее из оставшихся 3-х. Однако в других дисциплинах могут использоваться и другие варианты: среднее из 3 (например, для куба 7×7×7), лучшее из 3.

Текущие рекорды

   Нынешний рекорд скоростной сборки кубика был установлен 25 июня 2011 года на соревнованиях в Мельбурне Феликсом Земдегсом: он собрал кубик размера 3×3×3 за 5,66 секунды]. Он же и там же поставил предыдущий мировой рекорд 6,24 секунды 7 мая 2011 года. Предшествующие рекорды в 7,08 и 8,72 секунд принадлежали соответственно голландцу Эрику Аккерсдейку и японцу Ю. Накадзиме. Неофициальный рекорд принадлежит также Феликсу Земдегсу и составляет 5,36 секунды.

   Чемпионом мира 2011 года стал Михаил Плешкович из Польши, показавший в финале чемпионата среднее время 8,65 секунды. Михаил Плешкович из Польши собрал кубик рубика одной рукой за 9,53 секунды. Маршелл Эндрю из Венгрии собрал кубик рубика вслепую за 27,65 секунды. Необычное решение головоломки продемонстрировал Фахри Райхан из Индонезии: он собрал кубик ногами за 27,93 секунды.

   В октябре 2011 года робот CubeStormer II, специально собранный из 4 наборов конструктора Lego Mindstorms, побил рекорд человека и собрал кубик за 5,53 секунды (впрочем, следует отметить, что рекорд был установлен не в присутствии комиссии WCA, и, следовательно, официальным не является, а неофициальный рекорд, установленный человеком, ещё меньше).

Компьютерные программы

    Головоломки, подобные кубику Рубика, могут быть смоделированы на компьютере: от простых 2×2×2, 3х3х3 до очень сложных вариантов (100×100×100 или 1000×1000×1000 кубиков), до невозможных в физическом мире — 4-, 5-, и даже 7- мерные аналоги.

Соревнования в России

   8 марта 2009 года прошёл первый официальный чемпионат России, победителем стал Антон Ростовиков. 26—27 ноября 2011 года в Москве прошёл официальный открытый чемпионат России, в котором приняли участие около 60 человек в дисциплинах от 2×2×2 до 7×7×7, также сборка кубика Рубика вслепую. Чемпионом в дисциплине 3×3×3 стал Сергей Рябко со средним результатом в финале 10,66 секунды. Рекорд России в единичной сборке принадлежит Сергею Рябко и составляет 7,68 секунды.

Чемпионат Европы 2010, 2012 г.

    С 1 по 3 октября 2010 года в Будапеште прошёл чемпионат Европы, собравший участников, соревновавшихся в различных дисциплинах. Чемпионом Европы в сборке классического кубика 3×3×3 стал российский спидкубер Сергей Рябко, опередивший в финале в том числе бывшего рекордсмена Эрика Аккерсдейка, со средним временем в финале 10,31 секунд.

    С 12 по 14 октября 2012 года во Вроцлаве (Польша) прошёл чемпионат Европы. Чемпионом второй раз подряд стал участник из России Сергей Рябко, опередивший чемпиона мира. Среднее время Сергея составило 8,89 сек.

Другие фигуры…

    Кроме Кубика Рубика существует множество других головоломок, аналогичных по принципу устройства, но другой формы. Среди них наиболее известны: тетраэдр «Пирамидка Мефферта» (в СССР известна как «Молдавская пирамидка» и «Японский тетраэдр»), изобретённый раньше кубика, и являющийся самым простым для сборки из здесь перечисленных головоломок; другой тетраэдр — «Jing’s Pyraminx»; октаэдр, известный как «Trajber's Octahedron 3 × 3 × 3» — головоломка, которую можно бы было назвать двойственной Кубику Рубика по аналогии с понятием двойственный многогранник; додекаэдр «Мегаминкс», являющийся додекаэдрическим аналогом Кубика Рубика 3 × 3 × 3; множество головоломок этих же (в особенности октаэдра) и других форм: ромбододекаэдр, кубооктаэдр, усечённые тетраэдр и октаэдр и др. [1]

Магия кубика

Рассмотрим свойства магических квадратов на примере известной многим детской игры-головоломки.   На рисунке, приведенном ниже приводится магический квадрат  Кубика- Рубика.

       Показаны два варианта Кубика, на которых взаимодополнительные триады обозначены одинаковыми числами (или символами). На рисунке слева маленькие кубики пронумерованы цифрами, а на рисунке справа маленькие кубики обозначены символами.  

       Особенность этих двух кубиков в том,  что они имеют две общие грани (белую и красную). Это различие видно из сравнения свойств их главных диагоналей. На левом кубике - это единичная диагональ, а на правом главную диагональ образуют зеленые кружочки.

Можно раскрыть и тайну порождения магических квадратов.  Все магические квадраты порождаются тривиальным алгоритмом.

Так все магические строки  Кубик - Рубика порождаются следующим образом:

1.Заполняется первая строка магической матрицы (1,2,3).

2. Полученная строка сдвигается на один разряд вправо (0,1,2,3), а последний позиционный разряд числа (в нашем случае -3)  переносится в первый разряд числа, т.е. получаем (3,1,2). Полученный результат записывается во вторую строку.

3. Полученную строку снова сдвигаем, последний разряд числа переносим в первый разряд и записываем на место третьей строки.

        Данный алгоритм можно распространить на матрицу любой размерности. В частности, мы теперь легко можем получить магический куб размерности (9х9х9).

И этот куб не будет единственным магическим кубом данной размерности. Таких кубов можно построить теперь великое множество. И каждый из них будет нести собственные смыслы. [2]

Выводы

    Таким образом, головоломка «Кубик Рубика» («Волшебный кубик», «Венгерский кубик» и даже просто «Рубик») привлекла внимание, как говорится, «всех групп населения» и получила широчайшее распространение. О достоинствах этой замечательной головоломки, в которую с удовольствием стали играть и школьники и академики, находя в ней достоинства, сообразные уровню учёности, образования и склонности к исследованиям. [1]

        Список литературы

1. http://ru.wikipedia.org

2. Журнал «Наука и жизнь»