Mathematicians sorted out Rubik’s giant cubes

1 min


Rubik's

Mathematicians from the Massachusetts Institute of Technology estimated the number of moves needed to solve the Rubik’s cube (that is, bringing the cube faces to the same color) of an arbitrary size. The preprint of their article (pdf) appeared on arXiv.org.

Rubik’s cube studies by mathematicians began in the early 80’s of the last century (the puzzle itself was created in 1974). As it turned out, the group of symmetries of the cube, acting on the set of its squares, is rather complicated and difficult to study. In 2010, game theory experts calculated on the supercomputer all 43 252 003 274 489 856 000 possible initial positions for the standard Rubik’s cube (3 by 3 by 3) and found that from any initial position the cube can be collected in just 20 moves.

In the framework of the new study, scientists were interested in the asymptotic estimate of the number of movements necessary to solve the Rubik’s cube (although, in this case, it would be more correct to call it a rectangular parallelepiped) with sides of arbitrary size. The parameter n is the length of the maximum side of the puzzle, and “asymptotic” in the name means that the estimate is not exact, but with an increase in n, the optimal number of moves increases as an estimate.

Researchers managed to establish that in the general case the number of moves is O (n2) – that is, the number of cube movements needed to solve the problem increases approximately as a square n multiplied by some constant. At the same time, scientists proposed a direct decision algorithm that implements the proposed assessment. In two particular cases, scientists have been able to improve this result.

So, it turned out that for the “cubic” Rubik’s cube, that is, the puzzle with the sizes n on n by n, and for the “rope” of Rubik – the puzzle with the sizes n on n by 1, the score looks like O (n2 / log n). The last effect is due to the fact that in one movement in similar puzzles one can put several squares in the right place at once.

The problem of solving the Rubik’s cube belongs to the class of algorithmic problems of reorganization. A typical example of such a problem, encountered in practice, is the permutation of the boxes in the right way in the warehouse.


Like it? Share with your friends!

What's Your Reaction?

cute cute
90
cute
lol lol
210
lol
love love
180
love
scary scary
90
scary
hate hate
240
hate
geeky geeky
270
geeky
omg omg
120
omg
Sprintally

Sprintally cover latest technology news update, Lifestyle, IT tutorials, Business news, Recipes, Travel, Street Fashion, Lifestyle, Animals, Nature, Beauty, Relationship and Dating, Lifehack, Celebrities, Computer literacy, Automobile, Software, Vogue, Education, Family, product and service reviews and IT support services!

0 Comments

Your email address will not be published. Required fields are marked *

8 + three =

Choose A Format
Story
Formatted Text with Embeds and Visuals
Poll
Voting to make decisions or determine opinions
List
The Classic Internet Listicles
Personality quiz
Series of questions that intends to reveal something about the personality
Trivia quiz
Series of questions with right and wrong answers that intends to check knowledge
Ranked List
Upvote or downvote to decide the best list item
Open List
Submit your own item and vote up for the best submission
Countdown
The Classic Internet Countdowns
Video
Youtube, Vimeo or Vine Embeds
Send this to a friend