Consider an infinite square lattice of points with
integer coordinates on a plane.
If two
lattice points are chosen at random,
what is the probability that the
straight-line segment joining the two
lattice points will not pass through
any other lattice points?
**** Adapted from a problem appearing in the 2005 Fall collection of BENT, Brain Ticklers.
Charlie's solution is not really a solution as he never actually provided any details of his research - just handwaived it with a dumb program estimate. And I'm surprised and disappointed KS accepted it as official so quickly.
So let's give this problem a proper discussion and not just some handwavy excuse.
Without loss of generality, place one point at the origin and the other point at (x,y). Then the segment will not cross any additional lattice points if x and y are coprime.
Consider a prime p, x and y are coprime of not both are a multiple of p, which on an arbitrary large interval is probability 1-1/p^2.
Then multiply over all primes to get the infinite product:
(1-1/2^2)*(1-1/3^2)*(1-1/5^2)*(1-1/7^2)*.....
Now I will generalize a bit and replace the exponents of 2 with s, and take the reciprocals of everything. Then we get the Euler Product.
E(s) = (1/(1-1/2^s))*(1/(1-1/3^s))*(1/(1-1/5^s))*(1/(1-1/7^s))*.....
This is equivalent to the Riemann Zeta function, Mathworld provides a
proof in their article.
Now we are down to evaluating the Riemann Zeta function at s=2: 1 + 1/2^2 + 1/3^2 + 1/4^2 + 1/5^2 + .....
This specific case is known as the Basel problem and solving it is what gave Euler early fame in the field of mathematics. The sum converges to a value pi^2/6, and several
proofs are included in the Wikipedia article.
Earlier I took the reciprocals of the infinite product so the answer to this problem is 1/(pi^2/6) = 6/pi^2 ~= 1.644934.
Solution via Euler
