Mathematical Survivor

Many people are familiar with the reality TV series Survivor, in which members of a group of castaways eliminate one individual after another until, eventually, only one remains.

A while ago, mathematician Steven Kahan, who has a longstanding interest in number theory and recreational mathematics, came up with a mathematical variant of this contest of survival. What's intriguing about his version is that the sole survivor is completely predictable from the start and that the survivor may not even have been in the original starting group!

Kahan described his scheme in the article "Mathematical Survivor," published in the February 2007 Math Horizons.

You start with a collection of two or more real numbers. Suppose you happen to start with the collection of integers {2, 4, 6, 8}. You delete any two numbers from the collection, replacing them with the product of the two numbers that you deleted, added to the sum of those two numbers. For example, you could delete 2 and 6 and insert (2 ✕ 6) + 2 + 6 = 20.

You then repeat the process, deleting two more numbers and inserting the appropriate term. So, if you delete 4 and 20 from the new collection {4, 8, 20}, you insert (4 ✕ 20) + 4 + 20 = 104 to produce the collection {8, 104}. In this example, the final step gives the result (8 ✕ 104) + 8 + 104 = 944.

Intriguingly, if you start by deleting any other pair of integers, you end up with the same survivor! The result is totally independent of the selection process throughout the procedure.

Kahan proved the following theorem: If S = {x₁, x₂, …, x_n} is a collection of n not necessarily distinct real numbers, where n is greater than or equal to 2, then the mathematical survivor of S is guaranteed to be

(x₁ + 1)(x₂ + 1) … (x_n + 1) – 1.

So, for the collection {2, 4, 6, 8}, the theorem predicts that the mathematical survivor will be (2 + 1)(4 + 1)(6 + 1)(8 + 1) – 1 = 944.

It's interesting to see what happens in certain special cases. What if the collection includes 0 or –1, for example?

In his article, Kahan gave one particularly harmonious example. If the original cast of numbers is {1, 1/2, 1/3, 1/4, …, 1/n}, the sole survivor is n.

Figure out what happens with the following original casts:

1. {1, 2, 3, …, n}
2. {a, a, a, …, a} (n copies)
3. {a – 1, a² – 1, a³ – 1, aⁿ – 1}

Who's the real mathematical survivor?

Lewis Carroll and His Telescoping Determinants

Doron Zeilberger of Rutgers University liked to describe Charles L. Dodgson (1832–1898) as perhaps the most famous mathematician in the world. But Dodgson isn't known for his mathematical work; he's famous as Lewis Carroll for writing Alice's Adventures in Wonderland, its sequel, and other fantasies.

Nonetheless, Dodgson can be credited with at least one curious mathematical advance, first published in 1866 in the Proceedings of the Royal Society of London. Indeed, Dodgson's ingenious method for computing the determinant of a square matrix deserves to be more widely known.

Given a 2 x 2 matrix A, its determinant (det A) is the difference between diametrically opposed entries in the matrix. In the matrix below, det A = ad – bc.


Determinants are useful in the analysis and solution of linear equations. For example, a system of linear equations has a unique solution if the determinant of the system's matrix is nonzero. In this case, the matrix is made up of the coefficients of the system's linear equations.

"Determinants emerged gradually during the 18th century through the theory of equations….," Adrian Rice and Eve Torrence noted in the March College Mathematics Journal. "By the 19th century, the subject had become a mathematical area of increasing significance." Carl Friedrich Gauss (1777–1855) was responsible for naming these mathematical objects determinants.

Although it's easy to calculate the determinant of a 2 x 2 matrix, the task gets increasingly tedious and time-consuming as the size of the matrix increases. The standard method involves breaking the n x n matrix down into a larger number of determinants of lower degree by taking the product of entries in designated rows and columns, then alternately adding and subtracting the results (see example, below).


Even in the case of a 5 x 5 matrix, the computation can get tedious. It involves five 4 x 4 determinants, which break down into twenty 3 x 3 determinants, or sixty 2 x 2 determinants, for a total of 120 multiplications (plus all the additions to get the final answer).

Dodgson came up with an alternative method that significantly simplifies the calculation. His "condensation" algorithm comes down to calculating nothing more than 2 x 2 determinants. In the 5 x 5 case, for example, Dodgson's method requires only 60 multiplications (plus a few divisions).

Here's an example of Dodgson's condensation method at work. You start with the following 4 x 4 matrix.


You condense this matrix into the following 3 x 3 matrix.


That matrix, in turn, condenses into the following 2 x 2 matrix.


You now divide each entry of this matrix by the corresponding term in the interior of the original matrix.


The determinant of this matrix is –42. When divided by –7 (the interior term in the 3 x 3 matrix), we get the correct answer of 6 for the determinant of the original matrix.

In effect, you start with an n x n matrix, then successively compute an (n – 1) x (n – 1) matrix, an (n – 2) x (n – 2) matrix, and so on, until you arrive at a 1 x 1 matrix whose sole entry is the determinant of the original n x n matrix. The rule for computing the smaller k x k matrix is to take k² 2 x 2 connected subdeterminants of the (k + 1) x (k + 1) matrix and divide them by the corresponding k² central entries of the (k + 2) x (k + 2) matrix.

In a 1999 article on the alternating sign matrix conjecture, David Bressoud and James Propp remarked that "the method is also useful for computer calculations, especially since it can be executed in parallel by many processors." At the same time, the division steps are a nice error check for hand calculations because the answers should all be integers for matrices with integer terms.

The only catch with using Dodgson's condensation algorithm is the requirement that there be no zeros in the interior of a matrix. Otherwise, some of the divisions would be undefined. One way around the problem is to rearrange the rows and columns of the matrix so that zeros don't occur in the interior, but that isn't always possible.

Dodgson also described his condensation method in the only textbook that he ever wrote: An Elementary Treatise on Determinants (with their application to simultaneous linear equations and algebraical geometry).

"Dodgson's Treatise on Determinants was not a bestseller, not even selling enough copies to warrant a second edition," Rice and Torrence wrote. "The limited availability of the book together with the obscurity of the text itself made it highly unlikely that Dodgson's algorithm would catch on."

"Nevertheless," they added, "when teaching linear algebra, we have consistently found Dodgson's method to be the most popular method among our students for evaluating determinants. Curious!"

References:

Amdeberhan, T., and D. Zeilberger. 2001. Determinants through the looking glass. Advances in Applied Mathematics 27(August):225-230.

Bressoud, D. 1999. Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture. Mathematical Association of America.

Bressoud, D., and J. Propp. 1999. How the Alternating Sign Matrix Conjecture Was Solved. Notices of the American Mathematical Society 46(June/July):637-646.

Dodgson, C.L. 1866. Condensation of determinants, being a new and brief method for comupting their arithmetical values. Proceedings of the Royal Society of London 15:150-155,

Rice, A., and E. Torrence. 2007. "Shutting up like a telescope": Lewis Carroll's "curious" condensation method for evaluating determinants. College Mathematics Journal 38(March):85-105.

Zeilberger, D. 1997. Dodgson's determinant-evaluation rule proved by two-timing men and women. Electronic Journal of Combinatorics 4(No. 2):R22.

______. 1996. Reverend Charles to the aid of Major Percy and Fields-Medalist Enrico. American Mathematical Monthly 103(July):501-502.

Euler's Beauties

Those who assert that the mathematical sciences say nothing of the beautiful are in error. The chief forms of beauty are order, commensurability, and precision.—Aristotle, Metaphysics, XIII 3.107b

In 1988, David Wells surveyed readers of the Mathematical Intelligencer to get a sense of what mathematicians consider to be beautiful in their field. He provided a ballot listing 24 famous theorems. The results were published in 1990. Leonhard Euler (1707–1783) was responsible for three of the top five choices.

The readers ranked Euler's relation linking e, pi (π), and i as the most beautiful equation in mathematics.


It was Euler himself who introduced the constant 2.718281828459… to the mathematical world as the base of natural logarithms and designated it, "for the sake of brevity," e. Euler's relation follows from his discovery of the following remarkable identity (for any real x), when x = π.


Of course, Euler's relation can be rewritten as e^iπ + 1 = 0.

"As math professors are fond of observing, this equation assembles the five most important constants in mathematics," William Dunham pointed out in his book Euler: The Master of Us All.

• 0—the additive identity.
• 1—the multiplicative identity.
• π—the circular constant.
• e—the base of the natural logarithms.
• i—the imaginary unit.

"That these five superstar numbers should be related in so simple a manner is truly astonishing," Dunham wrote. "That Euler recognized such a relationship is a tribute to his mathematical power."

Of the world's most beautiful theorems, Euler's formula for a polyhedron, tying together the number of vertices (V), edges (E), and faces (F), ranked second: V + F = E + 2.

Euler's paper on this relation played a central role in early combinatorial topology.

Coming in fifth was the sum of an infinite series.


This equation represents one of Euler's earlier triumphs. In the previous century, a number of mathematicians had tried and failed to determine the exact value of this infinite series. Numerical approximations had shown the sum to be around 8/5, but the exact answer proved elusive.

"Well into the next century the problem remained unsolved, and anyone capable of summing the series was certain to make a major splash," Dunham recounted. "When it happened in 1735, the splash was Euler's. The answer was not only a mathematical tour de force but a genuine surprise…. This highly non-intuitive result made the solution all the more spectacular and its solver all the more famous."

What two theorems kept Euler from capturing the top three spots in the survey? One was Euclid's theorem that the number of primes is infinite. The other was the existence of five regular polyhedra (Platonic solids).

Levers, Dials, and Mystic Math

Solving a video or computer game's puzzles can lead to adventure—and mathematical discovery.

Near the beginning of the game Myst, a player encounters a contraption that includes three levers and a tower of three dials, each one reading 3. Manipulating the levers reveals that each of the three numbers is one face of a three-sided block. Rotating a block unveils the other faces, numbered 1 and 2.

Let's label the levers A, B, and C. With a little experimentation, you soon discover that pulling lever A leaves the top block alone and rotates the middle and bottom blocks to show the next face. So, if you start with faces 1, 2, 3 (from top to bottom), the new configuration after pulling lever A would be 1, 3, 1.

Pulling lever B leaves the bottom dial alone and rotates the top two dials. Lever C simply resets the blocks to their original 3, 3, 3 configuration.

If you've been paying attention to other clues in the game, you realize that your task is use the levers to rotate the blocks until they read 2, 2, 1 instead of 3, 3, 3.

To figure out how to accomplish this task most efficiently, it helps to delve into the realm of modular arithmetic, groups, and linear algebra.

As mathematician and self-described "gaming geek" Jessica K. Sklar put it, the puzzle's numbers can be regarded as integers modulo 3 (0, 1, 2), where a face's 3 is identified with 0 in the set Z₃. With three blocks, you have a set in which each element is a possible configuration of the blocks. And the contraption's levers can be regarded as actions on the group of these elements.

Sklar described her analysis of the Myst puzzle (and several more puzzles from other games) in an article in the December 2006 Mathematics Magazine.

So, starting with the element (0, 0, 0), you want to pull each of levers A and B a particular number of times to get the element (2, 2, 1). In effect, you're interested in writing (2, 2, 1) as a linear combination: (2, 2, 1) = a(0, 1, 1) + b(1, 1, 0), where a and b are the number of pulls required for each respective lever.

But there's no solution for a and b to the resulting system of congruences.

To solve the puzzle, you need an additional trick. It turns out that holding down lever A or B a little longer after the initial pull increments the middle number. So you're actually looking for (2, 2, 1) = a(0, 1, 1) + b(1, 1, 0) + c(0, 1, 0), where c represents the number of extra "beats" lever A or B must be held down.

Now, the system of congruences has a solution: a = 1, b = 2, c = 2. You solve the puzzle by pulling lever A once, lever B twice, and holding lever B down after its second pull just long enough to add (0, 1, 0) twice.

"And voilá, we hear a grinding noise and the gear at the bottom of the contraption opens," Sklar wrote. "Moreover, we have now gained access to a book that will allow us to travel a different world. Nice, huh?"

"One of the most beautiful things about computer games," she added, "is that they allow [us] to travel to worlds to which we can't physically go in real life: including mathematical worlds."