obtain a third number. Continue this way until
the chain of numbers obtained this way ends
on a number that repeats. This repeating number, in every case, is the number four.
As every number between one and 100 can be written
in 12 or fewer letters, the second number obtained will
lie between three and 12. One checks, by brute force,
that each of these numbers eventually leads to the number four.
At present, the brute-force method is the only
known technique guaranteed to yield an optimal solution to the famous TRAVELING-SALESMAN PROBLEM.
This problem is of significant practical importance.
Unfortunately, even with the fastest computers of
today, the brute-force approach cannot be carried out
in any feasible amount of time.
The famous FOUR-COLOR THEOREM was solved in
the 1970s by reducing the problem to a finite, but
extraordinarily large, number of individual cases that
were checked on a computer by brute force.
See also GOLDBACH’S CONJECTURE.
Buffon needle problem (Buffon-Laplace problem)
In 1733 French naturalist Georges Buffon proposed
the following problem, now known as the Buffon needle problem:
A needle one inch long is tossed at random
onto a floor made of boards one inch wide.
What is the probability that the needle lands
crossing one of the cracks?
One can answer the puzzle as follows:
Suppose that the needle lands with lowest end a
distance x from a crack. Note that 0 ≤ x ≤ 1.
In the diagram we see that if the needle lands within
an angle as indicated by either sector labeled θ, then it
will not fall across the upper crack, but it will do so if
instead it lands in the sector of angle π –2θ. Thus the
probability that the needle will fall across the crack,
given that it lands a distance x units below a crack, is
. Summing, that is, integrating,
over all possible values of x gives us the total probability P we seek:
In principle, this problem provides an experimental
method for computing PI: simply toss a needle onto the
floor a large number of times, say 10,000, and count the
proportion that land across a crack. This proportion
should be very close to the value . In practice, however,
this turns out to be a very tedious approach.
See also MONTE CARLO METHOD.
2
π
P
P dx
x dx
xdx
x
x
x
x
=
=
−
= −
= −
+ −
= −
−
=
−
−
−
∫
∫
∫
1
2
1
2
1
2
1
1
2
2
1
2
1
1
0
1
0
1
0
1
1
2
0
1
π
π
π
π
π
π
sin
sin
sin
P
x
x =
−
= −
−
π
θ
π
π
2
1
2
1
sin
Buffon needle problem 55
Solving the Buffon needle problem
the chain of numbers obtained this way ends
on a number that repeats. This repeating number, in every case, is the number four.
As every number between one and 100 can be written
in 12 or fewer letters, the second number obtained will
lie between three and 12. One checks, by brute force,
that each of these numbers eventually leads to the number four.
At present, the brute-force method is the only
known technique guaranteed to yield an optimal solution to the famous TRAVELING-SALESMAN PROBLEM.
This problem is of significant practical importance.
Unfortunately, even with the fastest computers of
today, the brute-force approach cannot be carried out
in any feasible amount of time.
The famous FOUR-COLOR THEOREM was solved in
the 1970s by reducing the problem to a finite, but
extraordinarily large, number of individual cases that
were checked on a computer by brute force.
See also GOLDBACH’S CONJECTURE.
Buffon needle problem (Buffon-Laplace problem)
In 1733 French naturalist Georges Buffon proposed
the following problem, now known as the Buffon needle problem:
A needle one inch long is tossed at random
onto a floor made of boards one inch wide.
What is the probability that the needle lands
crossing one of the cracks?
One can answer the puzzle as follows:
Suppose that the needle lands with lowest end a
distance x from a crack. Note that 0 ≤ x ≤ 1.
In the diagram we see that if the needle lands within
an angle as indicated by either sector labeled θ, then it
will not fall across the upper crack, but it will do so if
instead it lands in the sector of angle π –2θ. Thus the
probability that the needle will fall across the crack,
given that it lands a distance x units below a crack, is
. Summing, that is, integrating,
over all possible values of x gives us the total probability P we seek:
In principle, this problem provides an experimental
method for computing PI: simply toss a needle onto the
floor a large number of times, say 10,000, and count the
proportion that land across a crack. This proportion
should be very close to the value . In practice, however,
this turns out to be a very tedious approach.
See also MONTE CARLO METHOD.
2
π
P
P dx
x dx
xdx
x
x
x
x
=
=
−
= −
= −
+ −
= −
−
=
−
−
−
∫
∫
∫
1
2
1
2
1
2
1
1
2
2
1
2
1
1
0
1
0
1
0
1
1
2
0
1
π
π
π
π
π
π
sin
sin
sin
P
x
x =
−
= −
−
π
θ
π
π
2
1
2
1
sin
Buffon needle problem 55
Solving the Buffon needle problem