The classic bit about how to catch a lion
To: humourous-backbone@rascal.ics.utexas.edu
Subject: [Rich Kulawiec: GSP Digest #186]
Date: Tue, 25 Jul 89 00:34:23 EST
From: Gene Spafford <spaf@cs.purdue.edu>
The classic bit about how to catch a lion. Added to the end are some
new ways for physicists & computer scientists. I especially like
Dijkstra's method...
--spaf
------- Forwarded Message
==========
Item 3:
==========
From: ji@walkuere.altair.fr (John Ioannidis)
Date: 19 Jul 89 10:30:04 GMT
Subject: how to catch a lion
I found this some time ago in my mailbox. I'm not certain of its
origins, but it's a good one. It looks like something that might have
appeared in the JIR (Journal of Irreproducible Results) but I don't
have all the back issues with me to check.
A Contribution to the Mathematical Theory of Big Game Hunting
Problem: To Catch a Lion in the Sahara Desert.
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. We then performe an inversion with respect to the cage. Then
the lion is inside the cage, and we are outside.
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
interiour 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.
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. We silently approach the lion in
this sequence, carrying the proper equipment with us.
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].)
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 execise 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 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.4 A 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.
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 itsl 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 investigastions 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 esnures 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.)
Subject: [Rich Kulawiec: GSP Digest #186]
Date: Tue, 25 Jul 89 00:34:23 EST
From: Gene Spafford <spaf@cs.purdue.edu>
The classic bit about how to catch a lion. Added to the end are some
new ways for physicists & computer scientists. I especially like
Dijkstra's method...
--spaf
------- Forwarded Message
==========
Item 3:
==========
From: ji@walkuere.altair.fr (John Ioannidis)
Date: 19 Jul 89 10:30:04 GMT
Subject: how to catch a lion
I found this some time ago in my mailbox. I'm not certain of its
origins, but it's a good one. It looks like something that might have
appeared in the JIR (Journal of Irreproducible Results) but I don't
have all the back issues with me to check.
A Contribution to the Mathematical Theory of Big Game Hunting
Problem: To Catch a Lion in the Sahara Desert.
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. We then performe an inversion with respect to the cage. Then
the lion is inside the cage, and we are outside.
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
interiour 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.
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. We silently approach the lion in
this sequence, carrying the proper equipment with us.
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].)
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 execise 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 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.4 A 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.
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 itsl 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 investigastions 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 esnures 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.)
Comments
Post a Comment