Buffon needle problem 55

Solving the Buffon needle problem

obtain a third number. Continue this way until

the chain of numbers obtained this way ends

on a number that repeats. This repeating num-

ber, 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 num-

ber four.

At present, the brute-force method is the only

known technique guaranteed to yield an optimal solu-

tion 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 G

OLDBACH

’

S CONJECTURE

.

Buffon needle problem (Buffon-Laplace problem)

In 1733 French naturalist Georges Buffon proposed

the following problem, now known as the Buffon nee-

dle 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 xfrom 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 xunits below a crack, is

. Summing, that is, integrating,

over all possible values of xgives us the total probabil-

ity Pwe 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 M

ONTE

C

ARLO METHOD

.

2

π