You are currently browsing the monthly archive for January 2012.
Proofs from THE BOOK by Martin Aigner and Günter Ziegler begins by giving six proofs of the infinity of primes. We will go over the third proof. Before we go over this proof, lets cover some background.
— 1. Fermat Numbers —
Fermat numbers are defined by
so that and . They are of great interest in many ways: for example, it was proved by Gauss that, if , is a prime , then a regular polygon of sides can be inscribed in a circle by Euclidean methods. The property of the Fermat numbers which is relevant here is
We will prove this theorem later.
The first four Fermat numbers are prime, and Fermat conjectured that all were prime. Euler, however, found in 1732 that
In 1880 Landry proved that
It is currently known that , is composite for . Factoring Fermat numbers is extremely difficult as a result of their large size. has known factors with remaining (where denotes a composite number with digits). has known factors with remaining. has no known factors but is composite. There are currently four Fermat numbers that are known to be composite, but for which no single factor is known: and . In all the other cases proved to be composite a factor is known. No prime has been found beyond , and it seems unlikely that any more will be found using current computational methods and hardware.
— 2. Infinitude of Primes Theorem —
We are now ready to prove Euclid’s Second Theorem, also called the Infinitude of Primes Theorem using the third proof in Proofs from THE BOOK.
from which our assertion follows immediately. Indeed, if is a divisor of, say, and , then divides , and hence or . But is impossible since all Fermat numbers are odd.
To prove the recursion we use induction on . For we have and . With induction we now conclude
The following is the first post in 2006 regarding George Vaccaro’s horrifying encounters with the Verizon billing department over the difference between dollars and cents (and other basic math).
Verizon doesn’t know Dollars from Cents
I have a Verizon unlimited data plan in the U.S. and recently crossed the border to Canada. Prior to crossing the border I called customer service to find out what rates I’d be paying for voice and data. The data rate I was quoted was “.002 cents per kilobyte.”
I was surprised at the rate so I confirmed it with the representative I spoke to, and she confirmed it “point zero zero two cents per kilobyte.” I asked her to note that in my account.
I received my bill and was charged $.002/KB – which is dollars – “point zero zero 2 dollars per kilobyte”. As it is translated to cents would be .2 cents or 2 tenths of a cent – which is a 100 times greater rate than I was quoted.
My bill for my data usage in Canada was therefore much greater than I had expected – using the quote I was provided before my usage.
I have tried to resolve this issue with customer service reps on the phone, but noone seems to see the difference between “.002 cents” and “.002 dollars”.
Here is the audio of my most recent call with them on the matter. Original Full Length Recording I started recording when they put on the supervisor – I was a bit ticked at that point.
Who knew what confusion “$1 = 100 cents” could cause?
I’m still currently on the hook for the $71 and change. Hopefully someone at Verizon will figure this out and make ammends.
This is from XKCD, in response to George Vaccaro’s encounters:
Here is the timeline of events
- 12-07-2006 – Initial Post
- 12-08-2006 – First Email From Verizon – 50% Refund
- 12-08-2006 – My Response to Verizon
- 12-10-2006 – Response from Verizon – Full Refund – No Explicit Admission of Fault
- 12-10-2006 – Second Known Instance of the Problem
- 12-11-2006 – Verizon Admits Fault – But have not taken care of other cases
- 12-11-2006 – Open Letter to Verizon Management
- 12-13-2006 – Will Verizon Live up to its Worry Free Guarantee
- 12-14-2006 – Verizon is still Quoting .002 cents
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 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 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 with computational search,” he explains.
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 .
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 . This means that the maximum number of moves that will ever be required for a cube of side is proportional to (Read the proof here).
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.
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 . His first task is to work out how to turn that into an exact number for given sizes of cube.
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.”
These notes are a wonderful introduction to group theory! Though only 39 pages in length, it covers a fair amount of the subject in a very clear fashion by relating the theory to the study of the Rubik’s Cube.
A Rubik’s Cube is a cube in which the 26 subcubes on the outside are internally hinged in such a way that rotation (by a quarter turn in either direction or a half turn) is possible in any plane of cubes. Each of the six sides is painted a distinct color, and the goal of the puzzle is to return the cube to a state in which each side has a single color after it has been randomized by repeated rotations. The puzzle was invented in the 1970s by the Hungarian Ernő Rubik and sold millions of copies worldwide over the next decade.
The number of possible positions of the Rubik’s cube is
(Turner and Gold 1985, Schönert). Hoey showed using the Pólya-Burnside lemma that there are positions up to conjugacy by whole-cube symmetries.
The group of operations on the Rubik’s cube is known as Rubik’s group, and the Cayley graph of that group is called Rubik’s graph. The minimum number of turns required to solve the cube from an arbitrary starting position is equal to the graph diameter of Rubik’s graph, and is sometimes known as God’s number. While algorithms exist for solving a cube from an arbitrary initial position, they are not necessarily optimal (i.e., requiring a minimum number of turns) and computation of God’s number is very difficult. It had been known since 1995 that a lower bound on the number of moves for the solution (in the worst case) was 20, it was not known until demonstrated by Rokicki et al. (2010) that no configuration requires more than 20 moves, thus establishing that God’s number is 20.
A Note to the Reader
These notes are based on a 2-week course that I taught for high school students at the Texas State Honors Summer Math Camp. All of the students in my class had taken elementary number theory at the camp, so I have assumed in these notes that readers are familiar with the integers mod n as well as the units mod n.
Because one goal of this class was a complete understanding of the Rubik’s cube, I have tried to use notation that makes discussing the Rubik’s cube as easy as possible. For example, I have chosen to use right group actions rather than left group actions.
The goal of these notes is to give an introduction to the subject of group theory, which is a branch of the mathematical area called algebra (or sometimes abstract algebra). You probably think of algebra as addition, multiplication, solving quadratic equations, and so on. Abstract algebra deals with all of this but, as the name suggests, in a much more abstract way! Rather than looking at a specific operation (like addition) on a specific set (like the set of real numbers, or the set of integers), abstract algebra is algebra done without really specifying what the operation or set is. This may be the first math you’ve encountered in which objects other than numbers are really studied!
A secondary goal of this class is to solve the Rubik’s cube. We will both develop methods for solving the
Rubik’s cube and prove (using group theory!) that our methods always enable us to solve the cube.
Douglas Hofstadter wrote an excellent introduction to the Rubik’s cube in the March 1981 issue of Scientific American. There are several books about the Rubik’s cube; my favorite is Inside Rubik’s Cube and Beyond by Christoph Bandelow. David Singmaster, who developed much of the usual notation for the Rubik’s cube, also has a book called Notes on Rubik’s ’Magic Cube,’ which I have not seen.
For an introduction to group theory, I recommend Abstract Algebra by I. N. Herstein. This is a wonderful book with wonderful exercises (and if you are new to group theory, you should do lots of the exercises). If you have some familiarity with group theory and want a good reference book, I recommend Abstract Algebra by David S. Dummit and Richard M. Foote.
Topics covered are:
- The Rubik’s Cube and Subgroups
- Cube Notation
- Making the Rubik’ Cube into a Group
- Simplifying Group Notation
- The Symmetric Group
- Disjoint Cycle Decomposition
- Rubik’s Cube
- Group Homomorphisms
- The Sign Homomorphisms
- The Alternating Group
- Group Actions
- Valid Configurations of the Rubik’s Cube
- Not only is math beautiful, it is .
- Why did the chicken cross the Möbius Strip?
- I find your lack of math disturbing.
- …and it was delicious.
- Mathematical puns are the first sine of madness.
- If I’ve told you times, I’ve told you times…
- I have an imaginary friend .
- A mathematician is a machine for turning coffee into theorems. – Alfréd Rényi
- Instant mathematician just add coffee.
- Five out of four people don’t understand fractions.
- Old mathematicians never die. They just lose some of their functions.
- A topologist is a person who doesn’t know the difference between a coffee cup and a doughnut.
- Mathematicians have problems.
- What’s your sine?
- With mathematics, the possibilities are infinite.
- , I keep it real.
- Be happy. Do math.
- Mathematics is the language God used to write the universe.
- A mathematician, like a painter or poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas. – G. H. Hardy
- Mathematics knows no races or geographic boundaries; for mathematics, the cultural world is one country. – David Hilbert
- What is the volume of a disk with radius and height ? .