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.
For the two points being the endpoints of a line segment, that segment will not intersect any intervening points if and only if the delta x and delta y are relatively prime.
Simulation results in:
trials=1000000;
randomSpace=1000000;
dx=randi(randomSpace,[1,trials]);
dy=randi(randomSpace,[1,trials]);
relPrime=sum(gcd(dx,dy)==1);
relPrime/trials
finds 0.608082 of the random pairs of numbers (between 1 and a million) to be relatively prime. Even reducing the random space to just between 1 and 10, the ratio goes to 0.629578. For 1 to 100 it came out 0.608007.
A bit of research shows that the probability approaches 6/pi^2 =~ 0.607927101854027 as the random space increases. Even for a space consisting of integers 1 through 100, the variation due to using only one million trials is enough to bring the simulation results statistically within the theoretical mean.
|
|
Posted by Charlie
on 2024-05-23 12:23:44 |
solution -- simulation and research
