Hundred-Dollar, Hundred-Digit Challenge Problems

The hundred-dollar, hundred-digits challenge problems are a set of ten problems in numerical analysis published in the January/February 2002 issue of SIAM News (http://www.siam.org/siamnews/01-02/challenge.pdf). Nick Trefethen, the proposer of the problems, offered a $100 prize to the person or group obtaining the largest number of correct digits (up to a maximum of 10) for these problems by May 20, 2002. Trefethen underestimated the ingenuity of problem solvers, and 20 independent teams obtained 10 correct digits for all 10 problems. After an anonymous donor stepped in to help defray the larger than anticipated payoffs, prize checks went out to all winners by December 2002.

The problems posed were the following.

1. What is ? This problem is difficult to integrate numerically in its original form because of the strong oscillations near the origin. However, by making the substitution , it can be transformed to the integral

which converges fairly rapidly using oscillatory numerical integration techniques.

Boersma and Jansen used contour integration to transform the problem into

each of which converge quite rapidly.

Laurie noted that the integral can be written

where is any contour from 0 to 1 such that no singularities lie in the region defined by and the line from 0 to 1 (Wagon 2004). For example, is such a contour.

The problem can also be solved by writing the integrand as the asymptotic series

and integrating term by term to obtain the strongly oscillatory sum

Amazingly, this sum can be regularized using Wynn's epsilon method using a suitable number of terms and extrapolation degree to obtain around 7 correct digits.

2. A photon moving at speed 1 in the - plane starts at at heading due east. Around every integer lattice point in the plane, a circular mirror of radius has been erected. How far from the origin is the photon at ?

3. The infinite matrix with entries , , , , , , etc., is a bounded operator on . What is ? This problem is equivalent to finding the largest singular value of the infinite matrix with entries

i.e., the matrix

4. What is the global minimum of the function

(Cf. Bailey et al. 2007, pp. 12 and 219; Kampas and Pintér 2006). This problem can be solved in a one-liner in the Wolfram Language.

  NMinimize[f[x, y], {x, y}, Method -> {"RandomSearch",
    "SearchPoints" -> 700}, WorkingPrecision -> 20]

5. Let , where is the gamma function, and let be the cubic polynomial that best approximates on the unit disk in the supremum norm . What is ?

6. A flea starts at on the infinite two-dimensional integer lattice and executes a biased random walk: At each step it hops north or south with probability 1/4, east with probability , and west with probability . The probability that the flea returns to (0, 0) sometime during its wanderings is 1/2. What is ?

The solution is given by solving

where is a complete elliptic integral of the first kind, Equivalently, it is given by the root of

where is the arithmetic-geometric mean.

It is also given by solving , where

(Bornemann 2002).

7. Let be the matrix whose entries are zero everywhere except for the primes 2, 3, 5, 7, ..., 224737 along the main diagonal and the number 1 in all the positions with , 2, 4, 8, ..., 16384. What is the (1, 1) entry of ?

This problem can be solved exactly, yielding a rational number in which the numerator and denominator each have digits:

(Wagon 2004).

8. A square plate is at temperature . At time , the temperature is increased to along one of the four sides while being held at along the other three sides, and heat then flows into the plate according to . When does the temperature reach at the center of the plate?

An expression that gives 10 correct digits is given by

where is a polynomial root. Getting higher accuracy requires using more terms of the series.

9. The integral depends on the parameter . What is the value at which achieves its maximum?

By making the change of variables , the integral can be transformed to

By plotting, the maximum can be seen to occur near , and standard root-finding techniques can be used to determine it to high-precision.

10. A particle at the center of a rectangle undergoes Brownian motion (i.e., 2D random walk with infinitesimal step lengths) till it hits the boundary. What is the probability that it hits at one of the ends rather than at one of the sides? Amazingly, this problem has a closed-form solution, given by

where is the elliptic lambda function (cf. Bailey et al. 2007, p. 48).

The solutions are summarized in the following table.