March 23, 2007

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 = {x1, x2, …, xn} 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

(x1 + 1)(x2 + 1) … (xn + 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, a2 – 1, a3 – 1, an – 1}
Who's the real mathematical survivor?

No comments: