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.
No comments:
Post a Comment