Category: History

Win $1,000,000 by Playing Minesweeper!

Yes, you read that headline correctly: it is possible for a mathematician to win $1,000,000 by playing Minesweeper. Here’s how:

First, the source of the $1,000,000. In 2000, the Clay Mathematics Institute created a list of important unsolved problems in mathematics (see also Wikipedia), offering each one a prize of $1,000,000 for a solution. Specifically, according to the rules,

[A] proposed solution must be published in a refereed mathematics publication of worldwide repute… and it must also have general acceptance in the mathematics community two years after.

Of the eight problems on the list, one (the Poincare conjecture) has been solved so far. Incredibly, the mathematician who produced the proof turned down the $1,000,000. He was also awarded the Fields Medal, considered the Nobel Prize of mathematics, but he refused that as well.

The Millennium Problems parallel the famous 23 Hilbert problems posed by eminent mathematician David Hilbert in 1900. The Hilbert problems were unsolved at the time and were posed as a challenge to the mathematicians of the 20th century. These problems certainly generated a lot of buzz in the mathematical community, and most have been solved since 1900. (Sadly, none of the solvers won $1,000,000 for their work!)

What does this have to do with Minesweeper?

One of the problems is the famed P vs. NP problem. From Clay Mathematics:

Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker’s list also appears on the list from the Dean’s office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

In 2000, Richard Kaye (University of Birmingham, UK) made connected Minesweeper to the P vs. NP problem. Famed mathematical journalist Ian Stewart did a very nice job of describing the connection between the two, so I’ll simply refer to his post for a detailed description. Dr. Kaye’s website also gives a lot of information about the connection.

US vs UK: Mathematical Terminology

Math With Bad Drawings had an amusing essay concerning differences in mathematical nomenclature between American English and British English. I thought that it would be appropriate to share this around the Fourth of July.

From the essay and the comments to the essay:

  • Math vs. maths
  • Zee vs. zed
  • 3.5 vs. 3\cdot 5
  • Trapezoid vs. trapezium
  • Scientific notation vs. standard form
  • Exponents vs. indices
  • Revise and review vs. review and revise
  • Imperial units vs. metric units
  • Pythagorean theorem vs. Pythagoras
  • Slope vs. gradient
  • Root vs. surd
  • PEMDAS vs. BIMDAS
  • Billion vs. trillion (a generation ago)
  • GCD (greatest common divisor) vs. HCF (highest common factor)

John Nash: A Tragic but Meaningful Life

Princeton University’s Office of Communications put together a well-written news release concerning the life and tragic death of John Nash: http://www.princeton.edu/main/news/archive/S43/27/52G52/index.xml?section=featured. This very readable article discusses not only his mathematical contributions that ultimately led to his winning the 1994 Nobel Prize in Economics but also the very human side of his mental illness.

See also http://www.nytimes.com/2015/05/25/science/john-nash-a-beautiful-mind-subject-and-nobel-winner-dies-at-86.html?_r=0

Free resource: History of mathematics

I recently received an e-mail promoting the following free website: http://www.wwu.edu/teachingmathhistory/index.shtml

From the e-mail:

[This] is a collection of materials directed at either teaching a math history class or including math history ideas in other math courses. Things that are available:

  1. An extensive set of problem-solving lessons that include student materials, teacher commentary, problem sets, problem commentary, associated writing topics, and references…originally this was prepared with the intent it would become a “300-page” book, but now is being made available for FREE.
  1. A broad collection of materials that supports a Math History course … writing assignments, paper topics, writing prompts, rubrics, etc.
  1. A multi-level reference list of historical resources that focus on the history of mathematics, ranging from texts to articles. It can be used to build identify resources in the writing of papers and guide the broad understanding of the history of mathematics. If students need reference info on topic or mathematicians, please share this with them….might lessen the over-emphasis on Internet resources.

Free resource: Historical mathematics problems

I recently received an e-mail concerning the following free resource: http://mathhistoryproblems.wwu.edu/problem_select.asp. From the e-mail:

[This] is a data base of more than 1600 historical problems connected with mathematical topics, skills, and concepts taught in secondary schools and colleges. The problems are categorized within broad areas of number, algebra, geometry, measurement, trigonometry, number theory, probability, statistics, pre-calculus, calculus, logic, discrete mathematics, and recreational mathematics. Revealing international contributions and changing cultures, the problems span the full history of mathematics (2000 B.C. – 1940). Each problem statement includes its source and solution commentary.

R. L. Moore, the Moore method, and Inquiry-Based Learning

Devlin’s Angle recently published a nice synopsis of the work of R. L. Moore, one of the great mathematics instructors of the 20th century: http://devlinsangle.blogspot.com/2015/02/the-greatest-math-teacher-ever.html

Moore’s method uses the axiomatic method as an instructional device. Moore would give the students the axioms a few at a time and let them deduce consequences. A typical Moore class might begin like this. Moore would ask one student to step up to the board to prove a result stated in the previous class or to give a counterexample to some earlier conjecture — and very occasionally to formulate a new axiom to meet a previously identified need. Moore would generally begin by asking the weakest student to make the first attempt — or at least the student who had hitherto contributed least to the class. The other students would be charged with pointing out any errors in the first student’s presentation.

Very often, the first student would be unable to provide a satisfactory answer — or even any answer at all, and so Moore might ask for volunteers or else call upon the next weakest, then the next, and so on. Sometimes, no one would be able to provide a satisfactory answer. If that were the case, Moore might provide a hint or a suggestion, but nothing that would form a constitutive part of the eventual answer. Then again, he might simply dismiss the group and tell them to go away and think some more about the problem.

Moore’s discovery method was not designed for — and probably will not work in — a mathematics course which should survey a broad area or cover a large body of facts. And it would obviously need modification in an area of mathematics where the student needs a substantial background knowledge in order to begin. But there are areas of mathematics where, in the hands of the right teacher — and possibly the right students — Moore’s procedure can work just fine. Moore’s own area of general topology is just such an area. You can find elements of the Moore method being used in mathematics classes at many institutions today, particularly in graduate courses and in classes for upper-level undergraduate mathematics majors, but few instructors ever take the process to the lengths that Moore did, and when they try, they rarely meet with the same degree of success.

Lest this sound extreme, here’s a snapshot of Moore’s educational philosophy produced:

If you measure teaching quality in terms of the product – the successful students – our man has no competition for the title of the greatest ever math teacher. During his 64 year career as a professor of mathematics, he supervised fifty successful doctoral students. Of those fifty Ph.D.’s, three went on to become presidents of the AMS – a position our man himself held at one point – and three others vice-presidents, and five became presidents of the MAA. Many more pursued highly successful careers in mathematics, achieving influential positions in the AMS and the MAA, producing successful Ph.D. students of their own and helping shape the development of American mathematics as it rose to its present-day position of world dominance.

Present-day inquiry-based learning uses some (but not all) elements of Moore’s teaching style. I personally do not teach using the Moore method, as I have developed my own teaching style that seems to work well with my students. That said, I would seriously consider using the Moore method for classes which are best suited for this style of pedagogy.

Your Humble Servant, Isaac Newton

From the YouTube description:

Almost fifty years ago, Cambridge University Press published the correspondence of Isaac Newton, a seven-volume, 3000-page collection of letters that provides insight into this great, if difficult, genius. William Dunham shares his favorite examples of Newton as correspondent. He ends with Newton’s most-quoted line about standing on the shoulders of giants and how his search for its place of origin led him, improbably, to a library in Philadelphia.

A 100-Year old computer for computing Fourier transforms

From http://www.engineerguy.com/fourier/:

Many famous machines have been built to do math — like Babbage’s Difference Engine for solving polynomials or Leibniz’s Stepped Reckoner for multiplying and dividing — yet none worked as well as Albert Michelson’s harmonic analyzer. This 19th century mechanical marvel does Fourier analysis: it can find the frequency components of a signal using only gears, springs and levers. We discovered this long-forgotten machine locked in a glass case at the University of Illinois. For your enjoyment, we brought it back to life in this book and in a companion video series — all written and created by Bill Hammack, Steve Kranz and Bruce Carpenter.

A free PDF of their book is available at the above link; the book is also available for purchase. Here are the companion videos for the book.

Student t distribution

One of my favorite anecdotes that I share with my statistics students is why the Student t distribution is called the t distribution and not the Gosset distribution.

From Wikipedia:

In the English-language literature it takes its name from William Sealy Gosset’s 1908 paper in Biometrika under the pseudonym “Student”. Gosset worked at the Guinness Brewery in Dublin, Ireland, and was interested in the problems of small samples, for example the chemical properties of barley where sample sizes might be as low as 3. One version of the origin of the pseudonym is that Gosset’s employer preferred staff to use pen names when publishing scientific papers instead of their real name, therefore he used the name “Student” to hide his identity. Another version is that Guinness did not want their competitors to know that they were using the t-test to test the quality of raw material.

Gosset’s paper refers to the distribution as the “frequency distribution of standard deviations of samples drawn from a normal population”. It became well-known through the work of Ronald A. Fisher, who called the distribution “Student’s distribution” and referred to the value as t.

From the 1963 book Experimentation and Measurement (see pages 68-69 of the PDF, which are marked as pages 69-70 on the original):

The mathematical solution to this problem was first discovered by an Irish chemist who wrote under the pen name of “Student.” Student worked for a company that was unwilling to reveal its connection with him lest its competitors discover that Student’s work would also be advantageous to them. It now seems extraordinary that the author of this classic paper on measurements was not known for more than twenty years. Eventually it was learned that his real name was William Sealy Gosset (1876-1937).