Kipli's Cage

The June issue of Scientific American has an article on Sudoku, the number grid filling-in game that has swept the puzzle world.  (Personally, I find the puzzles tedious, but to each their own.)  As a programming exercise for myself, I put together a python Sudoku class to solve a Sudoku problem.  It uses a simple backtracking algorithm, summarized below:

Given a valid starting position, for each row, each column and each 3 by 3 sub-matrix, construct a set of allowable entries; these are those numbers that are not yet included in the row (column, sub-matrix).  To solve the problem, call the function Fill() on the upper-left cell of the matrix:

Fill (cell):

1. If the matrix is filled then we have a solution: print it and return

2. If the cell is not empty, go to the next cell (move left to right, top to bottom)

3. Else:

   1. find the intersection of the allowable sets for the corresponding row, column and sub-matrix

   2. for each entry in the intersection

      1. place the entry in the matrix, delete that entry from the corresponding sets of allowable entries for the row, column and sub-matrix

      2. call Fill on the next cell

      3. remove the entry from the matrix, add the entry to the corresponding sets of allowable entries for the row, column and sub-matrix

import copy

class Sudoku:
    def __init__(self,initS):
        # make sure original matrix is valid, otherwise warn and return
        if not self.valid_mat(initS):
            print "Initial matrix not valid."
            return
        # store the original problem and make a copy for filling in
        self.originalS = copy.deepcopy(initS)
        self.S = copy.deepcopy(initS)
# set up the row, column and sub-matrix allowable sets
        # start with all possible integers in each set, then remove those in the original matrix
        self.AllowRow = list(set(range(1,10)) for i in range(9))
        self.AllowCol = list(set(range(1,10)) for i in range(9))
        self.AllowSub = list(list(set(range(1,10)) for j in range(3)) for i in range(3))
        for i in range(9):
            for j in range(9):
                self.AllowRow[i].discard(self.S[i][j])
                self.AllowCol[j].discard(self.S[i][j])
                self.AllowSub[i/3][j/3].discard(self.S[i][j])
# workhorse function to find solution recursively
    def fill(self,i,j):
        # do a little bit of index-checking
        if (i > 8 and j > 8) or i < 0 or j < 0:
            print "bad starting location"
            return
        if i > 8:
            # we have a filled matrix
            self.sol_found = True
            print "Solution found:"
            self.print_mat(self.S)
            print "\n"
        else:
            # only fill in empty cells (cell is 0)
            if self.S[i][j] == 0:
                # find entries allowed by row, column and sub-matrix constraints
                # then try each allowable entry one after another
                allowed = list(self.AllowRow[i] & self.AllowCol[j] & self.AllowSub[i/3][j/3])
                for e in allowed:
                    self.S[i][j] = e
                    self.AllowRow[i].remove(e)
                    self.AllowCol[j].remove(e)
                    self.AllowSub[i/3][j/3].remove(e)
                    if j < 8:
                        nexti = i
                        nextj = j + 1
                    else:
                        nexti = i + 1
                        nextj = 0
                    # try to fill the next cell
                    self.fill(nexti,nextj)
                    # reset the matrix and allowable sets for the next entry
                    self.S[i][j] = 0
                    self.AllowRow[i].add(e)
                    self.AllowCol[j].add(e)
                    self.AllowSub[i/3][j/3].add(e)
            else:
                # just go to the next cell
                if j < 8:
                    nexti = i
                    nextj = j + 1
                else:
                    nexti = i + 1
                    nextj = 0
                self.fill(nexti,nextj)
# wrapper function to find solution from the initial matrix
    def solve(self):
        self.sol_found = False
        print "Original Sudoku problem:"
        self.print_mat(self.originalS)
        print "\n"
        self.fill(0,0)
        if not self.sol_found:
            print "No solution"
# check a matrix for valid entries
    def valid_mat(self,mat):
        is_valid = True
        for i in range(9):
            for k in range(1,10):
                if mat[i].count(k) > 1:
                    is_valid = False
        for j in range(9):
            temp = list(mat[i][j] for i in range(9))
            for k in range(1,10):
                if temp.count(k) > 1:
                    is_valid = False
        for i in range(3):
            for j in range(3):
                temp = []
                for m in range(3):
                    for n in range(3):
                        temp.append(mat[3*i + m][3*j+n])
                for k in range(1,10):
                    if temp.count(k) > 1:
                        is_valid = False
        return is_valid
# print the matrix
    def print_mat(self,mat):
        for i in range(9):
            print mat[i]

Some comments on the code:

• I've done very little error-checking; here's hoping that strange data doesn't sneak in.
• Solutions can be found very quickly, though when no solutions are possible, the running time can be a couple of seconds. I've not made any attempt at optimizing the code; there may be special tricks that will speed up the process.
• The code could be modified for larger matrices (say, 16 by 16). However, since solving Sudoku problems is known to be NP-Complete, this kind of backtracking approach will not scale well.
• Two other approaches mentioned in the Wikipedia article are using Knuth's Dancing Links (after modeling the problem as a graph-coloring problem) and constraint programming. These would probably be better than the simple backtracking I used.

Let `f` be a function that chooses a random integer from 1 to 100 (inclusive) with a uniform probability distribution. Then the probability that what `f` returns is an even integer is 1/2. We will use `f * f` to denote calling `f` twice and multiplying the results, so it is simply the product two randomly chosen integers. In general, let `f^n` represent calling `f` `n` times and multiplying the `n` random integers returned.

Let `P(a = E)` be the probability that `a` is an even integer and `P(a = O)` the probability that `a` is odd. Show that

1. `P(f^n = E) = 1 - (1/2)^n`

2. `P(\sum_{k=1}^n f^k = E) = 1/2`

So the probability that the product of a large number of these random integers is even is close to 1, but the probability that the sum of the products of these random integers is even is always 1/2.

What happens if `f` chooses a random integer from 1 to 3? Or more generally, assume that `f` is choosing from some finite set of positive integers with `a` even integers and `b` odd integers. Now what is the probability that the sum of the products, `\sum_{k=1}^n f^k`, is even?

Let `s_n = P(\sum_{k=1}^n f^k = E)`. Set `p = b/(a+b)`, so `s_1 = 1 - p`. Following the proof of (2), we can write a recursive expression for `s_{n+1}`:

`s_{n+1} = P(f^{n+1} = E) s_n + P(f^{n+1} = O) (1 - s_n) = (1 - p^{n+1})s_n + p^{n+1} (1 - s_n) = p^{n+1} + (1 - 2p^{n+1})s_n`.

Since `|s_{n+1} - s_n| < p^{n+1}`, the sequence `\{s_n\}` forms a Cauchy sequence, and so converges to some value `A`.

But what is `A`? Numerical experiments indicate that it is not 1/2 (or if it is, then the rate of convergence is very slow) and a closed form expression for `s_n` generated by Maple is not especially helpful. So at this point I'm stumped.

The number 7712, prime factorization `2^5 241`, appears in several integer sequences. An interesting one is A063776, the number of subsets of `\{1,2,...,n\}` which sum to 0 mod `n`. Investigating this sequence some more leads to a result about the number of losing positions in the game of Nim.

Recall that Nim is played with sticks in heaps: a move is to remove any number of sticks from a single heap and the loser is the player who cannot take any sticks. If there are `k` heaps of `n_i` sticks in heap `i`, then we write the position as `(n_1,n_2,...,n_k)`. If there are no sticks in any heap then the position is (0); if there is more than one heap then we will assume that all the `n_i` are positive (since a heap with 0 sticks doesn't affect the game).

Theorem. Fix `m \geq 1`. The number of losing positions `(n_1,n_2,...,n_k)` in the game of Nim where the `n_i` are distinct and less than `2^m` is `L_m = 2^{2^m - m - 1}`.

Example: if the heap sizes can be between 1 and 7 then `L_3 = 16`. The losing positions are: (4, 5, 6, 7), (3, 5, 6), (3, 4, 7), (2, 5, 7), (2, 4, 6), (2, 3, 6, 7), (2, 3, 4, 5), (1, 6, 7), (1, 4, 5), (1, 3, 5, 7), (1, 3, 4, 6), (1, 2, 5, 6), (1, 2, 4, 7), (1, 2, 3), (1, 2, 3, 4, 5, 6, 7), and (0).

The connection between this result about Nim and the number 7712 can be found in We will get to this result about Nim from the number 7712 through the paper An interesting result about subset sums by N. Kitchloo and L. Pachter. In that paper, the authors derive a formula for the number of subsets `B` of `\{1,2,...,n\}` such that `\sum_{b\in B} b \equiv k` mod `n`.

For example, there are 6 subsets of `\{1,2,3,4,5\}` whose members have sum congruent to 2 mod 5: `\{2\}, \{1,2,4\}, \{3,4\}, \{0,2\}, \{0,1,2,4\}, \{0,3,4\}`.

The formula given by Kitchloo and Pachter works for arbitrary `k` and `n` and involves Euler's totient function `\phi(t)` and the Mobius function `\mu(t)`. But for the special case that `k \equiv 0`, the formula reduces to

`N_n = 1/n \sum_{t|n, t   odd} 2^{n/t} \phi(t)`

(By convention, the empty set is included in this count.) It's not hard to see that the number that started this, 7712, is `N_{17}`.

Kitchloo and Pachter also present a formula for the number of subsets of a finite abelian group `G` whose elements sum to the identity element (0) of `G`. This formula is not terribly complicated but all we will need is the special case that `G` is the direct sum of `m` copies of `\mathbb Z_2`. Then the formula for the number of subsets with zero sum is simply `2^{2^m - m}`.

Now, this count includes the empty set and the set containing just the zero element `(0,0,...,0)`. Of the others, half will contain only non-zero elements, so there are `2^{2^m - m - 1}` nonempty subsets with zero sum and either only non-zero elements or the single element `(0,...,0)`. This is the number given in the theorem; we need only connect it with losing positions in Nim.

There is an easy way to tell if a position in Nim is winning or losing: XOR the binary digits of the number of sticks in the heaps. If the result is all 0's then the position is losing, otherwise it is winning (and the person to move should take the number of sticks needed to change the XOR to all 0). Here's an example with 4 heaps:

Since the XOR is 1001 and not 0000, this is a winning position for the player making the move; he should take 9 sticks from one of the heaps.

The connection between positions of Nim and `\mathbb Z_2^m` is obvious: map the number of sticks in a heap with its binary representation (padded to the left with 0's if needed), then a Nim position is a subset of `\mathbb Z_2^m`; the zero element of `\mathbb Z_2^m` corresponds to the zero game (0) of Nim. Since XOR binary digits and addition in `\mathbb Z_2^m` are equivalent, losing positions of unequal heap sizes are in one-to-one correspondence with subsets of `Z_2^m` with sum of `(0,...,0)`. This proves the theorem.

It turns out that the sequence `L_m` is sequence A016031, a de Bruijn sequence (the number of ways of arranging `2^n` bits in a circle so all `2^n` consecutive strings of length `n` are distinct). And that looks interesting as well...

KnotPlot is a wonderful program for generating, viewing, playing with knots. The program itself has been around for a while, but I first saw it yesterday at a talk on knots. A description of the features of KnotPlot:

Knots can be loaded from a database of almost 1000 knots and links or sketched by hand in three dimensions. Also, knots may be constructed via the Conway notation or using a tangle calculator. A number of special knot types (torus knots, knot chains, Lissajous knots) may be created on the fly. Finally, new knots can be created from old knots using a number of transformations.

There are lots of extras beyond knots, such as creating knots from braids, Celtic knots, and other fascinating demos. In addition to a nice learning tool for knot theory, this is the kind of thing I could spend hours just playing with.

I helped judge a science fair this weekend, and in the process came across an instance of over-mathematization of the world.

The situation was this: I and a group of 5 other people were charged with the task of selecting the top three projects from about a dozen. After going through each project individually and then again as a group while talking with the students who worked on the project, we came up with our own impressions of each project. Now to the decision stage.

We first went down the list of projects and eliminated those that we felt were not 'top three' material. We did this by general consensus: if anyone felt that a project was worth talking about some more then it was added to the list of potential winners. At the end of this we had six projects to consider.

So how do we decide which project is top ranked, which is second ranked, and which is third? This can be viewed as a voting problem, and a method to solve it is called a voting system.

Now, there are lots of voting systems. The most common one is simple majority rule---vote for the choice you most prefer and count how many votes each choice (candidate) receives; the winner is the one with the most vote. Unfortunately, this obviously may not work for more than two choices.

For three or more choices, we could just determine the winner by plurality: the winner is the one with the most votes, though not necessarily the one with the majority of votes. But this method has some problems, most obviously that we need to do more than select a single winner; we also need second and third place. Plurality voting also has the problem that it may encourage voters to not vote for their top-ranked choice, especially if it appears that that their third-ranked choice will win a plurality of the votes. Perhaps by voting strategically (and not true to their preference), a voter can swing the election to their second-ranked choice.

Another method we could use is a Borda count: each person assigns `n-1` points to the top-ranked choice, `n-2` points to the second-ranked choice, and so on to 0 points for the last-ranked choice. Then the points are totaled for each candidate and the winner is the one with the most points (and the second and third place can also be determined). This will find our rankings in one vote.

However, the Borda count also has its problems. In some situations it is possible for a group of voters (or even one voter) to change their rankings and make a winner become a loser while still ranking the original winner first! For example, suppose there are 22 voters with these rankings:

So A gets 21 points, B gets 23 points and C gets 22 points; the Borda ranking is B-C-A. But now suppose that the 4 voters who prefer B-C-A were to change their preferences to B-A-C. They still prefer B (the previous winner), but now the Borda totals come out to 25 points for A, 23 points for B and 18 points for C. Candidate A has gone from third place to first, and the voters who put him there still prefer B to win!

Other voting systems have other problems. In fact, given a set of quite reasonable criteria that a voting system should satisfy (such as not allowing the situation above), there is no voting system that satisfies all of the criteria. This is upshot of Arrow's Impossibility Theorem.

So which voting system should we have used to rank the projects? In fact we didn't use any of them, for the simple reason that we didn't need to. After ranking the projects individually, we put our rankings on the board and saw what the consensus was. In our case, it was clear which project was ranked first, and that the second-third ranks were between two others. After a brief discussion, we all agreed on an ordering and that was that.

And in our case, that was the best option. There was no need to 'quantify' the results since there was no need for a final, end of discussion vote. Unlike most elections, the group was able to continue discussion about the projects until there was a consensus. Perhaps if we had not been able to reach a consensus we would have had to vote, but luckily that wasn't necessary.

However, one member of the group insisted on getting 'objective' results that would 'quantify' the situation, using what (I think) amounted to the Borda count system. With these results, he argued, we could see that the 'right' result was, and so eliminate possible 'force of personality' effects that may arise during discussion.

But why should the Borda count give the 'right' result? Why should any one quantification be preferred over any other? I could understand why it would be nice to protect the wilting lilies of the world who cannot stand up for themselves, but when our rankings are arrived at independently, then displayed for all to see, I'm not sure that personality problem is very significant. (And lest I be accused of being the forcing personality, I should point out that I said nothing at all during the discussion of our second-third choices.)

I think he places too much emphasis on 'quantified' results, especially in this case when there was no need for them. It was especially curious given that there is no objective way to determine which system we should have been using. After all, what criteria we want our system to satisfy is a matter of preference itself; should we have a vote to determine what voting system we should use?

Mathematics is good, and quantification can be useful, but sometimes it is not necessary for reaching a good decision.

Swedish mathematician Lennart Carleson has been awarded the 2006 Abel Prize (BBC report). The award was based in large part on Carleson's work on Fourier series.

But I'm not sure what to make of this part of a Reuter's report:

"The prize statutes say it should aim to spur interest in mathematics among children and young people. So far, all winners of the prize have been in their 70s."

Is Reuter's trying to make a little dig at the Abel awards committee?

A recent post, Ask Mathforge: What are the Odds? at mathforge.net asks a question about the game of High-Low. In the game, a card is turned over (from the top of a regular shuffled deck) and the player is asked to guess if the next card will be higher or lower than the one shown. A simple strategy to play the game would be to guess 'High' if the card is an ace through 6 (consider ace to be '1'), 'Low' if the card is 8 through King, and flip a coin if the card is a 7. Intuitively, the player is playing the best he can without memory.

If we make the assumption that the player always gets the random coin flips correct, what is the probability that he will get every turn correct through the entire deck?

An estimate of the probability puts it at around 1.5 million to 1 (with a few other assumptions). In my approach to the problem, I wanted to count how many arrangements of the cards would be 'good' ones---the player will win following the given strategy (and luck to guess correctly on the middle 7 card). Since there are `{52!}/{(4!)^{13}}` possible arrangements of the cards, we could then determine the probability.

For ease of discussion, let's make the following definition. Given `n` cards of each rank from 1 to `m` (for a total of `mn` cards in the deck), a Hi-Lo arrangement of the cards is an arrangement `a_1 a_2 a_3 \dots a_{mn}` that satisfies

1. `a_i < a_{i+1}` if `1 \leq a_i < m/2`
2. `a_i > a_{i+1}` if `m/2 < a_i`, and
3. if `a_i = m/2` then there are no restrictions on `a_{i+1}`

However, computing `HL(13,4)` by hand (meaning: with a computer search), is not likely. The numbers grow very, very quickly. Here's a summary of some of the values for small `m` and `n`:

The even `m` values in the first column is sequence A048163 in the On-line Encyclopedia of Integer Sequences. The row corresponding to `m = 3` is sequence A110706.

Even for three ranks, the closed-form expression for `HL(3,n)` is complicated. I'm not even sure how to approach the problem of finding `HL(4,n)` for `n\geq 2`, or even what kinds of estimates would be reasonable for `HL(13,4)`.

So the question is still open: what is the probability of getting a HiLo arrangement?

Daniel Horsley, a doctoral student at the University of Queensland, Australia, has reportedly solved Lindner's conjecture on Steiner triple systems.

Let `V` be a set of size `v`. A Steiner triple system (of degree `v`) is a collection of subsets of size 3 such that each pair of elements in `V` appears exactly once in an element of the collection. Put another way, a Steiner triple system is a partition of the edges of the complete graph on `v` vertices into triangles. For example, a Steiner triple system of degree 7 is illustrated below.

There are Steiner triple systems of degree `v` if and only if `v` is congruent to 1 or 3 mod 6. The number of nonisomorphic Steiner triple systems increases very quickly: at `v = 13` there are 80 systems; at `v = 19`, there are 11084874829 different systems.

Lindner's conjecture is about embedding partial Steiner triple systems (a partition of some subset of the edges of the complete graph into triangles). Lindner conjectured that any Steiner triple system of degree `v` can be embeddedin (extended to) any Steiner triple system of degree at least `2v + 1` (and also congruent to 1 or 3 modulo 6).

Steiner triple systems show up in combinatorial design theory, an area of mathematics that aids in the design of statistical experiments (though, as is usual, many important mathematical concepts predate their application and go beyond the applications today). For example, given a collection of different varieties of seeds that we would like to test for (say) hardiness, and a collection of plots where we might plant the seeds, how do we assign seeds to plots so that we can discern differences in seed varieties from differences in land plots?

More information on Steiner triple systems can be found at mathworld and on design theory at DesignTheory.org and the DMOZ Open Directory entry on Design Theory.

The 193-digit number

310 7418240490 0437213507 5003588856 7930037346 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609

has been factored. Mathworld explains why that is a big deal.

Show that there are no five-digit numbers such that if you remove the first two digits and place them at the end (e.g., 12345 to 34512) then the resulting number is half the original.

Note: of course the number 00000 would work, but we will ignore that trivial case.

I've been doing some reading on basic set theory (as part of an "intro to proofs" course) and have been debating what to do with the axioms of Zermelo-Fraenkel set theory. Mathworld lists 9 axioms (plus the Axiom of Choice for a total of 10). Which ones really need to be discussed and how much weight should they have?

Those that I am thinking of focusing on include:

• Extensionality: `\forall A \forall B [(\forall x (x \in A \iff x \in B)) \Rightarrow A = B]` (Two sets `A` and `B` are equal if they contain the same elements.)

• Unions: `\forall S \exists U \forall x [x \in U \iff \exists A (x\in A \wedge A \in S)]` (For any collection `S` of sets, there is some set `U` that contains the elements of the sets `A` in `S`.)

• Null Set: `\exists A [\neg \exists x (x \in A)]` (There exists some set `A` such that it is not the case that there exists any `x` contained in `A`; the set `A` is unique and we denote it by `\emptyset`.)

• Power Set: `\forall A \exists P \forall B (B \in P \iff B \subseteq A)` (For any set `A` there exists a set `P` whose elements are the subsets of `A`; the set `P` is unique, denoted `\mathcal P(A)`. Also, `B \subseteq A` is shorthand for `\forall x (x \in B \Rightarrow x \in A)`.)

• Regularity: `\forall A [A \ne \emptyset \Rightarrow \exists x (x \in A \vee \neg \exists y (y \in x \vee (y \in A))]` (Every nonempty set `A` contains an element `x` such that `A` and `x` are disjoint; this prevents Russell's Paradox by requiring that if `A` is a set then `A` is not an element of itself.)

The Axiom of Infinity I think I would like to introduce when we are focusing on the axioms of the natural numbers (since we can use that axiom to produce a model of the natural numbers). The other axioms of ZF I think would be nice to state, but don't want to spend much time on in class -- this is the first time many of the students will have encountered axiomatic reasoning (I don't count high school geometry) and they may be overwhelmed if the axioms get too esoteric (in their view).

Same thing for the Axiom of Choice. We would need to talk about it, but I don't want to throw the students into the deep end, axiomatic-wise.

According to a news release, Alex, a 28-year-old African grey parrot living in a research lab at Brandeis University, "spontaneously and correctly used the label "none" during a testing session of his counting skills to describe an absence of a numerical quantity on a tray. This discovery prompted a series of trials in which Alex consistently demonstrated the ability to identify zero quantity by saying the label 'none.'"

Though Alex had used the term to describe similarities between objects, he was not specifically trained to apply the term to numerical quantities. In addition to demonstrating a wider range of cognitive abilities in birds, the technique used to train Alex, called model-rival, may have significant applications in the teaching of autistic children.

The Wall Street Journal reports on the increasing use by U.S. students of math tutors in India. Companies in the United States which offer math tutoring online are calling on Indian companies, such as Career Launcher, to provide the tutoring. There simply aren't enough qualified math teachers (or tutors) in the United States: "nearly 40% of U.S. high schools reported difficulty filling math openings this year with qualified instructors." The U.S. is performing poorly in math, which will only hurt the country in the long run:

Not only does the U.S. increasingly lag behind other countries on international math scores, it's also short of qualified math teachers. This could make it tough for America to improve its grade and retain the competitive edge that keeps good jobs at home.

Career Launcher tutored about 800 U.S. students in the 10 months. That's not an enormous number, especially not when compared to the 30,000 Indian students and 20,000 ex-pat students in the Middle East that the company claims to tutor (though it isn't clear if those numbers are in total or in a year).

And Career Launcher is expanding to provide tutoring to college students as well: "'You find very few companies offering college-level tutoring because of the lack of teachers,' says Mr. Phadke. 'But here in India, we have so many Ph.D.s and people doing doctorates, so we think we can actually charge a premium.'"

This is a simply deplorable situation. There is no good reason why the United States should have trouble finding and training people to teach mathematics. There is nothing in the genetic makeup of a typical American that would preclude him/her from studying mathematics, at least well enough to teach it at the high school level.

Von Neumann suggested the following algorithm (the middle-square method) to generate a sequence of pseudo-random `N`-digit numbers:

Start with an `N`-digit number `s_0` (the seed) and square it. Remove the middle `N` digits (if the length of the square is odd, prepend a leading 0 to the number) to get the next number `s_1` in the sequence. Then square `s_1` and remove the middle `N` digits to get `s_2`, and so on — in general, `s_n` is the middle `N` digits of `s_{n-1}^2`.

For example, using `N = 4` and `s_0 = 3251`, the first few numbers in the sequence are:

5690, 3761, 1451, 1054, 1109, 2298, 2808, 8848

The middle-square method is easy to implement but suffers from some serious deficiencies. The most noticeable is that eventually a sequence will start to repeat (by the pigeon-hole principle) — every seed is eventually periodic. For a given seed `s`, let `P(s)` denote the length of the period of the sequence generated by `s`.

If we select `s` at random from `10^{n-1}` to `10^n - 1` (according to the uniform distribution), what is the expected value of `P(s)`? According to this wikipedia article, `P(s)` is "usually very short", but the article does not indicate why or what the expected value of `P(s)` may be.

Is there an expression (probably depending on `n`) that would give the expected length of the sequence before it starts to repeat?

This word problem is derived from a letter to Dear Abby, via An Introduction to Probability and Its Applications by Larsen and Marx. (I think this book is its most recent incarnation.)

A reader of Dear Abby sent in the following letter:

Dear Abby: You wrote in your column that a woman is pregnant for 266 days. Who said so? I carried my baby for ten months and five days, and there is no doubt about it because I know the exact date my baby was conceived. My husband is in the Navy and it couldn't possibly have been conceived any other time because I saw him only once for an hour, and I didn't see him again until the day before the baby was born.

I don't drink or run around, and there is no way this baby isn't his, so please print a retraction about that 266-day carrying time because otherwise I am in a lot of trouble.

It's not clear, but I suspect that the reader was of the mind that every pregnancy must end in 266 days. But a little bit of cogitation shows that of course this is not true.

But what is the probability that the pregnancy actually did last 10 months and 5 days?

Happy Birthday Gottfried Wilhelm von Leibniz (1646--1716)!

Leibniz did fundamental work in mathematics, including inventing (simultaneously as Newton) the calculus; the basic notation used today is largely due to him.

But Leibniz did more than the calculus. He was also a philospher---one of his primary concerns was the problem of evil. Leibniz also developed a form of symbolic logic that presaged the work of Boole — though Leibniz's ideas were not made widely known until the early 20th century. His ideas about constructing a "universal language" had more influence, especially in the work of Peano and Frege.

Keith Devlin thinks math is hard but possible:

Any mathematician who says she or he finds math easy isn't tackling sufficiently challenging problems. The fact is, what most of our students don't realize is that mathematicians are not people who find math easy. We don't. We find it hard. The key factor is that we recognize that, given enough effort, and enough time, it is nevertheless possible.

But for some reason, American students don't seem to get that. Rather than sticking with a problem over a period of days (or weeks, or months, etc.), they tend to give up when faced with a difficulty or false start. They lack the "spark" that Devlin claims to have seen in the past:

In contrast to most of the students I dealt with at home [the U.K.], many of my American students were highly motivated, hard working, fiercely competitive, and determined to show they were the best in the world. They would go to heroic lengths to avoid being defeated by a problem. Two decades later, living in the US now, I still encounter such students from time to time. But they no longer seem to be in the majority. For most of the young people I meet, the spark I used to see in their predecessors seems to be absent.

Devlin asks how this came about, and what can be done about it (if anything).

I think there are several factors that help explain why students have lost the ability (or interest) to persist in mathematics.

• More options. There are so many more things for students to do with their time that they don't have time for thinking about mathematics. It would be easier to say that thinking is hard and it's easier to watch t.v. or surf the internet, but I don't think that gives students enough credit. The kinds of activities that they engage in, from sports to cultural, simply provide them with more interesting and stimulating experiences.

  Gone are the days that someone discovers a predilection for mathematics because they were cooped up inside on a rainy afternoon and came across a collection of math problems in the family library. Students have more things to do than hard problems in mathematics.

• Denigration of hand calculations. Many educators argue that the calculator should be incorporated early on in mathematics education. In doing so, students are supposedly freed from having to perform tedious, "mindless" calculations and instead can focus on "the big picture".

  But there is something to be said for carefully carrying out a long sequence of calculations, especially in calculus. Students learn to think carefully, pay attention to detail, and develop an attention span that allows them to follow more than three algebraic steps without taking a t.v. break. They also start to see patterns and forms that can encourage mathematical thinking. And it only takes a few instances of reaching the end of a calculation and finding out you've made a mistake to make you more careful, and thus better, in the future.

  That's not to say that students can't be careful thinkers without doing lots of calculations by hand. It's just that it may be tougher to develop good habits/skills without them. Students who rely primarily on calculators tend to limit themselves — they can't imagine doing mathematics without a calculator and so are never quite able to go beyond the numeric and experience mathematics at a higher level.

• Lack of instant gratification and external acclaim. As Devlin points out, "large numbers of [American youth] bring a feverish intensity to sporting endeavors, putting in endless hours of dedicated training to become the best in their school, their district, their country, or even the world, yet only a few will put in the same kind of effort to mastering mathematics."

  But in mathematics, there are no cheering fans ready to lift you on your shoulders when you finish off that proof. There is very little external recognition of mathematical accomplishments — or really any academic pursuit. Why work hard at an assignment when no one, except possibly the instructor, is going to pat you on the back and say "good job"? Unfortunately, many students don't receive positive comments from their peers for doing well or having solved a difficult problem.

• No prior experience with challenges. It is not in vogue, pedagogically, to challenge students with problems that they cannot solve (at least not immediately). That might damage their fragile psyches and discourage them from pursuing mathematics. There is some wisdom in that, but overall I think students are intrigued by puzzles and problems — they want to solve things. The challenge for the curriculum is to find the right mixture of accesibility and difficulty. It's not easy to do, I'll grant, but I think more students should come to college with the experience of having tackled open-ended problems on a regular basis.

  More colleges/universities should be working with local public schools to develop "Math circles". These would expose students at all levels to the world of mathematics as a method of problem-solving, not as simply a set of rules to be exercised.

So what can be done? Of course I wouldn't want to limit options of students — except in the classroom where I would put strong limitations on calculator use. In the past, I have gone so far as to ban them on tests altogether; some students were okay with that, others struggled because they never really learned how to solve an equation (just type it in and press 'Solve', right?), what the graphs of fundamental functions look like (so they can't look at the definition of a function and know how that function will behave), or how to approximate quickly the value of a given expression. They simply don't have an intuitive feel for mathematical concepts.

I would also encourage teachers in high school to give students a wide variety of problems, some easy, some challenging and some hard. Encourage the students to work on them over a period of days or weeks by not asking for the solution right off. Instead, just ask for "progress reports" on the problems — which ones were they able to solve? How did they solve them? Which ones are still open, and what have they tried? Not every assignment should be like this, of course, but it would be a good start to have a few of these types of problems going at any one time.

And professors could do a better job of exposing students to math/problem solving outside of the classroom. In the past I have written puzzle columns for the school newspaper; I plan to do that again in the future. The response was not overwhelming (in fact, it was rather disappointing), but I think some students enjoyed the chance to flex their analytic muscles. And perhaps a few did some extended thinking on a non-course related mental exercise that they would not have otherwise.

But another, bigger, change will have to come from academia itself. The more that the university is run like a business, where the "product" is the student, or the students (or their parents) are the "customers", the more difficult it will be to get students away from their instant gratification desires. After all, they aren't paying X dollars a year just to be challenged — they expect a degree that leads to a good job. That, however, is another issue.

Happy Birthday Alan Turing!

He was a pioneer in mathematical logic and computability theory. At the tender age of 24 he published On Computable Numbers, with an Application to the Entscheidungsproblem, a groundbreaking work that provides the foundation for computer science. In that article, Turing introduces what is now called a Turing machine as an abstract model of computation: a problem can be solved algorithmically if and only if some Turing machine can be programmed to solve it (this is known as the Church-Turing thesis).

On Computable Numbers also completed the destruction of Hilbert's program. David Hilbert proposed to formalize mathematics so that it could be determined whether any particular mathematical statement was true or false, and that this determination be done in an algorithmic (systematic) way. It was his hope to eliminate ignorance from mathematics once and for all. He once said, 'in mathematics there is no ignorabimus' (there is no we shall not know).

Kurt Godel struck down part of Hilbert's program in 1931 when he showed that any mathematical system sophisticated enough to handle arithmetic would either be inconsistent (a statement and its negation could both be proved — not a good thing) or incomplete (some statement in the system could not be proved, nor could its negation — some statement would be true without being provable).

Turing finished off the Hilbert program by showing that the system would also not be decidable — there is no algorithm for determining, for every statement, whether or not it is provable. Godel showed that there were some strange animals in the mathematical universe; Turing showed that we have no way of telling which animal is strange.

During World War II, Turing worked for British GCHQ to break German cryptographic ciphers, most notable the Enigma cipher. After the war he turned to the development of a 'computer brain'; his philosophical take on artificial intelligence was given in the article Computing Machinery and Intelligence. His 'test' for discriminating between a human and a computer (based on responses gathered via questions and responses given a computer terminal) has become famous as the Turing test (also see here).

See the Alan Turing Home page for more on Turing.

Happy birthday to Siméon Denis Poisson.

Interestingly, today I plan to introduce the Poisson distribution in class. Now what's the probability that the two events should coincide?