Invertibility 101

Operations or actions that mathematicians study, that you do while playing games, and those that happen in real life can be split into invertible (reversible) and non-invertible (non-reversible). In real life, putting your socks on is an invertible operation, since you can take them off. Opening a can is non-invertible, you cannot easily close it and return back to the original state. In games, operations in Rubik's Cube and the 15 Puzzle are invertible. If you rotate a face of the Rubik's Cube, rotating it back bring the Cube to the previous state. Sliding a square into the empty slot of the 15 Puzzle is invertible just by sliding the square back. In Tetris,  2048 and thousands of other games either all or most moves are not invertible. Ringiana and Ringsanity are on the side of the Rubik's Cube and the 15 Puzzle in this divide.

In real life it gets more complicated--is walking a mile invertible? Roughly yes, just walk a mile back. But we spent time and a bit of energy walking that mile, and then going back, and the time spent does not come back, except in occasional novels and movies. In real life invertibility is dampened by lost time, resources and opportunity costs, and requires a more refined approach to define and deal with.

Here I want to discuss invertibility in mathematics and in the Ringiana and Ringsanity games. We say that an operation A is invertible if there is an operation B so that doing A then B does not change the original state. We write AB for the operation of doing A then B (for simplicity I'm reversing common math convention that BA denotes doing A then B). The operation of doing nothing, not changing the original state, is called identity and denoted Id (also denoted I, id, 1, e). We write the invertibility condition, that doing A then B is the same as doing nothing as 

            AB = Id 

It turns out not to be quite enough. We should throw in the dual condition, that first doing B than A in the identity (no change in state) as well: 

 BA = Id  

If both properties hold, we say that A and B are invertible and B is the inverse of A. For example, A can the operation 

Take my socks off 

And B the operation

Put my socks on 

Both compositions AB and BA are identities, returning us to the original state before the operations started. There is an additional complication that, at least conventionally, we cannot apply A to any state, only to the state when we are wearing the socks. Likewise for B, which only applies when the socks are off. This can be drawn, with states shown as boxes and actions as arrows. 

A mathematical structure of this kind is called a groupoid. A groupoid has some states and has actions taking us between the states, with every action invertible. 

An additional and extremely useful simplification happens when the same invertible operation can be applied in any state. In the Rubik's Cube game, A could the operation: 

Rotate the face with the central square red 90 degrees clockwise. 

Its inverse B is the operation 

Rotate the face with the central square red 90 degrees anticlockwise. 

Operations A and B are defined no matter how the pieces of the cube have been arranged, and the two operations are inverses of each other.

We write B=A^-1 to denote that B is the inverse of A. This relation is equivalent to A being the inverse of B: 

A=B^-1

Mathematical notion of a group axiomatizes the structure of a collection of invertible operations. A group can be generated by some invertible operations X, Y, Z, ... such that each can be applied to any state of the system. A group G consist of arbitrary finite products of generators X, Y, Z, ... and their inverses. For instance, XY^-1XZ is in the group G if X, Y, Z are in G. It denotes the composition of first doing X, then the inverse of Y, followed by X, followed by Z. Any group contains the identity Id, which is also XX^-1 for any generator X of the group. 

Puzzle time: Can you figure out what is the inverse Id^-1 of the identity? That is, how does one invert doing nothing? 

 Group theory studies groups, collections of invertible transformations (also called symmetries) that are closed under composition (going from X and Y to XY) and under taking inverses (going from X to X^-1). Group theory a big and key subject in mathematics. Books have been written even about particular groups, including the Rubik's Cube Group. That group can be generated by just six operations, rotating one of the six faces of the cube by 90 degrees clockwise. It's a very large but finite group with 2125922464947725402112000 elements. 

Puzzle time: Why do we include both conditions 

AB = Id    and   BA = Id

in our definition of invertibility of A? Why just requiring 

 AB = Id  

is not enough? Can you think of examples from (a) math, (b) games, (c) real life?  

We next look at invertibility in Ringiana (Android, iPhone) and Ringsanity games.  

Spoiler alert and disclaimer!

It's more fun to play these games on your own first and discover invertibility of basic moves for yourself.

There are eight moves in Ringsanity, and in the previous post we labelled them e1 through e8, starting from the first quadrant and going counterclockwise: 

 

 Move e1 expands the first quadrant clockwise and squishes quadrants III and IV together into III. Its inverse is 

Please reread Spoiler Alert above!

the move that expands quadrant III counterclockwise and squishes quadrants I and IV together into a single quadrant, 

and that move is e6. Move e1 followed by move e6 is the same as doing nothing. Move e6 followed by e1 is the same as doing nothing: 

Our shorthand for writing the move e1 followed by e6 is 

e1e6 or e16. Extending this notation, it's natural for us to write identity as e, and our invertibility formula takes the form 

   e16 = e     or     e16 = Id

Let's not forget the other way, e6 then e1 is identity:

e61 = Id 

Since we write, for instance, e463 to denote move e4, followed by e6, then e3, it might be natural to use e for identity, since that's just means no moves (doing nothing). This turns out to be a good convention for Ringsanity, but not for Ringiana, which admits additional moves. For the most part, we'll stick with Id for identity.

Puzzle time: Pair up the remaining six Ringsanity moves into three pairs of mutually-inverse moves before reading the rest of the post.

The answer is in the table below. In the left column there are moves e1 through e4. The right column lists their inverses. 

The pairs are (e1,e6), (e2,e5), (e3,e8), (e4,e7). 

Each Ringsanity move expands a quadrant into an adjacent quadrant. Peer over the adjacent quadrant--next to it on the other side hides the inverse of the move. e1 expands quadrant I into quadrant IV. The other move that expands into quadrant IV is e6, exactly the inverse of e1. 

Moves e2, e5 both expand into quadrant II:

 

Moves e3, e8 expand into quadrant I: 

 and moves e4, e7--into quadrant III:

 

 In each pair of inverse moves, one expands clockwise, the other counterclockwise. 

Ringiana game has four more moves. Compared to e1-e8, these moves are non-agressive and simply transpose adjacent quadrants. We denote these moves s1, s2, s3, s4, starting from the East move (transpose quadrants I and IV) and going counterclockwise. 

Move s1 (East) transposes arcs I and IV. 

Move s2 (North) transposes arcs I and II. 

Move s3 (West) transposes arcs II and III. 

Move s4 (South) transposes arcs III and IV. 

What is the inverse of s1? It's just s1. Doing s1 twice in a row brings us back to the original state. Likewise for the remaining transpositions: the inverse of s2 is s2, of s3 is s3, of s4 is s4: 

 We have 

  s1s1 =  Id,   s2s2 = Id,   s3s3 = Id,  s4s4 = Id

To summarize, Ringsanity has 8 generating moves, all invertible. They pair up into four mutually-inverse pairs. 

Ringiana has 8 (expand) + 4 (swap) = 12 generating moves, with four mutually-inverse pairs of the Expand-Shrink moves and four Swap moves that are their own inverses.

 

Making sense out of chaos: ordering expand-shrink moves

To understand Ringiana (for Android and iPhone)  and Ringsanity (iPhone)  we are going to develop some notations for moves that occur in these games. The most interesting moves, the expand-shrink moves, are common to both games. Every Ringsanity move is an expand-shrink, while Ringiana also has swap or transposition  moves, which exchange two adjacent arcs. 

We  will call expand-shrink moves ES-moves, for lack of a good verb to describe this novel action. An ES-move expands a quarter of the ring into two, either clockwise or counterclockwise, and shrinks the two quarters into one. 

The two shrinking quarters are located along the ring either clockwise or anticlockwise after the expanding quarter. 

Here is a video with a bunch of ES-moves in Ringsanity 

 In Ringsanity only the outer ring moves, while colors of the inner disk remain static. The goal, recall, is to match the colors of the outer ring with those of the inner disk. In Ringiana for iPhone Sergey Nemirovsky (who did almost all the coding) composed ES-moves with radial shrinking and expansion for fancier animations.

 Nikolay Gromov coded Ringiana for Android in OpenGL with a distinctly 3D appearance. ES-moves are still there, but their animations look different. By the way, fancy programming in OpenGL and for Android is not Nikolay's main work. He is a professor of theoretical physics and writes fancy papers such as Quark-anti-quark potential in 4D SYM.

Having looked at implementations of ES-moves, we return to their classification.  There is a total of 8 moves in Ringsanity:  the ring has four quarters, and each quarter can be expanded clockwise or anticlockwise. A programmer would label these moves 0 through 7. As a mathematician, I start with 1 and will label them 1 through 8, adding prefix e  and denoting the moves e1, e2, e3, ..., e8. 

When a mathematician decides to introduce some order in the two-dimensional plane, she often sets up a coordinate system. Let's do that, placing the center of coordinates at the center of the inner disk. Schematically: 

 Outer ring is shown as a shade of yellow, and inner disk light pink. The four quadrants are I, II, III, IV going anticlockwise starting from the Northeast quadrant. 

The four quadrants perfectly match the four quarters of the outer ring. We follow counterclockwise convention and also start with quadrant I. Moves e1, e2 will denote expanding quadrant I piece clockwise and anticlockwise: 

e1 expands piece I counterclockwise and shrinks pieces III and IV into a single piece that will occupy quadrant III. After expansion, piece I occupies quadrants I and IV. 

e2 expands piece I clockwise and shrinks pieces II and III into a single piece that will occupy quadrant III. Following the expansion, piece I occupies quadrants I and II. 

We proceed counterclockwise. Moves e3 and e4 expand the piece in quadrant II, clockwise and anticlockwise, correspondingly: 

 

We proceed, denoting clockwise and anticlockwise expansions of piece III by e5, e6, and the two expansions of piece IV by e7, e8. Here is the diagram of all the moves, where the arrows indicate direction of expansion, clockwise or anticlockwise: 

Now for some applications. Spoiler alerts--we're going to solve levels 1, 3, and 10 of Ringiana, and in few steps. You might want to pause and crack them on your own first!  

Ringiana level 1 is solved by the e2 move:

Ringiana level 3 takes two moves, e5 followed by e8: 

We write this sequence of moves e5e8 or simply e58.

Ringiana level 10 is done in four moves: 

Can you write them down? They are e6, e2, e4, e8. We write the solution as e6e2e4e8 or, shorter, e6248. Each of these moves expands-shrinks counterclockwise, so they are all "anticlockwise" moves. These are exactly the four anticlockwise moves in Ringiana, e2, e4, e6, e8--carrying even labels. The clockwise moves are e1, e3, e5, e7, exactly those with odd labels. In Ringiana notation, odd=clockwise and even=anticlockwise. 

Can you find other Ringiana and Ringsanity levels that can be solved by only clockwise or only anticlockwise moves?