Fun math with colored cubes

Mind games, like puzzles, discipline thinking, form a thinking culture, the value of which can hardly be overestimated, develop imagination, moreover, a person acquires all these personal improvements in the most exciting form - in the form of a game.

---

Quite a bit of history

Puzzle «Instant Insanity» ( Instant Insanity ), arguably one of the most sought to illustrate the applicability of the theory of graphs in solving problems of this type it. In any case, on youtube you will find many examples of such its use by a considerable number of mathematics teachers. It is difficult to say how long this puzzle itself has been known for a long time, but it was popular enough to attract the attention of one of the members of the student mathematical “Archimedean Society” of Cambridge University, hiding behind the pseudonym “F. De Carteblanche "(his real name, according to the famous collector and puzzle chronologist Robert Stegman / Rob Stegmann- Cedric AB Smith), and be noted in the publication of the periodical Eureka No. 9 (1947) of The Archimedeans. After the publication of an elegant solution by F. De Carteblanche, and to this day, mathematicians find reasons to return from time to time to this problem, and to the class of problems arising from it.

The puzzle itself consists of 4 cubes painted in 4 colors, which are proposed to be arranged in a row so that on each side of the resulting prism / pyramid all 4 colors are presented. For brevity and convenience, they often use the designation for the pyramid "1x4x4".

The commercial name Instant Insanity stuck to this puzzle in the late 1960s. Her other well-known trade names are Tantaliser, Crazy Cubes, and there are a dozen others that are less known, but fairly common, and there are quite a few clones representing her modifications.

In 1969, the journal Science and Life, issue 2, a short note about this puzzle appeared from Bronislav Ivanovich Koltov, a well-known popularizer of science, a great lover of puzzles and the author of numerous books on puzzles and entertaining mathematical problems. Later, at least two toy factories in the USSR, in Odessa and Kirov (PO Vyatka) released this puzzle.


Fig. 1. The puzzle, produced in the 1970s by Vyatka software, Kirov

The puzzle is really very exciting, since all the features that make this kind of game popular are present in it: it is moderately complex and has an attractive design - it can be solved in no more than 8 steps, and can be arbitrarily compact.

Puzzle on photos stored in my more than 40 years, is called "a puzzle with one solution" in the English-language literature (sometimes even used the expression «simple solution / simple solution "). This name may not seem the most obvious, and I will explain its origin below.

I will definitely give here a graphic solution to the puzzle, but earlier I would like to introduce some definitions intended to simplify my further presentation of the material.

For what, actually?

How many sets of four cubes exist that have a “one solution”? - I have never met attempts to carry out such a calculation, although it is extremely simple, but there were indications of patents that protect the rights of owners, including both the trade name of the game and the combination of colored cubes. The idea to make such a calculation came immediately after the idea of ​​writing a computer version of the puzzle. It may seem that the task of finding all possible combinations of cubes with “one solution” is too narrow, specific, but the approach I used to search for an array of four-element assemblies can be very convenient for describing and formalizing other problems with cubes, and for solving these problems.

Actually, the purpose of this article, in addition to entertaining the reader with examples of space-color transformations of four-element cube assemblies, is also to offer the community enthusiastically discussing puzzles like the one in question, a simple, concise and understandable language for describing the states of such like a cube of an object, instead of the voluminous and painful “scan number 2, rotate around the Z axis, in the right-handed system ..”, etc. Anyone who has to, at least occasionally, bore his imagination with reading is like x phrases believe annoyed with the lack of a more concise and expressive techniques describe the state of the object under discussion. Particularly outraged by the lengthy descriptions of the states of objects of programmers, the mental culture of which is sophisticated by the habit of formalization, logic and algorithmization.

Let us try to formalize a few simple observations on cubes.

Some notation and terminology conventions

For ease of use in the future, we index the faces of the cube as follows (see Fig. 2 ):
0 - the bottom face, 1 - the front face, 2 - the top side, 3 - the back, 4 - the left side, 5 - the right side.


Fig. 2. Unfolding cubes

Let us describe all the possible rotations of the cube in its local right-handed coordinate system , in which we position the cube so that the centers of the cubes in a row are on the Z axis and the X axis is directed upwards.


Fig. 3. Indexed turns. The

letter denotes a rotation of 90 degrees around the corresponding axis, a minus sign in front of it indicates that the rotation is carried out by -90 degrees.

In this form of recording, it is easy to fix the spatial position of the cube, he would not have performed an arbitrarily complex sequence of rotations: for example, you can obtain a sequence of indices for rotations (X, X) by rearranging the initial position of the cube indices in the corresponding column “indexes” of the table.

A convenient form of recording is by arranging the convertible indices from top to bottom, from the initial position to the new spatial movement of the cube.

Graphical solution

Why is it “unique” if the cubes, in strict accordance with the requirements of the puzzle, can obviously form several different spatial combinations?


Fig. 4. Assembled puzzle

Because the “right” puzzle has the only graphical solution !
To repeat the decision of F. De Carteblanche, we need a brief excursion into graph theory, and the knowledge we need is so insignificant that people who have not heard so far about this area of ​​mathematics will hardly feel the new knowledge as "baggage".

Each cube in the graph representation can be written as a combination of its opposite sides - for example, take the cube with number 27 ( Fig. 2 ), its record looks like this: RY / RB / GY.

• The order of writing the faces and the colors themselves in the faces does not matter, which directly indicates the invariance of the permutations of the faces of an individual cube to the state of the puzzle solution. This fact does not seem to be the most expected, therefore somewhat surprising: changing, for example, two opposite faces of a cube twice, we get the same cube, but in a different spatial position, however changing faces once or three times, we have a completely different cube, however it In combination with the previous three set cubes, it again forms a puzzle that has a “simple solution." We “liven up” this observation by taking an index record: we choose cubes with numbers 27, 16, 10, 5. from the table of the development of cubes, since the faces 4 and 5 of the cube are lateral (in accordance with the agreement ), it is obvious that the development of these cubes is shown on Fig. 2in the assembly (decision) position, having adopted the digital designation “red - 0, yellow - 1, blue - 2, green - 3”, we write: we will interchange the opposite faces of the first cube, except for its side faces hidden from the observer: [120031] - but it is the same cube, only at position 230145 (Z, Z); swap faces with indices 0 and 2: [100231] - the cube at position 210354 (Y, Y) will take its former place in the assembly, except that the side faces hidden from the observer have swapped; swapping the faces with indices 1 and 3, we get a cube [021031], which after turning 032154 (X, X) will also become [001213], like the previous one. The assembly as a whole, meanwhile, as soon as we return the “modified” cube to its previous position, continues to remain “solved”.
  
  [001231] - кубик 27
[112301] - кубик 16
[233011] - кубик 10
[320111] - кубик 5
Именно эта сборка вращается на Рис. 4.

  
• Let's pay attention to the turns for numbers 4, 7, 8, 13, 16, 20, 22 from the Indexed Turns Table (Fig. 3) - these are the turns in which the side faces of the cubes do not take part, and all these turns applied to all assembly blocks at the same time, do not break the "solution" of the puzzle. Those. spatially different combinations of cubes in which a puzzle solution can be observed actually ... 8.
  

However, back to the graphs . It is enough for us to imagine the graph as a certain set of vertices (nodes, nodes) that are in interconnected relations or, more simply, connected by edges (ties, edges). The vertices , in our case, we will assume the colors or the colored faces themselves, and as links the physical edge of the cube is only relevant in the sense of indicating that the two colors selected on the graph form a pair in the particular implementation of the cube under consideration. If an edge closes at the same vertex , it is customary to call a graph with such a construction a pseudograph, and the corresponding edge is a loop.

Let us solve the puzzle in Fig. 5: in a lowercase entry, the cubes that make it up look like YG / RB / RY, RY / GY / BY, GB / RG / YY, GR / YY / YB . Below each cube we place its representation in the form of vertices and edges of the graph corresponding to it , after which we combine all four pseudographs into a single graphic design.

Actually, it is precisely on this intricacy that we have to ponder in order to solve the puzzle:

• inside this combined multigraph, it is necessary to distinguish two separate subgraphs (two paths), each of which passes only once through all four color vertices, using each of the 4 edges numbered from 1 to 4-X. Moreover, each vertex should have only two outgoing edges or only both ends of the loop emanating from it . One subgraph will represent a series of cubes in the "puzzle solution" position facing the observer, the second - a series of cubes in the "top" position. Obviously, any edge cannot be used in both subgraphs.because cannot represent the frontal and upper parts of the assembled prism at the same time.

Fig. 5. Graphic solution to the puzzle

It turns out that you can divide a multigraph into two subgraphs , observing all these conditions, in only one way. From here, in fact, came the steady expression "the only solution."
If each of the cubes in its received arrangement (indexed entry in Fig. 5) is rotated in the XXZ sequence (103254), then in this assembly we will recognize the familiar cubes 27, 16, 10, 5 in this assembly.

Of course, there are sets of cubes of 4- e, who do not have a single solution, like those that have too many solutions to make combining them seem entertaining.
In general, it continues to seem to me that I continue to exploit the borrowed speech stamp - the “only solution” is not the most successful way, but maybe someone will offer a concise and accurate definition for assemblies with the minimum possible number of combinations required by the condition of the task . Personally, for me, any combination of cubes that allows a larger number of combinations for assembly than the minimum possible causes some difficulty in classifying it.


Fig. 6. Example build with 24 solutions

A bit about complexity

In all the texts I reviewed on this puzzle (Instant Insanity, Tantalizer), research on its complexity came down to calculating the total number of combinations that can fit the cubes in the pyramid, or calculating the probability of accidentally finding a solution among possible combinations of cubes. Moreover, these calculations are sometimes made in such an amazing way that you just get lost trying to get into the idea of ​​the author: for example, according to the author (or authors) of the Wikipedia article, the probability of accidentally finding the solution to the puzzle is 13824. This figure was the result of the author’s insight into the fact that the order of the cubes in the pyramid does not matter, and therefore generates new 24 solutions, and it’s good to divide 24x24x24x24 into these 24, for finding the probability ... And this blunder spreads across the network through the efforts of the pollinators of the Internet space that do not know doubts.

Among 331776 possible combinations formed by cubes (naturally, without trying to change their order in the pyramid) there can be only 8 solutions, which will give for probability a figure slightly higher than calculated by the authors of the Wikipedia article - 41472. And this figure is also found in the same article, but in terms of the number of unique or essential configurations for finding a solution: it’s enough to fix the first cube on one of the faces of each of the three pairs of opposite faces, then the number of options for significant combinations will be 3x 24x24x24. This figure coincides with the probability just because fixing the first cube, we will get the only solution in the course of enumerating possible combinations.

Meanwhile, using the form for recording turns in indexed faces, it is easy to show that the solution to the puzzle can be found in no more than 8 steps.

We carefully consider the table in Fig. 3: among all the unique spatial arrangements in which each of the cubes can be located, there are 6 arrangements consisting of 3 rotations by 90 degrees, and 11 consisting of 2 rotations.

It seems quite logical if, to find the greatest number of steps required to solve the puzzle, we take a combination of cubes in the position to solve the puzzle and try, changing the spatial arrangement of each cube, to simulate the combination that is as far as possible from the solution- i.e. “Equidistant” from the combinations that “assembly” could go into if all the cubes were simultaneously applied turns 4, 7, 8, 13, 16, 20, 22 from the table Fig. 3.

Let's start with the study of the consequences of applying 3-fold turns (numbers 19 to 24 in the table) to each of the dice: total combinations of 6 3-step turns, as applied to our case, can be 15:
<19,20,21,22>, <19,20,21,23>, <19,20,21,24>, <19,20,22,23>, <19,20,22,24>, <19,20,23,24>, <19,21,22,23>, <19,21,22,24>, <19,21,23,24>, <19,22,23,24>, <20,21,22,23>, <20,21,22,24>, <20,21,23,24>, <20,22,23,24>, <21,22,23,24>.

The order of the cubes in the assembly does not matter for the solution; therefore, the rotation order in these combinations is also not significant.
Any of the turns at numbers 20 and 22 immediately leads the cube to which this turn was applied to the position occupied by this cube in one of the 8 puzzle solutions (see above). If we consider a space-fixed (not requiring further rotations) cube to which rotation 20 was applied, then any cube located in one of 5 other 3-step positions can be moved to position 20 in two step: turn 11 (19 + 11 → 20) to position 19, apply 21 + 14 → 20, 22 + 16 → 20, 23 + 12 → 20, 24 + 15 → 20 (just rearrange the indices of the faces of the initial position in accordance with directions to add rotation): In case we fix a cube to which we applied rotation number 22, possible transitions For other cubes, they may look like this:
19+11: 21+14: 22+16: 23+12: 24+15:
435102 534120 321054 240513 250431
341520 351402 230145 425031 524013
------ ------ ------ ------ ------
103254 103254 103254 103254 103254


19 + 18 → 22, 20 + 16 → 22, 21 + 9 → 22, 23 + 10 → 22, 24 + 17 → 22.

In total, to achieve a solution, it took us only six actions .

Only one of the 15 3-step combinations contains neither the 20th turn from the rotation table, nor the 22nd. - This is a set of <19,21,23,24>. Perhaps the duration of the steps to the solution, in this spatial arrangement, will be different: we
turn the cube located in position 19 (X, X, Y) to position 16 (Z, Z): 19 + 1 (Y) → 16 (we did only one turn by turning the cube 90 degrees around the Y axis); for the remaining three cubes, we also need only one operation per cube to translate it into position 16 (Z, Z):
19 + 3 → 18, 21 + 6 → 18, 23 + 5 → 18, 24 + 2 → 18 . - In this case, it took only 4 turnsto go to the position of the collected solution.

It remains to take a close look at what the 2-step rotary combinations promise us, in which we immediately abandon the turns at numbers 8, 13 and 16, since any of them fixes one of the cubes in the solution position, and take, for example, for the purposes of our analysis sequence <9,10,11,12> - to translate this sequence into any of the 8 positions of the solution (see above) is possible as a result of the following operations, easily found using the table:

9 + 23 (X, Y, Y) → 4, 10 + 6 (-Y) → 4, 11 + 5 (-X) → 4, 12 + 19 (X, X, Y) → 4 or
9 + 5 (-X) → 7, 10 + 21 ( X, X, -Z) → 7, 11 + 23 (X, Y, Y) → 7, 12 + 3 (Y) → 7 or
9 + 12 (X, -Z) → 8, 10 + 9 (X, Y) → 8 , 11 + 10 (X, Z) → 8, 12 + 11 (X, -Y) → 8 or
9 + 10 (X, Z) → 13, 10 + 14 (Y, Z) → 13, 11 + 12 ( X, -Z) → 13, 12 + 18 (-X, -Y) → 13 or
9 + 15 (Y, -X) → 16, 10 + 11 (X, -Y) → 16, 11 + 17 (Z, -Y) → 16, 12 + 9 (X, Y) → 16 or
9 + 2 (X) → 20, 10 + 1 (Y) → 20, 11 + 24 (X, Z, Z) → 20, 12 + 21 (X, X, -Y) → 20 or
9 + 24 (X, Z, Z) → 22, 10 + 19 (X, X, Y) → 22, 11 + 2 (X) → 22, 12 + 6 (-Y) → 22 or 
return to the initial position by reverse turns, - in any of these cases , the sum of all the turns made over the cubes is 8 .

So how many are there?

In the mobile version of my puzzle, I didn’t want some combination of cubes to become familiar and boring to the player, and I did not hope that 24 options for possible repainting the set of cubes could mislead inquisitive minds for a long time.
In addition, it’s just interesting to yourself: how many unique combinations of four-colored cubes of 4 exist, which are combinations with a “one solution” and not a “repainting” of ourselves?

You can simply take all 68 possible colorings of cubes (it is precisely this number of colorings in 4 colors that indicates the Burnside lemma) and a simple exhaustive search “for 4 out of 68” to find all these combinations (simultaneously checking them for “uniqueness” and “repainting”) - this method, however, does not differ in grace and promises to be very costly in time of machine calculation ( more than 30 times from what I accepted, as comparisons subsequently showed). It seemed to me optimal to build immediately possible combinations of cubes on the 4th. In addition, a careful look at the index form of recording the spatial positions of the cube (Table, Fig. 3) allows us to make some optimization of this sorting:

• recording through indices makes it easy to determine which color models of cube coloring cannot be found in assemblies with the “only” (minimum set of matching puzzle combinations) solution: 12 dice used by Rob Stegmann in his set of 56 are just not suitable for such assemblies , therefore, groups 5 and 6, in his classification, did not appear anywhere in “simple” solutions .
• Having sifted out “unsuitable” color models even before the stage of modeling the assemblies themselves with 4 cubes each, it is possible to significantly reduce the time for sorting combinations of cubes for assemblies.
• These filters are appropriate to use, as in puzzles with three-color coloring of cubes (there are some, but we do not consider them here), and in the case of four-color coloring.

Fig. 7. Invalid sequences

It is easy to see from Fig. 7 that cubes having equally colored opposite or adjacent non-lateral faces, as well as cubes whose side edge painting repeats the filling of any of the non-side faces, cannot be present in assemblies with “one solution” because give rise to new, additional solutions.

It should be noted that quite “fit” cubes easily create assemblies that do not meet the criterion of “uniqueness of solution”: for example, the combination in Fig. 6, in which synchronous placement of assembly cubes in any of its 24 possible spatial positions leaves the assembly “solved” , formed just by “fit” cubes with numbers 25, 17, 15, 23.

The “not repainted” assemblies with the “one solution” gained 1073 during the time slightly exceeding the minute of my computer’s work, and these 46 cubes, of which all these assemblies are combined, are shown in Fig. 2. I was somewhat discouraged that in this set there were no 10 more cubes, the coloring of which I was supposed to see, because they fully met the requirements I formulated. Then I added them first to the array of "my" cubes and drove away the usual " evil brute force""- as a result, the generated array of assemblies continued to be the number in 1073, only the set of cubes used for these assemblies changed: four cubes from the" new "ones were added to my set, but they replaced the two cubes that were previously in the set ... The same result was obtained for an array of 68 cubes generated solely from the principle of uniqueness of coloring
Magic number 1073.

Repainting

All 1073 assemblies I found are unique, none of them can be turned into any other by repainting and turning the cubes. Moreover, any other assemblies combined from the 46 cubes shown in the table will be only isomorphic derivatives from these previously counted 1,073 assemblies.

How this happens can be seen from the following example.

Let's create an assembly with “one solution” from the cubes we have (all scans from Fig. 2 ) - among the 1073 assemblies of the final sample, this set is absent, but this is a completely “playable”, “one-solve puzzle”. The assembly is shown in the solution position. We repaint its faces as follows: yellow - in blue, blue - in yellow, otherwise 1 - 2, 2 - 1:

[001233] - кубик 29
[123300] - кубик 30
[230121] - кубик 17 в положении XX-Y (534120)
[312000] - кубик 32



[002133] - и повернем на XXZ (103254)] : [001233] - кубик 29
[213300] - и повернем на XXZ (103254)] : [123300] - кубик 30
[130212] - и повернем на XXZ (103254)] : [312021] - кубик 46
[321000] - и повернем на XXZ (103254)] : [230100] - кубик 31

That is, in this example, it was not possible to create a new entity by repainting (any assemblies formed from the set shown in Fig. 2 are already considered among the existing 1073's) - the assembly that we repainted is not included in the final set of 1073 unique puzzles, but can be composed of those 46 dice that served as the material for all puzzles. However, such an assembly will be only an example of isomorphism, since by an ordinary change of colors, it turns into another assembly (from other cubes) already taken into account by us. Nevertheless, “repainting” creates a considerable number of “unrecognizable” looking puzzles. On R. Stegmann's website there are enough examples of isomorphically homogeneous Instant Insanity puzzles.

“What follows from this?”

It will be extremely annoying if the culture of intellectual leisure gives way to a culture of contemplative leisure. I hope that their peaceful coexistence is possible.