Problem: To Catch a Lion in the Sahara Desert.
(Hunting lions in Africa was originally published as "A contribution
to the mathematical theory of big game hunting" in the American
Mathematical Monthly in 1938 by "H. Petard, of Princeton NJ" [actually
the late Ralph Boas].  It has been reprinted several times.
This is a hugely extended version with contributions from the net.

1. Mathematical Methods

1.1 The Hilbert (axiomatic) method

We place a locked cage onto a given point in the desert.  After that
we introduce the following logical system:
   Axiom 1: The set of lions in the Sahara is not empty.
   Axiom 2: If there exists a lion in the Sahara, then there exists a
            lion in the cage.
   Procedure: If P is a theorem, and if the following is holds:
              "P implies Q", then Q is a theorem.
   Theorem 1: There exists a lion in the cage.

1.2 The geometrical inversion method

We place a spherical cage in the desert, enter it and lock it from
inside.
Case 1: The lion is inside the cage. This case is trivial.
Case 2: The lion is outside the cage. We then perform an inversion
with respect to the cage.  Then the lion is inside the cage, and we
are outside.
Warning: With this method, it is important not to stand in the middle
of the cage, as one will disappear in the infinite.

1.3 The projective geometry method

Without loss of generality, we can view the desert as a plane surface.
We project the surface onto a line and afterwards the line onto an
interior point of the cage. Thereby the lion is mapped onto that same
point.

1.4 The Bolzano-Weierstrass method

Divide the desert by a line running from north to south.  The lion is
then either in the eastern or in the western part.  Let's assume it is
in the eastern part.  Divide this part by a line running from east to
west.  The lion is either in the northern or in the southern part.
Let's assume it is in the northern part.  We can continue this process
arbitrarily and thereby constructing with each step an increasingly
narrow fence around the selected area.  The diameter of the chosen
partitions converges to zero so that the lion is caged into a fence of
arbitrarily small diameter.
Warning: With this method take care that the beautifull skin of the
lion is not damaged.

1.5 The set theoretical method

We observe that the desert is a separable space.  It therefore
contains an enumerable dense set of points which constitutes a
sequence with the lion as its limit. With a cage on our backs,
we jump from point to point of this sequence an so approach the lion
as near as we like.

1.6 The Peano method

In the usual way construct a curve containing every point in the
desert.  It has been proven [1] that such a curve can be traversed in
arbitrarily short time.  Now we traverse the curve, carrying a spear,
in a time less than what it takes the lion to move a distance equal to
its own length.

1.7 A topological method

We observe that the lion possesses the topological gender of a torus.
We embed the desert in a four dimensional space.  Then it is possible
to apply a deformation [2] of such a kind that the lion when returning
to the three dimensional space is all tied up in itself.  It is then
completely helpless.

1.8 The Cauchy method

We examine a lion-valued function f(z). Be \zeta the cage.  Consider
the integral

          1    [   f(z)
       ------- I --------- dz
       2 \pi i ] z - \zeta

               C

where C represents the boundary of the desert.  Its value is f(zeta),
i.e. there is a lion in the cage [3].

1.9 The Wiener-Tauber method

We obtain a tame lion, L_0, from the class L(-\infinity,\infinity),
whose fourier transform vanishes nowhere.  We put this lion somewhere
in the desert.  L_0 then converges toward our cage.  According to the
general Wiener-Tauner theorem [4] every other lion L will converge
toward the same cage.  (Alternatively we can approximate L arbitrarily
close by translating L_0 through the desert [5].)

From: chohn@vub.ac.be (Ohn Christian)

1.10 The Mathematical Induction method

Consider, for each n, the following statement:
    P(n) : 'It is possible to catch n lions in the desert.'
Of course, P(n) is true for large enough n, because the lions are then
so tightly packed together that it is easy to catch them. But now,
P(n) implies P(n-1) ('cause if you catch some lions, you can always
release one of them). Hence, P(1) is true.

1.11 The Banachsche or iterative method

Let f be a contraction of the Sahara in it with contraction point x_0.
On this point we put the cage. By successive iteration W(n+1)= f(W(n)),
n=,1,2,..... (W(0)=Sahara) the Sahara will be contracted to X_0. In this
way the lion will get in the cage.

1.12 The Kalra Method

Make a list of the lion's whereabouts.  Classify them into different fuzzy
sets. The lion will get confused and fall into your trap.

1.13 The Cartesian method

Take the origin as close as possible to the lion. Then perform rotation
operation again and again. Initially, the lion will feel dizzy. Finally it
will fall down.

1.14 The Inductive Method

 Initial Condition: If you center a large cage on any one
grain of sand, and a lion is on or close to the grain of sand. then
he will be trapped by the cage. By close we mean within epsilon
grains of sand. Given a cage the size of 2 * (size of lion *
epsilon) it works.
 First Hypothesis: Given the first grain of sand in the
desert, if the lion is standing on it you will trap him.

       Proof: Given by the initial condition.

       Induction Hypothesis:  Assume that a lion is on a grain

of sand n, and is trappable. Now, for grain n+1 (assume all grains of sand
are ordered, inorder) n+1 is close to n, hence n is close to n+1. If the
lion is on grain n, and is trappable; then he is close to n+1, and by the
above condition, trappable.  Hence, no matter where the lions are if you
drop a cage centered on a piece of sand you will catch a lion.

1.15 The Integro-Differential Method

Integrate the Sahara over its entire surface. The lion is now somewhere in
the result. Differentiate the result w.r.t the earth's rotation. The
resulting value is zero, and the lion is no more.

From: David J Corbett djc123@student.canterbury.ac.nz
1.16  Group theory method
Note that "dog in lace" is an anagram of "caged lion".
Therefore, apply the appropriate permutation from S9 on a dog in lace to
obtain a caged lion.  The matter of obtaining a dog in lace is left to
the reader.

2 Theoretical Physics Methods

2.1 The Dirac method

We assert that wild lions can ipso facto not be observed in the Sahara
desert.  Therefore, if there are any lions at all in the desert, they
are tame.  We leave catching a tame lion as an exercise to the reader.

2.2 The Schroedinger method

At every instant there is a non-zero probability of the lion being in
the cage.  Sit and wait.

2.3 The Quantum Measurement Method

We assume that the sex of the lion is _ab initio_ indeterminate.  The
wave function for the lion is hence a superposition of the gender
eigenstate for a lion and that for a lioness.  We lay these eigenstates
out flat on the ground and orthogonal to each other.  Since the (male)
lion has a distinctive mane, the measurement of sex can safely be made
from a distance, using binoculars.  The lion then collapses into one of
the eigenstates, which is rolled up and placed inside the cage.

2.4 The nuclear physics method

Insert a tame lion into the cage and apply a Majorana exchange
operator [6] on it and a wild lion.

As a variant let us assume that we would like to catch (for argument's
sake) a male lion.  We insert a tame female lion into the cage and
apply the Heisenberg exchange operator [7], exchanging spins.

2.5 The Newton gravitation method

Cage and lion attract each other with the gravitation force. We neglect
the friction. This way the lion will arive sooner or later in the cage.

2.6 The Newton third law method

Let the lion catch you (let's assume you remain alive here).  For every
action there is an equal and opposite reaction.  Therefore, you will have
captured the lion.

2.7 The Special relativistic method

One moves over the desert with light velocity. The relativistic length
contraction makes the lion flat as paper. One takes it, rolls it up and
puts a rubber band around the lion.

2.8 The Special relativistic method (method 2)

Run in the direction opposite to that of the lion. The relative velocity
makes the lion run faster and hence he feels heavier and gets tired.

2.9 The general relativistic method

All over the desert we distribute lion bait containing large amounts
of the companion star of Sirius.  After enough of the bait has been
eaten we send a beam of light through the desert.  This will curl
around the lion so it gets all confused and can be approached without
danger.

2.10 The Heisenberg method

Position and Velocity from a moving lion can not be measure at the same
time. As moving lions have no physical meaningfull position in the desert,
one can not catch them. The lion hunt can therefore be limited to
resting lions. The catching of a resting, not moving lion is left as
an exercise for the reader.

2.11 The Schroedinger cat method
From: Alain Gottcheiner agot@ulb.ac.be

I'm no specialist of quantum mechanics, so it's possible that I've
overlooked something important, but the following method should work :

1) Note that a lion is nothing else than some big cat.

2) Pour some contact poison that's lethal to lions over the Sahara.

3) Thereafter, either the lion is dead, or it isn't.  So look at the Sahara
to reduce the lion's state to either dead or alive.  If he's dead, you will
have no problems picking him and putting him in the cage. If it is not,
proceed back to step 2.

4) Since the probability (P) of this trick working is not 0, and since
[limit, on n going to infinite, of 1 minus P to the nth, is O] you've got
1OO% probability of some iteration of the process bringing up the result
you wanted.

There could just be a snag about the method : if the lion is dead,
obvioulsy he's not moving anymore, and his momentum is known to be nought,
so how are you going to measure where he is lying ?


2.appendix The Heisenberg constriction

You will disturb the lion when you observe it before capturing.
So keep your eyes closed.

3 Experimental Physics Methods

3.1 The thermodynamics method

We construct a semi-permeable membrane which lets everything but lions
pass through.  This we drag across the desert.

3.2 The atomic fission method

We irradiate the desert with slow neutrons.  The lion becomes
radioactive and starts to disintegrate. Once the disintegration
process is progressed far enough the lion will be unable to resist.

3.3 The magneto-optical method

We plant a large, lense shaped field with cat mint (nepeta cataria)
such that its axis is parallel to the direction of the horizontal
component of the earth's magnetic field.  We put the cage in one of the
field's foci . Throughout the desert we distribute large amounts of
magnetized spinach (spinacia oleracea) which has, as everybody knows,
a high iron content.  The spinach is eaten by vegetarian desert
inhabitants which in turn are eaten by the lions.  Afterwards the
lions are oriented parallel to the earth's magnetic field and the
resulting lion beam is focussed on the cage by the cat mint lense.

[1] After Hilbert, cf. E. W. Hobson, "The Theory of Functions of a Real
    Variable and the Theory of Fourier's Series" (1927), vol. 1, pp 456-457
[2] H. Seifert and W. Threlfall, "Lehrbuch der Topologie" (1934), pp 2-3
[3] According to the Picard theorem (W. F. Osgood, Lehrbuch der
    Funktionentheorie, vol 1 (1928), p 178) it is possible to catch every
    lion except for at most one.
[4] N. Wiener, "The Fourier Integral and Certain of its Applications" (1933),
    pp 73-74
[5] N. Wiener, ibid, p 89
[6] cf e.g. H. A. Bethe and R. F. Bacher, "Reviews of Modern Physics", 8
    (1936), pp 82-229, esp. pp 106-107
[7] ibid

4 Contributions from Computer Science.

4.1 The search method

We assume that the lion is most likely to be found in the direction to
the north of the point where we are standing.  Therefore the REAL
problem we have is that of speed, since we are only using a PC to
solve the problem.

4.2 The parallel search method.

By using parallelism we will be able to search in the direction to the
north much faster than earlier.

4.3 The Monte-Carlo method.

We pick a random number indexing the space we search.  By excluding
neighboring points in the search, we can drastically reduce the number
of points we need to consider.  The lion will according to probability
appear sooner or later.

4.4 The practical approach.

We see a rabbit very close to us.  Since it is already dead, it is
particularly easy to catch.  We therefore catch it and call it a lion.

4.5 The common language approach.

If only everyone used ADA/Common Lisp/Prolog, this problem would be
trivial to solve.

4.6 The standard approach.

We know what a Lion is from ISO 4711/X.123.  Since CCITT have specified
a Lion to be a particular option of a cat we will have to wait for a
harmonized standard to appear.  $20,000,000 have been funded for
initial investigations into this standard development.

4.7 Linear search.

Stand in the top left hand corner of the Sahara Desert.  Take one step
east.  Repeat until you have found the lion, or you reach the right
hand edge.  If you reach the right hand edge, take one step
southwards, and proceed towards the left hand edge.  When you finally
reach the lion, put it the cage.  If the lion should happen to eat you
before you manage to get it in the cage, press the reset button, and
try again.

4.8 The Dijkstra approach:

The way the problem reached me was: catch a wild lion in the Sahara
Desert. Another way of stating the problem is:

       Axiom 1: Sahara elem deserts
       Axiom 2: Lion elem Sahara
       Axiom 3: NOT(Lion elem cage)

We observe the following invariant:

       P1:     C(L) v not(C(L))

where C(L) means: the value of "L" is in the cage.

Establishing C initially is trivially accomplished with the statement

       ;cage := {}

Note 0:
This is easily implemented by opening the door to the cage and shaking
out any lions that happen to be there initially.
(End of note 0.)

The obvious program structure is then:

       ;cage:={}
       ;do NOT (C(L)) ->
               ;"approach lion under invariance of P1"
               ;if P(L) ->
                       ;"insert lion in cage"
                [] not P(L) ->
                       ;skip
               ;fi
       ;od

where P(L) means: the value of L is within arm's reach.

Note 1:
Axiom 2 ensures that the loop terminates.
(End of note 1.)

Exercise 0:
Refine the step "Approach lion under invariance of P1".
(End of exercise 0.)

Note 2:
The program is robust in the sense that it will lead to
abortion if the value of L is "lioness".
(End of note 2.)

Remark 0: This may be a new sense of the word "robust" for you.
(End of remark 0.)

Note 3:

From observation we can see that the above program leads to the
desired goal. It goes without saying that we therefore do not have to
run it.
(End of note 3.)
(End of approach.)

4.9 The Linked List Method

Make a linked list of all objects in the desert. Then delete the pointers
on either side of the lion.(Make sure you are not AFTER the lion.)

4.10 The Automata Method

Use a Non-Deterministic Finite Automaton with epsilon moves from all states
to the final state, and no moves from the final state. The lion will soon
enter the final state and be trapped.

4.11 The Divide And Conqure Method (by recursion)

Divide the desert in half. Repeat the process until you have the lion, a
grain of sand, or some other object that cannot be divided without blood
shed. You have the lion. The order of this method = O(insane). (Where
sanity is anything reasonable.)

5 Other Methods

5.1 The Time-Cop Method

Use a time-machine and take the entire Sahara back a few years in time. The
lion is just a cub now, and all you need is a mouse-trap.

5.2 The Shakespeare Method

Hold the lion still for a moment (I don't care how you do it), and recite
Shakespeare`s Hamlet to it. The lion will change from 'To be' to
'Not-to-be'.

5.3 The Pentagon method.

Construct a safe, secure cage and leave the door open.  Alternate massive
B-52 strikes across the Sahara desert with subtle propaganda campaigns
emphasizing the safety and security of your cage.  When a lion enters the
cage, close and lock the door.

5.4 The supply-side method.

Distribute vast quantities of lion food and eliminate all threats to the
lion population.  Put a cage in the desert and wait for the explosive
growth of the lion population to force a lion into the cage.

5.5 The Marxist-Leninist method.

Indoctrinate the gazelle population of the Sahara desert in dialectical
materialism.  Disguise your cage as a re-education camp for capitalist
lions, and the gazelles will bring you all the lions you need.

From: David J Corbett djc123@student.canterbury.ac.nz
5.6 The crossword method
"1 Across  Dog in lace, confused, becomes trapped Leo (5,4)", to which
the solution is "caged lion".

For other articles, see also:

A Random Walk in Science - R.L. Weber and E. Mendoza
More Random Walks In Science - R.L. Weber and E. Mendoza
In Mathematical Circles (2 volumes) - Howard Eves
Mathematical Circles Revisited - Howard Eves
Mathematical Circles Squared - Howard Eves
Fantasia Mathematica - Clifton Fadiman
The Mathematical Magpi - Clifton Fadiman
Seven Years of Manifold - Jaworski
The Best of the Journal of Irreproducible Results - George H. Scheer
Mathematics Made Difficult - Linderholm
A Stress-Analysis of a Strapless Evening Gown - Robert Baker
The Worm-Runners Digest
Knuth's April 1984 CACM article on The Space Complexity of Songs
Stolfi and ?? SIGACT article on Pessimal Algorithms and Simplexity Analysis