(Mathematically) Making a 2×2 Rubik’s Cube

Almost everyone has, at some point, played with the deceptively simple puzzle that is a Rubik’s cube. Even before studying pure maths, we had heard about the idea of Group Theory through an interest in Rubik’s Cubes. Rubik’s Cubes are a common example in group theory because of the physical illustration of the mathematical idea of a group. A group is defined as a set equipped with an operation with elements composed into other elements, identity and inverse elements, as well as being associative. The elements of the group that defines a Rubik’s Cube are all the possible scrambles. The operations are generated by rotating faces of the cube, meaning algorithms that manipulate the cube in more specific ways can always be broken down into a collection of face turns. The identity of the Rubik’s is not moving the cube, which maintains the current scramble. The inverses are just rotating faces in opposite directions or composing those inverses as to undo a collection of moves; this can be thought of as undoing the moves of a scramble to solve the cube again. Finally, associativity can be thought of as the fact that any string of moves can be grouped together into collections of easy to do moves without affecting the algorithm, which is rather important for solving cubes quickly.

The reader may be wondering the exact mathematical construction of a Rubik’s Cube. For example, a clock is used to represent a group called the “cyclic group” because of the repeated cycles through the numbers. Similar to the jump in complexity of movement of the hand of a clock to the movement of pieces of a Rubik’s Cube, the group representing a Rubik’s Cube is too complex for the purpose of this article. For solving a Rubik’s Cube, it is not necessary to know the mechanical workings, but it can help gain a deeper understanding of the cube. The same concept will be applied to the group as the specific construction will not be necessary for following conclusions.

From a strictly mechanical standpoint, a 2x2 Rubik’s Cube is the same as a 3x3. A 2x2 functions as a 3x3 with smaller edges hidden behind larger corners. The same idea applies to the groups that define each of the different cubes. A quotient group is a group that can be obtained through sending elements of a group to the quotient group through an equivalence relation. For the quotient group Q = G/H, Q is constructed by sending elements of G that differ only by elements of H to the same element in Q. If G were to be the group of a 3x3 and we wanted to make Q a 2x2, how do we construct H. Thinking back to the physical way this is done, we want an operation that “hides” the edge pieces and only gives us corner pieces. The necessary group turns out to be the group of algorithms that move and rotate edge pieces of the Rubik’s Cube. The reader should check for understanding of the following: if all of the possible edge cases are equivalent, the equivalence classes can be represented as different possible corner positions, which is just a 2x2.

The last step to confirm that the results are mathematically sound is to confirm that the group of edge positions and orientations is a normal subgroup of the 3x3. A subgroup means that the edge positions are a subset of the total scrambles and that the moves on a 3x3 are moves on the set of edge positions, which can be checked through an understanding of the Rubik’s Cube itself. To be a “normal” subgroup, the edges must follow the property that the combination of any moves on the 3x3, then moving only edges, and then the inverse of the first moves results in moving edges. Since edges and corners are independent of each other, the corners are unaffected by the middle move and thus scrambled and solved by the first and last move. Only edges can change during this process, meaning that the subgroup of edges is normal.

It has taken groups, quotient groups, equivalence relations, and normal subgroups all to mathematically represent that simply ignoring edges on a 3x3 Rubik’s Cube leaves a 2x2. Armed with this knowledge, the reader may consider what other quotient groups can be created on a 3x3 by making other collections of scrambles equivalent. For example, can the group of moves that only move and rotate corners be treated the same why we treated the group of moves that only move and rotate edges?

Contributors: Joseph Brewster, David Staudinger

关于我们

Chúng tôi là sinh viên năm thứ mười hai ở trường học viên quốc gia quận Morris. Chúng tôi học toán thuần túy. Brendan Halstead là thày giáo của chúng tôi.

Universal Property: How can we define mathematical objects?

In algebra we are interested in thinking about objects. Objects can be many things including numbers, sets, and many more complicated constructions. Category theory is a powerful tool which analyzes these objects and how they are related.

When defining a category we define what the objects are and what the “morphisms” between those objects are. Morphisms are however we choose objects to be related. There are some additional restrictions which we can touch on later.

Let’s look at a simple category: In this category, the objects are positive integers and morphisms compare the value of these numbers. We’ll say the morphism points towards the bigger number. More rigorously, there exists a morphism from $$a$$ to $$b$$ if and only if $$a\leq b$$. We can visualize this with the following diagram:

We can make some obvious statements about morphisms in this category. It is always true that $$a\leq a$$. We can also say that if $$a\leq b$$ and $$b\leq c$$ then $$a\leq c$$. These are the additional constrictions on morphisms: every object must have a morphism to itself (called the identity morphism) and that composing morphisms in a row implies the existence of a morphism connecting the ends:

So now we understand a basic category and how it works.

Let’s look at a more interesting category. The objects are still positive integers and now the morphisms are divisibility operators. This means that there is a morphism from $$a$$ to $$b$$ if and only if $$a$$ divides $$b$$ (written as $$a | b$$). For example: $$3|9$$, $$2|e$$ if $$e$$ is even.

Let’s take a look at our first Universal Property. Say we have two numbers $$a$$ and $$b$$ which both divide $$z$$. What number $$w$$ has the property that no matter what $$z$$ is, as long as $$a$$ and $$b$$ both divide $$w$$, it is also true that $$w$$ divides $$z$$? Observe the diagram

Take a second to understand the question. For any $$z$$ which is divisible by both $$a$$ and $$b$$, we want to find a $$w$$ which is also divisible by both $$a$$ and $$b$$ which must necessarily divide every choice of $$z$$. For every multiple of both $$a$$ and $$b$$ (called $$z$$), we want to find a multiple of $$a$$ and $$b$$ (called $$w$$) which always divides it.

Let’s consider some examples. Let $$a=4$$, $$b=6$$. What are some common multiples of these? There’s $$6\times 4 =24$$ but there’s also $$6\times 2 = 4\times 3 = 12$$ and $$6\times 100 = 4\times 150 = 600$$. These are a few of our candidates for $$w$$.

So then, what is a reasonable choice? Can we choose a huge number like $$600$$? No, because $$600$$ doesn’t divide $$24$$. So, we are looking for the smallest of these values which divides every possible $$z$$. A least common multiple, if you will. That would be $$12$$. This works for every $$z$$ value i.e. every common multiple of $$4$$ and $$6$$. Any number which is a common multiple, is itself a multiple of the least common multiple. We can choose $$z=12$$ or $$z=600$$ and it doesn’t matter. $$w=12$$ will always work.

Let’s look at what we just did there. We took this diagram, which admittedly we kind of just conjured out of thin air, but we used it to rigorously define the least common multiple. A number is the least common multiple if and only if it satisfies this diagram in this category. This is a rigorous definition. This quality of how the least common multiple interacts with arbitrary numbers is its universal property.

Later, we will discuss at greater length how these kinds of structures can be applied to sets. Even though with the least common multiple there might be simpler ways to define it, we often find in Algebra that the best way to define objects is by their universal property.

As an exercise to the adventurous and curious reader, consider the the following diagram in the same category. What object (number) $$w$$ satisfies the universal property:

Remember, solid lines are given. The dotted line is what you are trying to prove exists for any choice of $$z$$.

(Hint: $$z$$ must satisfy the properties indicated by the arrows to $$a$$ and $$b$$)

Contributors: David Staudinger, Joseph Brewster

Bigger Infinities Than Infinity

Can you get a room in an infinitely large, yet fully booked, hotel? There are a lot of rooms to count in Hilbert’s Grand Hotel, an infinite number of them to be exact. A common understanding of infinity is that it is at the end of counting, the last room. Start at one and end at infinity after a long walk down the hall. There are, however, many more numbers than just 1, 2, 3, etc; so how many of those are there? This is where the notion of thinking of “infinity” as the end of counting becomes complicated. Infinity is specifically bigger than any number you can count to, meaning regular intuition of math stops working. If there were a million rooms in a hotel and all were full, you couldn’t get a room; not a billion or even a trillion. But with infinite rooms, you can certainly get a room in the hotel, just tell everyone to move down by one, and you take the first room.

Now imagine a rather large group of new guests comes, infinitely large actually; how could anyone possibly give all these guests a room? Unlike when you got a room, Hilbert can’t just shift everyone over by infinite rooms. How about another, not hotel related, question, “how many even numbers are there? Odd?” It may be clear that there are the same number of evens as odds, because each make up half of the natural numbers. What if I told you that there are the same number of even numbers as natural numbers. I can hear you thinking, “How can this be?! It’s obviously half as many!” This can be explained by taking each counting number and doubling it; there will be only even numbers and you’ll never run out of numbers because there is no last counting number to double. This idea can be used to fit infinitely more guests into the hotel; scale the room numbers and fit an infinite number of guests between all the current guests. So now Hilbert knows how to add an infinite number of guests into the hotel. He should be done now, right? Wrong.

Word of Hilbert’s extremely spacious hotel has now attracted even more guests than before, an infinite number of buses, each carrying an infinite number of guests, arrive. Once again, the previous methods fail as the room numbers cannot scale by infinity. To fit this many guests, it requires some clever mathematical tricks. One possible solution is to send guests to powers of prime numbers; for example, the guests in room i go to room 2i and those in the first bus in seat n go to 3n, continued for infinite prime numbers for each bus. Another creative solution is to interweave the numbers representing the bus and the seat with the first digit of each, the second digit of each, etc to assign the new room numbers. Each of these methods is able to send any guest represented by a pair of natural numbers (a,b) to a single natural number in the hotel. There are many more possible solutions to this particular section of the problem, an interesting question for the reader’s consideration.

There was a single bus left over after Hilbert somehow found rooms for the infinite busses of infinite guests; however, the guests on this last bus don’t have seat numbers, rather they are all identified by an infinitely long name. It may, at first, seem like a doable task for the expert room arranger; however, this is an impossible task. Unlike the buses of guests, you cannot count these named guests. Since previous groups had a first and second guest, it was possible to fit them into the hotel using the clever tricks explained previously. The group of named guests is simply too large to fit into the hotel. Consider an infinite list of these infinitely long names of the guests. If you generate a new name by changing the first letter of the first name, second letter of the second name, and continue for all the names, you will get a new infinitely long name that is not in the list. You can always “find” new names that make the list even longer. Even if you arranged the names in alphabetical order, you could simply “make” more names in between those names, making it impossible to order and number the new group. Since the members of the group cannot be properly assigned natural numbers, none of the previously explored tricks can fit them into the hotel. Defeated, the hotel manager resigns on the spot, having made all the money he could need from the admission of the previous infinite guests.

Hilbert’s hotel is an example of the difference in cardinality, or size, of sets. Groups with the same or less cardinality as the room numbers could fit, but even then there was an infinite group too large for the infinite hotel. This is illustrated by numbered guests being able to fit into numbered rooms, but named guests could not fit because infinitely more names could always be generated from any infinite list. The number of rooms is considered to be infinite, but “countably’’ infinite, meaning it corresponds in a one-to-one relationship with the counting numbers. As touched on when covering the named guests, the group of guests could not be counted, and therefore could not be admitted. This larger, continually generated infinity, is referred to as “uncountably” infinite, since it cannot be in a one-to-one relationship with counting numbers. The notion of different size infinities is crucial in the study of different sets of numbers.

The technique used to fit guests into Hilbert’s hotel is a valid approach to other, arguably more mathematical, questions. For example, does there exist a function that sends the interval [0,1) to (0,1) with everything in the latter interval being “hit” by a unique number in the previous interval. It turns out that there is. The function exists by “shifting” all the numbers that can be represented by 1/n over to 1/(n+1), sending 0 to ½, and sending the rest of the numbers to themselves.

The existence of a function that sends any set to any other set given by every element of the second set being “hit” by a unique element in the previous set means that the sets have the same cardinality. These functions can be used to compare the sizes of different sets; many of these comparisons require interesting tricks of grouping and moving infinitely large sets around, like those presented in both problems.