You are currently browsing the tag archive for the ‘algorithm’ tag.

In the television show Futurama, episode “The Prisoner of Benda,” Dr. Farnsworth created a machine that swaps the minds of two individuals. Unfortunately, they discover that the machine cannot be used on the same pair of bodies again.

The question is, given a collection of jumbled up minds and bodies, how can you get them all back to normal? Well, they have to come up with some equation to prove that, with enough people switching, eventually everyone will end up in their rightful form.

It was first mentioned in an interview that head writer and executive producer David X. Cohen gave to the American Physical Society:

“In an APS News exclusive, Cohen reveals for the first time that in the 10th episode of the upcoming season, tentatively entitled “The Prisoner of Benda,” a theorem based on group theory was specifically written (and proven!) by staffer/PhD mathematician Ken Keeler to explain a plot twist. Cohen can’t help but chuckle at the irony: his television-writing rule is that entertainment trumps science, but in this special case, a mathematical theorem was penned for the sake of entertainment.”

This theorem is now known as Keeler’s Theorem, or the “Futurama Theorem”.

The Futurama Theorem proves that no matter the size of the collection or how many mind swaps have been made, all minds can be restored to their original bodies using only two extra “clean” bodies (individuals who haven’t swapped minds with anyone) are needed, since a collection of just two people with swapped minds could never get back to normal.

If you want to know more about the details on group theory (group, the symmetric group, permutation diagrams, transpositions, cycle notation, products of disjoint cycles, products of distinct transpositions, etc.) read the talk given by Dana C. Ernst about the Futurama Theorem. He has blogged twice on this talk:
1. Talk about the Futurama Theorem
2. Another talk about the Futurama Theorem

and he has given the talk three times:
1. November 3, 2011 Gordon Talk
2. December 7, 2011 PSU Talk
3. February 28, 2012 UNO Talk

I personally like the first talk. He mentions:

“The slides for the second talk are very similar to the first set, but there are a few differences:

• The second talk is shorter. I trimmed a few things from the first talk that were not completely necessary.
• I’ve improved the wording in a few spots.
• In the second talk, multiplication of permutations is right to left.”

Talks 2 and 3 are almost identical.

If you read the talk, you will understand the proof that appeared in the show,

which uses nothing other than basic facts about group theory and permutations. Furthermore, you will understand applying the algorithm to the arrangement of minds in Futurama requires 13 moves. However, since Fry and Zoiberg only swapped with each other and since there is only one other cycle, we could use Fry and Zoiberg as $x$ and $y$, respectively in the algorithm and thus it only requires 9 moves.

Below are the implementations of the 13 move algorithm in Sage and WolframAlpha. (Note, Sage and WolframAlpha will multiply cycles left to right):
 S_11 = SymmetricGroup(11) c7 = S_11("(1,2,3,4,5,6,7)") c1 = S_11("(8,9)") t1 = S_11("(8,10)") t2 = S_11("(9,11)") t3 = S_11("(9,10)") t4 = S_11("(8,11)") t5 = S_11("(10,1)") t6 = S_11("(11,7)") t7 = S_11("(11,6)") t8 = S_11("(11,5)") t9 = S_11("(11,4)") t10 = S_11("(11,3)") t11 = S_11("(11,2)") t12 = S_11("(11,1)") t13 = S_11("(10,7)")

 

c1*t1*t2*t3*t4*c7*t5*t6*t7*t8*t9*t10*t11*t12*t13 

Click here to view the 13 move algorithm for the Futurama permutation solution in WolframAlpha

Here are some questions posed by Dana C. Ernst:
1. Can we do better (i.e., fewer moves to fix the cycles)?
2. Under what circumstances do we not need to introduce two “clean” people?
3. Would only using one “clean” person ever be useful?
4. Could you use fewer moves if you allowed more than two “clean” people?

We now know the answer to some these questions. Students from the University of California, San Diego have improved the result, giving a better algorithm for finding the minimum number of switches to put everyone’s head back in the right places, give optimal solutions for two particular situations, and give necessary and sufficient conditions for it being possible to represent the identity permutation as $m$ distinct transpositions in $S_n$.

Here is the paper submitted on April 26, 2012.

Cracking the hardest mystery of the Rubik’s cube

ERIK AKKERSDIJK holds the world record for doing it in 7.08 seconds (watch a video). Thibaut Jacquinot does it with one hand (watch a video). Seventeen-year-old Joey Gouly likes to do it blindfolded and Zbigniew Zborowski has done it a staggering 3390 times in one day. They are all experts at solving the Rubik’s cube, the must-have toy of the 1980s and one of the most popular games in history.

Since the first world championship was established in 1982, the record for solving the Rubik’s cube has been slashed from 19 seconds to just over 7 seconds. But it’s not just gamers who are interested in solving the Rubik’s cube. Mathematicians are just as fascinated by this toy. For them, the question is: how many moves are needed to solve a maximally jumbled-up Rubik’s cube? In other words, what is the smallest number $n$ for which the most scrambled standard Rubik’s cube can be solved?

The article above was written Sept. 2008 in the NewScientist. To view the latest records visit the World Cube Association (WCA). Read full article here

The following is a related article written June 2011 in the NewScientist.

Rubik’s cubes of any size can now be solved

Only the most hardcore puzzle-solvers ever go beyond the standard 3x3x3 Rubik’s cube, attempting much larger ones such as those pictured on the right. Now an algorithm has been developed that can solve a Rubik’s cube of any size. It might offer clues to humans trying to deal with these tricky beasts.

Rubik’s cube science got a boost last year when a team led by programmer Tomas Rokicki of Palo Alto, California, showed that even the most scrambled standard Rubik’s cube can be solved in 20 moves or less. That feat was a big deal: the figure has been dubbed “God’s number”, the assumption being that the Almighty couldn’t solve it faster. But that result didn’t shed light on the monster cubes.

So Erik Demaine, a computer scientist at the Massachusetts Institute of Technology, set out to find a general algorithm for solving a cube with any side-length – of $n$ squares.

The new approach differs from that of Rokicki’s. The latter used a “brute force” method, relying on computers borrowed from Google to check all 43 quintillion possible solutions, but Demaine says doing the same for larger cubes would be impossible. “You can’t solve all values of $n$ with computational search,” he explains.

Cubie paths

Instead, Demaine’s team started by looking at a method Rubik’s cube enthusiasts commonly use to quickly solve the puzzle. Essentially, you try to move a single square, or “cubie”, into the desired position while leaving the rest of the cube as unchanged as possible. Because it’s not possible to move a single cubie without disturbing others, this method is time-consuming, requiring a number of moves that is proportional to $n^2$.

Demaine and his colleagues found a short-cut. Each cubie has a particular path that will place it in the correct position. His algorithm looks for cubies that all need to go in the same direction, then moves them at the same time. “We found that instead of solving one cubie at a time, you can parallelise that process and solve several,” Demaine says.

Grouping cubies with similar paths reduces the number of moves required by a factor of around log $n$. This means that the maximum number of moves that will ever be required for a cube of side $n$ is proportional to $\frac{n^2}{logn}$ (Read the proof here).

Helping humans

Figuring out a single cubie’s path without a computer is no easy task, let alone doing it for the whole cube, so it’s unlikely that humans will be able to directly apply this formula. But Demaine reckons it could offer cube-solvers a few tips.

“It gives me a couple of ideas how to solve this thing faster,” agrees Stewart Clark, a Rubik’s cube enthusiast and physicist at Durham University, UK who owns an 11x11x11 cube.

Clark says it’s possible that some of the techniques behind the algorithm could be applied to speeding up other problems that involve searching or sorting through sets of data with a similar mathematical structure to the cube. “It would need a little bit of tweaking, but there are areas where you might be able to tweak it in the right direction.”

So has the Rubik’s cube given up all of its secrets? No, says Demaine. Right now his algorithm only gives an approximate value for the number of moves required to solve a cube of any given size: it states that the value is proportional to $\frac{n^2}{logn}$. His first task is to work out how to turn that into an exact number for given sizes of cube.

Less-scrambled cubes

Even then, however, a further puzzle remains. Demaine’s current algorithm only finds the most efficient way to solve a cube if it is in the most scrambled state of that cube possible. But he would also like to explore whether an algorithm exists for finding the number of moves required by less-scrambled cubes.

“Suppose someone takes a solved 20x20x20 Rubik’s cube and makes five moves – can you figure out [from that scrambled state] what those five moves were?” he asks. In other words, can you solve it in five moves? He suspects that you cannot, but has yet to prove it. “We don’t know.”

For Rokicki, the next task is to find an algorithm that can solve any 4x4x4 cube in the fewest possible moves. “It would probably take more CPU time to solve a single random 4x4x4 position than we used to prove God’s number for the 3x3x3.”

UCLA mathematicians devise an algorithm based on data from the Los Angeles Police Department for the Hollenbeck area east of downtown. Read the article here.