Pressing Toward the Prize

Archive for the ‘Articles’ Category

I recently came upon an article in Math Horizons magazine (Nov. 2010) that caught my eye: The Quest for God’s Number. Now I never knew God had a number, so I thought I better stop and check it out. The first thing I discovered is that God’s number is linked to God’s algorithm… who knew?

What this really has to do with is solving a Rubik’s Cube in the fewest moves, and hence the shortest amount of time. According to the article by Rik van Grol, “God’s algorithm is the procedure to bring back Rubik’s Cube from any random position to its solved state in the minimum number of steps. The maximum of all minimally needed number of steps is referred to as God’s number. This number can be defined in several ways. The most common is in terms of the number of face turns required, but it can also be measured as the number of quarter turns… Earlier this year, after decades of gradual progress, it was determined that God’s number is 20 face turns. Thus, if God’s algorithm were used to solve the cube, no starting position would ever require more than 20 face turns.” The article chronicles the process used to determine that God’s number is 20, and as one might imagine, it involves looking at an astronomically large number of possible pattern combinations, more than 4.3 x 10^19.

It was interesting to find that one of the mathematicians working on lowering the upper bound in search of God’s number used group theory in his calculations. He used the cube group, similar to the shape groups we studied in Abstract Algebra. His group had 6 moves on a cube fixed in space, Left, Right, Front, Back, Up, and Down, and the group operation was concatenation. He then divided the cube group into a nested chain of subgroups, and created an algorithm to eliminate some of the moves early on in the process. Using this method, he was able to show that the Rubik’s Cube could be solved in at most 85 moves. This was in 1979. By January of 1980 he had reduced it to 80, and by the end of that year, to 52. In 1995, another mathematician brought the upper bound to 29 face turns, but it was not until July of this year that the upper bound met the lower bound at 20.

Now that they have found God’s number for the classic 3x3x3 cube, they have turned their attention to the 4x4x4, 5x5x5, 6x6x6, and 7x7x7 cubes, all of which are currently on the market. There might be a hitch in this, though, since the 7x7x7 cube has 2.0 x 10^160 possible positions. Good luck with that!

Advertisements

I was looking through the November 2010 issue of Math Horizons, and I discovered an article by Stephen Abbott in which he interviews Corey Greenspan, the winner of this year’s memorizing \pi contest at Southern New Hampshire University. Apparently Corey memorized the first 419 digits of \pi, and he shares with Stephen Abbott how he managed such a feat. Personally, I can’t imagine doing what Corey did, but his accomplishment pales in comparison to the world records for memorizing \pi. According to the article, the official world record held by Lu Chao is 67,890 digits of \pi, with the unofficial world record being 100,000 digits as recited by Akira Haraguchi of Japan.

Not to be outdone, check out these fun videos of a young lady balancing 15 books on her head while solving a Rubik’s cube and reciting the first 100 digits of \pi. The first video is recorded in her dorm room,

and the second is of her sharing her “talent” on the Ellen DeGeneres show.

Truly, I couldn’t do even one of the things she does, let alone all three at once! Like I said, people are aMAZing!!

The time has come for me to submit the proposal for my Capstone Senior Project. I have decided that I would like to explore the complexities of voting, including the paradoxes and problems that can arise when there are three or more candidates (or issues) on the ballot. There is a rich history of voting analysis that dates back to 1770 with French mathematician JC Borda, who, concerned with the outcomes produced by plurality voting, developed a weighted voting system called the Borda Count. A decade or so later, the Marquis de Condorcet attempted to discredit the Borda Count by demonstrating flaws in the procedure, and presented his method based on pair-wise counting, which had some problems of its own.

Then in the 1950’s, Kenneth Arrow, perhaps unaware of this 18th century conflict, analyzed similar problems with voting. He began by defining basic conditions that should be met in a voting procedure, and then attempted to find a voting method that satisfied these conditions. His conclusion was that with three or more candidates, the only procedure that satisfies all the conditions is a dictatorship! So if we are left to choose “between a dictatorship or a paradox” (per Donald G. Saari), what are we to do? Saari uses mathematics to show that there is a more reasonable option, and in fact shows mathematically that the Borda Count is the most reasonable option. I would like to study this centuries-long debate, the issues and “solutions” as they were presented, as well as Saari’s analysis that leads to a reasonable resolution. As has been suggested, since Saari uses linear algebra in his analysis, it would be interesting to run a few elections with fellow students and manipulate the outcomes using linear spaces. I would also like to investigate the reasons why plurality voting is still widely used, even though its flaws are fairly obvious.

I recently ran across an article that Donald G. Saari (author of Basic Geometry of Voting) wrote in 1996 about that year’s elections, highlighting the ease with which an unwanted outcome can occur. As he explains, when an election result is not what one thinks it should be, that is, the preferred candidate or issue does not win, it is called a voting paradox. This is generally not due to the voters, but rather the voting procedure used. In plurality voting, the process we use in which each voter votes for one candidate and the candidate with the most votes wins, multiple candidates can “split the vote” causing an “inferior” (at least according to the will of the people) candidate to be elected.

Saari demonstrates his point with a very entertaining story about his encounter with a group of precocious 4th graders in 1991. He was attempting to present a counting problem caused by a hypothetical voting example, when the students recognized a flaw in his assessment of the winner in a three-way vote. According to plurality voting, candidate A was preferred to B who was preferred to C in a 6:5:4 vote, when considering only the first choice of each voter. But the students immediately protested, because he did not factor in the “next best” preference, which alters the outcome. In fact, when all rankings were considered, not just the top-ranked candidate, the winner A under plurality voting was actually the least preferred by the majority of the voters, and C was in fact the favorite.

When he asked the students what they thought was the “correct” voting procedure to use, one of the students suggested voters assign 3 points to their favorite candidate, 2 points to the next best, and 1 point to their least desirable candidate. What this student described is the Borda Count method, named for the French mathematician JC Borda, who developed this method in 1770. When the Borda Count method was applied to the voting example, it showed that C was preferred to B who was preferred to A by a 34:29:27 vote – consistent with the students’ earlier assessment. Then Saari presented a version of Marquis de Condorcet’s puzzling example from the 1780’s that shows it is possible to have no winner, because there is a way to count the votes so that every candidate has the same number of votes. The students saw right through this example, as well.

The amazing thing about these students is how quickly they recognized a flaw and were able to suggest reasonable solutions, based solely on their examination of the problem. As Saari points out, they have not yet been conditioned to blindly accept the way things are, but rather used critical thinking skills coupled with their value of fair play. He is concerned that too often our educational system stifles the creativity of our students rather than nurture their inventiveness and innate desire to explore the world around them. He suggests that educators consider changing their classroom approach in order to foster creativity and develop problem-solving skills in their students. As these 4th graders demonstrate, children can accomplish amazing things when given the right environment.

I recently did a review of an article involving Gaussian integers (complex numbers whose real and “imaginary” parts are integers) in which the Euclidean algorithm was used to find the greatest common divisor (gcd) of two complex numbers. I had never heard of the Euclidean algorithm before, and the process described in the article involved complex numbers and several Greek letters, so I had no idea what was going on. Then, as luck would have it, only a few days later we discussed in math class how to use the Euclidean algorithm to find the gcd of two integers, that is, the largest number that divides both of them without leaving a remainder. It is based on the principle that the gcd does not change if the smaller number is subtracted from the larger number. If this process is repeated, the numbers keep getting smaller until one of them is zero. At this point, the gcd is the larger, non-zero number.

Here is a simple video that describes the process used to find the gcd of 123 and 36:

So what happens if the numbers are a bit larger?

Let’s find the gcd of 5,624 and 3,959:

\begin{aligned} 5,624 &= 3,959 \cdot 1 - 1,665\\ 3,959 &= 1,665 \cdot 2 - 629\\ 1,665 &= 629 \cdot 2 - 407\\ 629 &= 407 \cdot 1 - 222\\ 407 &= 222 \cdot 1 - 185\\ 222 &= 185 \cdot 1 - 37\\ 185 &= 37 \cdot 5 - 0 \end{aligned}

So the gcd(5,624, 3,959) = 37.

No matter how large the numbers, the process can be completed in a finite number of steps. It has been found that the maximum number of steps required is five times the number of digits in the smaller integer. If the numbers are sufficiently large, this still could take a very long time. The beauty of this algorithm is that a computer can be programmed to complete the steps in a matter of seconds, rather than the untold hours if calculated by hand. Although I still don’t fully understand this algorithm as applied to Gaussian integers, I have found it to be a wonderful tool for calculations on real integers.

Part of preparing for our Capstone Senior Project is learning how to research information using mathematical resources, including articles, books, and textbooks. Although the database Mathscinet is a great place for gathering references on a particular topic of interest, we have discovered that most of the articles are a bit over our heads. In those research articles, mathematicians are writing to their peers, of which we are not (yet). An alternative for us is to consider using math journals geared more toward the level of undergraduates. This leads me to our current Capstone assignment. After a lesson on how to best read a math article, complete with an appropriate list of do’s and don’ts, each of us was assigned an article to “read” and then do a review in the fashion of a “2nd grade book report.” I found that as simple as this sounds, it was a pretty tall order!

My article was entitled “Gaussian Integers and Arctangent Identities for \pi” by Jack S. Calcut, taken from The Mathematical Association of America, June-July 2009 issue. Not knowing what Gaussian integers were, at least not by name, I was relieved to find that a Gaussian integer is simply a complex number whose real and “imaginary” parts are integers. But as I stated in an earlier blog, my exposure to complex numbers has been minimal, and my exposure to graphing complex numbers has been nonexistent. This made the article a bit of a challenge for me, but the author did a very good job of explaining and defining terms where he thought there might be confusion on the part of the reader; this gave the article the feel of an instructional textbook. Not every term was defined, however, and I was grateful for my current Abstract Algebra course when I had to look up the definition of a commutative ring. Since a commutative ring has to do with binary operations and groups, and we have recently been studying both, I was thrilled to find that I actually understood the definition!

The article began by addressing the connection of arctangent identities for \pi to calculating the decimal digits of \pi. Then a lesson involving unique factorization, primes, and irreducibles in \mathbb{Z}[i], concepts I understood only marginally, led to the main lemma about Gaussian integer z \neq 0 and the conditions under which z^n is real. This was then used to show that a simple form of an arctangent identity for \pi does not exist. The author also expanded the application of the lemma to show connections between rational vs. irrational values in the leg lengths and angles of right triangles, as well as various concepts involving angles created on geoboards. As it turns out, developments in this area have been ongoing since the 14th century, involving a multitude of mathematicians who have discovered, and at times rediscovered, the various concepts, identities, and applications presented. And with the advent of the computer, new calculations, identities, and avenues of study have been made possible. This was a very interesting article, even though there was much I did not fully understand. I am deeply grateful that I only needed to produce a “2nd grade book report” about it!

While reading the September 2010 issue of “Math Horizons” magazine, I ran across some fun and interesting articles. In the “fun” category was an article written by Donald Byrd, a parody, or mathematicizing (is that a word??), of the seemingly endless song “100 Bottles of Beer on the Wall.” For the infinite version, with infinite bottles of beer on the wall, one falls down, and you are left with infinite bottles of beer, forever. The larger infinity version starts with uncountable bottles, if countable bottles fall,  then you still have uncountable bottles of beer. The indeterminate version: start with infinite bottles of beer, if infinite bottles of beer should happen to fall, you are left with indeterminate bottles of beer on the wall, and this is the end of that song! Other versions include geometric progression, Euler’s identity, differentials, identity, topological dimension, and fractal dimension. All in all, pretty entertaining.

Another article, written by Bruce Torrence and still in the “fun” category,  described a convention of magicians, mathematicians, and puzzle masters held in honor of Martin Gardner, “the prolific and magnetic author whose interests spanned the seemingly disparate disciplines of mathematics, puzzles, magic, and the spirited debunking of pseudoscience.” A particularly obscure puzzle was presented by one of the speakers before he abruptly ended his brief talk and sat down: “I have two children. One is a boy born on a Tuesday. What is the probability I have two boys?” …brief pause… “The first thing you think is ‘What has Tuesday got to do with it?’ Well, it has everything to do with it.” As it turns out, this riddle became the talk of the convention, and was finally solved by counting all possible outcomes, including gender, births, and days of the week, and using basic probability theory. By the way, the answer is 13/27.

Finally, of extreme interest to me, was an article about the terrors of Mathematical Analysis. This is the course I will be taking in the spring, and it is the only course I still need to fulfill my major. The bad part is that I am already stressing about taking it. I have heard frightening things about how impossible this course is, and how I should just resign myself to being happy if I pass it, let alone trying to get a good grade in it. So Tina Rapke’s article “Confronting Analysis” was speaking to me. She shares about how she struggled with mathematical analysis in the beginning, actually “drowning” is the word she used, and how she eventually found understanding and success by hard work, tenacity, and consulting multiple resources, some of which she discusses in the article. She is now a Ph.D. candidate pursuing an interdisciplinary degree in mathematics and education, having written her PH.D. candidacy exam in analysis, and passing. Her advice to those who struggle with analysis? a) You are not alone! b) Be open to various textbooks and resources, and  c) Don’t give up!

I think I will keep this article close at hand… spring semester is coming!



    • gramsonjanessa: I can't wait to listen to your capstone presentation in the spring! Your proposal was really interesting and I'm interested to see how the linear alge
    • dewittda: This is impressive! I thought I was good because I solved a rubik’s cube once in an hour. I served with a guy in the Air Force who could solve a r
    • ZeroSum Ruler: The Euclidean algorithm should me the mainstream way we teach students how to find the GCF. Why isn't it? A mystery.

    Categories