1. Toys that are popular all over the world
1974 In the spring, E. Rubik, a professor of architecture at Budapest Institute of Applied Arts, had an interesting idea. He wants to design a teaching tool to help students intuitively understand the various rotations of space geometry. He thought about it and decided to make a 3×3×3 cube with small squares, and each face can be rotated at will. Such a cube can conveniently demonstrate various spatial rotations.
Although this idea is good, it faces a thorny problem in practice, that is, how to make all sides of such a cube rotate at will? Rubik tried many ideas, such as connecting small squares with magnets or rubber bands, but all failed. One afternoon that summer, he was enjoying the cool air by the Danube, and his eyes inadvertently fell on the pebbles by the river. Suddenly, a new idea flashed through his mind: treating the internal structure of a cube with a round surface similar to a cobblestone surface. The new idea succeeded, rubik quickly completed his own design and applied for a patent from the Hungarian Patent Office. This design is the familiar Rubik's Cube (also called Rubik's Cube) [Note 1].
Six years later, rubik's Rubik's Cube, led by a Hungarian businessman and amateur mathematician, entered the western European and American markets and became a fashionable toy all over the world at an alarming rate. In the next 25 years, the sales of Rubik's Cube exceeded 300 million. Among the players in the Rubik's Cube, there are both babbling children and bosses of multinational companies. Although the Rubik's Cube didn't become a teaching tool of space geometry as rubik imagined, it became the best-selling toy in history.
The magic of the best-selling Rubik's Cube lies in its amazing number of color combinations. When a Rubik's cube leaves the factory, each side has a color, and there are six colors in total. However, after these colors are disrupted, the number of combinations that can be formed is as high as 432.5 billion [Note 2]. If we make each of these combinations into a Rubik's cube, then these Rubik's cubes can be arranged together from the earth to the distant starry sky 250 light years away. In other words, if we put a lamp at one end of such a row of Rubik's cubes, it will take 250 years for the light to shine on the other end. If a diligent player wants to try all the combinations, even if he doesn't eat, drink or sleep, it will take him 65.438+050 billion years to get them (in contrast, our universe is currently less than 65.438+040 billion years old). Compared with such combined figures, the adjectives of "thousands", "hundreds of millions" and "billions" commonly used by advertisers on weekdays have become rare modesty. We can safely say that even if a person starts playing the Rubik's Cube from BIGBANG, there is almost no hope to restore a Rubik's Cube whose color is disturbed.
2. Rubik's cube and "magic number"
There are many players in the Rubik's Cube, so it is natural to compete with each other. From 198 1, Rubik's cube lovers began to hold worldwide Rubik's cube competitions, thus creating their own world records. This record is constantly being refreshed. As of the writing of this article, the fastest record of restoring the Rubik's Cube-as we mentioned at the beginning of this article-has reached an astonishing 7.08 seconds. Of course, a single recovery record is accidental. In order to reduce this contingency, since 2003, the champion of the Rubik's Cube competition has been determined by the average score of repeated recycling [Note 3]. At present, the world record for this average score is 1 1.28 seconds. The appearance of these records shows that although the Rubik's Cube has astronomical color combinations, as long as you master the tricks, there are not many rotations required to restore any combination.
So, how many times do you need to rotate at least to ensure that no matter what color combination can be restored [Note 4]? This problem has aroused the interest of many people, especially mathematicians. The minimum number of rotations needed to restore any combination is dubbed by mathematicians as the "magic number", and the Rubik's cube, the darling of the toy industry, has invaded the academic world at one fell swoop because of this "magic number".
To study the "magic number", of course, we must first study the reduction method of the Rubik's cube. In the process of playing the Rubik's Cube, people have long known that it is easy to restore any given color combination, which has been proved by the excellent records of countless players. The reduction method used by Rubik's cube players, although easy to master by human brain, does not have the least number of rotations, so it is not helpful to find the "magic number". Finding the method with the least number of rotations is a difficult mathematical problem. Of course, this problem is not difficult for mathematicians. As early as the mid-1990s, people had a practical algorithm, and the minimum number of rotations to restore a given color combination could be found in about fifteen minutes on average. Theoretically speaking, if someone can find such a minimum number of laps for each color combination, then the maximum number of laps is undoubtedly the "magic number". But unfortunately, the huge number of 432.5 billion has become a stumbling block for people to peek at the "number of gods." If the algorithm mentioned above is adopted, even if 1 100 million machines are used at the same time, it will take1100 million years to complete.
It seems that brute force doesn't work, so mathematicians turn to their old job: mathematics. From a mathematical point of view, although the color combination of the Rubik's cube is ever-changing, it is actually produced by a series of basic operations (namely rotation), and those operations also have several very simple characteristics. For example, any operation has an opposite operation (for example, the operation opposite to clockwise rotation is counterclockwise rotation). For such operations, mathematicians have a very effective tool in their arsenal to deal with them. This tool is called group theory, which appeared more than 40 years ago when the Rubik's Cube appeared/kloc-0. It is said that German mathematician D Hilbert once said that the key to learning group theory is to choose a good example. Since the advent of the Rubik's Cube, mathematicians have written several books on group theory through it. Therefore, although the Rubik's Cube has not become a teaching tool of space geometry, it can be used as a "good example" for learning group theory to some extent.
For the study of Rubik's cube, group theory has a very important advantage, that is, it can make full use of the symmetry of Rubik's cube. When we mention the huge figure of 432.5 billion, there is actually an omission, that is, the symmetry of the Rubik's Cube as a cube is not considered. As a result, many of the 432.5 billion color combinations are exactly the same, just from different angles (such as making different faces face up). Therefore, the daunting figure of 432.5 billion is actually "pork with water". So, what percentage of this "pork" is "water"? Say it to scare everyone: it accounts for nearly 99%! In other words, mathematicians can reduce the color combination of the Rubik's cube by two orders of magnitude only through symmetry [Note 5].
But reducing two orders of magnitude is not enough to find the "magic number", because it only reduces the aforementioned 10 million years to10 million years. For solving a mathematical problem, 1 00000 years is obviously too long, and we don't expect anyone to use1100 million computers to count the number of gods. Mathematicians are clever, but they are not necessarily rich in other ways. Maybe what they can really use is the machine on their desk. Therefore, in order to find the "number of gods", people need to find more ingenious ideas. Fortunately, the power of group theory tools is far from being used to analyze something as obvious as the symmetry of a cube. With its help, new ideas soon appeared.
3. Looking for "the number of God"
1992, the German mathematician H. Kochiemba put forward a new idea to find a way to restore the Rubik's Cube. He found that some basic rotation patterns of the Rubik's Cube can form their own series, and nearly 20 billion color combinations can be formed through this rotation [Note 6]. Using these 20 billion combinations, Ke Xianba decomposed the reduction of the Rubik's Cube into two steps: the first step is to convert any color combination into one of the 20 billion combinations, and the second step is to restore the 20 billion combinations. If the restoration of the Rubik's Cube is compared to a boat sailing to a fixed destination in the sea of Wang Yang, then the 20 billion color combinations proposed by Ke Xianba are like a special water area-a special water area 20 billion times larger than that fixed location. The two steps he proposed are like letting the ship sail to that special water area first, and then sail to that fixed destination from there. Finding a huge special water area in the sea of Wang Yang is obviously much easier than finding that small destination directly, which is the advantage of Keshanba's new idea.
Even so, it is not easy to estimate the number of gods by Cochaba's method. Especially for fast calculation, it is best to store the minimum number of rotations to recover 20 billion color combinations (this is equivalent to the map of that "special water area") in the memory of the computer, which requires about 300 megabytes of memory. 300 trillion is not a big number today, but in the year when Ke Xianba put forward new ideas, the memory of ordinary machines was far less than one tenth of it. So it was not until three years later that someone gave the first estimation result by Kochenba's method. His name is M. Reid, and he is a mathematician in university of central florida, USA. In 1995, Reid found that any color combination of the Rubik's Cube can become one of the 20 billion combinations of Cochrane Barna after at most 12 rotations. After at most 18 revolutions, any one of those 20 billion combinations can be recovered. This shows that any color combination of the Rubik's Cube can be restored by rotating 12+ 18=30 times at most.
After getting the above results, Reid quickly improved his calculation, reducing the results from 30 to 29, which shows that the "number of gods" will not exceed 29. Since then, with the development of computer technology, mathematicians have further improved the results of Reid, but the progress is not rapid. It was not until 1 1 years later in 2006 that Silviu Radu, a doctoral student at the Institute of Symbolic Computing at johannes kepler University, pushed the result to 27. The following year, in 2007, computer scientists D. Kunkle and G. Cooperman of Northeastern University pushed the result to 26. Their work uses a parallel computing system, which uses 7 million megabytes of memory and consumes 8,000 hours of computing time (equivalent to 24 hours of uninterrupted computing in the past year).
These calculations show that the number of gods will not exceed 26. However, the greatest advantage of all these calculations-that is, using the "special water area" of Keshan Dam-is also their fatal weakness, because the restoration methods they give must pass through that special water area. But in fact, many of the best restoration methods in TINT don't pass through that special water area at all. For example, any ship that is close to its destination, but not in special waters, obviously does not need to deliberately bypass that special waters before going to its destination, like the direct charter flights in mainland Taiwan Province Province. Therefore, the restoration method obtained by the way of thinking of Ke Xianba is not necessarily the best, and the estimation of "the number of gods" is also likely to be overestimated.
However, what if the special waters of Keshenba are not introduced and the calculation is too large? Mathematicians decided to take a compromise, that is, to expand the "area" of that special water area, because the larger the special water area, the greater the possibility that the best recovery path just passes through it (of course, the amount of calculation will increase accordingly). In 2008, Rokic, a computer expert who has studied 15 years, used an ingenious method equivalent to expanding the special waters of Koshanba by thousands of times, and launched four fierce attacks on the number of gods in a few months, reducing its estimated value from 25 to 22. As of this writing, this is the best result in the world. Rokic's calculation is supported by Sony Pictures Imageworks, a film special effects production company, which has produced special effects for famous films such as Spider-Man and provided Rokic with computer resources equivalent to 50 years of uninterrupted calculation.
So, now we know that the number of gods must not exceed 22. However, although the special waters in Rokic are very large, there are still many color combinations. The best way to recover is not to pass through that special water area. So the "number of gods" is likely to be less than 22. So, how much is it? Although people can't know for sure, there are indications that it is very likely to be 20. This is because in all the efforts of the past years, people have never encountered any color combination that can only be restored after more than 20 flips-including about 4 trillion color combinations directly calculated by Rokic. This shows that the "number of gods" is probably not more than 20. On the other hand, people have found tens of thousands of color combinations, which must be restored after 20 turns. It can be seen that the "number of gods" cannot be less than 20. Combining these two aspects, mathematicians generally believe that the true value of "the number of gods" is 20. Of course, "God" may be subtle, and none of us can guarantee whether it will surprise us in a corner. The only thing we have reason to believe is that the mysterious "magic number" interwoven by this game and mathematics is not too far away from the day it came out.
To annotate ...
1. The Rubik's Cube was named by rubik himself, and the Rubik's Cube was named by American toy company Ideal Toys. In western countries, the name Rubik's Cube is more popular, while in China, the name Rubik's Cube is more popular. In addition, readers should be reminded that there are many kinds of Rubik's Cube, and the 3×3×3 Rubik's Cube introduced in this paper is only the most common one.
2. The specific calculation is as follows: There are 8 vertices in the small cube that makes up the Rubik's Cube, and there are 8 between them! Species replacement; Each of these vertices has 3 colors and 37 combinations of orientations (due to structural limitations, only 7 vertices of the Rubik's Cube can have independent orientations). Similarly, the Rubik's Cube has 12 cubes with edges and 12 cubes in the middle! /2 permutations (divided by 2 because once the vertices of the Rubik's cube are determined, only half of the edge permutations are possible); These faces each have two colors, and their orientations are 2 1 1 combinations (due to structural limitations, only1/faces in the Rubik's Cube can have independent orientations). So the total number of color combinations of the Rubik's Cube is 8! ×37× 12! × 211/2 = 4325200327489856000, which is about 432.5 billion. In addition, it is worth mentioning that if we allow the Rubik's Cube to be dismantled and reorganized, the aforementioned structural restrictions will no longer exist, and the number of color combinations will be as high as 519 billion. However, the increase in the number of combinations does not mean that it is more difficult to recover. In fact, the limitation of Rubik's cube structure on the number of combinations is the main reason why it is difficult to restore the Rubik's cube. For example, under the exchange of adjacent letters, there are about 40 billion combinations of 26 English letters, far more than the number of combinations of Rubik's cube colors, but it is very simple to restore the randomly arranged 26 English letters from A to Z to their original arrangement through the exchange of adjacent letters.
3. To be exact, take the average of the three scores among the five attempts.
In order to make this question meaningful, of course, we must first define what is rotation. In the mathematical research of the Rubik's Cube, rotation refers to rotating any side of the Rubik's Cube (including nine small squares) clockwise or counterclockwise by 90 or180. For each face, there are three kinds of such rotation (please think about it, why not four kinds? )。 Because the Rubik's Cube has six faces, there are 18 basic rotation modes.
5. To be exact, there are 18 basic rotation modes, and the obtained color combination * * * is 8! ×8! ×4! /2 (about 654.38+09.5 billion).