How Many Rational Slopes?

222 Views Asked by At

Given an $N$ by $M$ grid with integer coordinates (e.g. like pixels in an image), how many slopes are defined by the set of lines passing through the each grid point pair?

Note that because the coordinates are integer, the line slope $\frac{p}{q}$ is obviously rational.

The horizontal and vertical slopes are two slopes in this set and do not necessarily need to be part of the analytic solution (to avoid degeneracies and infinities). We will also, obviously, ignore the case of lines with the same point at both ends.

1

There are 1 best solutions below

0
On BEST ANSWER

The proportion of fractions in lowest terms is $6/\pi^2$. Using JHance's comment, there will be around $$\frac{12}{\pi^2}(M-1)(N-1)$$ different slopes.
Here is why that proportion of fractions in lowest terms is $6/\pi^2$:
$3/4$ of the time, $m$ and $n$ are not both multiples of $2$.
$8/9$ of the time, they are not both multiples of $3$.
$24/25$ of the time, they are not both multiples of $5$ and so on.
So the proportion in lowest terms is $$\frac{3}{4}\frac89\frac{24}{25}...$$ Its reciprocal is $$\frac43\frac98\frac{25}{24}...\\ =\left(1+\frac14+\frac1{16}+...\right)\left(1+\frac19+\frac1{81}+...\right)...\\ =1+\frac14+\frac19+\frac1{16}+\frac1{25}+\frac1{36}+...\\=\frac{\pi^2}6$$