1
$\begingroup$

I was hoping to get some help to not only solve the problem but also identify what branch of math this would fall under (and hopefully improve my tags). The problem goes like this:

Say there is some MxN matrix where there are M rows and N columns of equally spaced vertices and M and N are greater than or equal to 3. If you choose three random points that are all different from each other, what are the odds they all end up in a straight line?

The problem is easy when you calculate the possibility of the three vertices being in the same column or row, but the tricky part is if they end up being in the same diagonal. Even calculating the number of diagonals of slope 1 is kinda trivial, but non-slope 1 diagonals are where everything gets much more difficult, especially factoring in the idea that colinear points don't have to be right next to each other on the same line(a single line with containing 5 dots has 5 choose 3 possibilities just in that one line).

After consulting with some combinatorics professors, they said that this problem didn't seem to be a true combinatorics problem and they said that because the matrix is finite and we don't allow for the lines to wrap around the matrix, it might not be possible but they aren't sure where to start with the diagonal problems.

$\endgroup$

1 Answer 1

1
$\begingroup$

I will answer a slightly more general question: when you choose $k\ge 3$ points in the matrix, what is the probabiliity that all $k$ points are collinear? I will think of the grid as the set of points $(x,y)$ in the Cartesian plane, where $x$ can be any integer between $0$ and $m-1$, while $y$ is an integer between $0$ and $n-1$.

Let $(x_0,y_0)$ be an initial point, and let $m$ be a positive, finite slope. Specifically, write $m=b/a$ for integers $a,b\in \mathbb N^+$ with $\gcd(b,a)=1$. We will count the number of ways to select $k$ collinears point in this grid, such that one of the points is $(x_0,y_0)$, and such that the slope of the line is $m$. This accounts for all lines with positive slope; to account for negative slope, we will multiply by $2$ in the end.

The set of grid points on the line through $(x_0,y_0)$ with slope $m$ are $$ \{(x_0+at,y_0+bt)\mid t\in \mathbb Z,0\le x_0+at\le m-1,0\le y_0+bt\le n-1\} $$

We need to figure out the size of this set. This is easy to do, but a bit messy. First, let us count the points where $t>0$. We need to have $x_0+at\le m-1$ and $y_0+bt\le n-1$. This means that $$ 0<t\le \min\left( \left\lfloor\frac{m-1-x_0}{a}\right\rfloor, \left\lfloor\frac{n-1-y_0}{b}\right\rfloor \right) $$ Next, when counting points where $t<0$, we instead need $x_0+at\ge 0$ and $y_0+bt\ge 0$, which implies $$ -\min\left( \left\lfloor\frac{x_0}{a}\right\rfloor, \left\lfloor\frac{y_0}{b}\right\rfloor \right)\le -t <0 $$ Overall, we see that the number of grid points on this line where $t\neq 0$ is equal to $$ f(x_0,y_0,a,b):=\min\left( \left\lfloor\frac{m-1-x_0}{a}\right\rfloor, \left\lfloor\frac{n-1-y_0}{b}\right\rfloor \right)+\min\left( \left\lfloor\frac{x_0}{a}\right\rfloor, \left\lfloor\frac{y_0}{b}\right\rfloor \right) $$ We need to choose $k-1$ other grid points on this line, where we cannot choose $(x_0,y_0)$. The number of ways to do this is $\binom{f(x_0,y_0,a,b)}{k-1}$. We then take the sum of this over all admissible values of $x_0,y_0,a,$ and $b$. Next, we must multiply by $2$, since we were only accounting for positive slopes. Finally, we need to divide by $k$, since this counting method gives a special role to one of the points, $(x_0,y_0)$. Therefore, the number of ways to select three points which are collinear (except for vertically and horizontally aligned points) is $$ \frac2k\sum_{x_0=0}^{m-1}\sum_{y_0=0}^{n-1}\sum_{a=1}^{m-1}\sum_{b=1}^{n-1}\binom{f(x_0,y_0,a,b)}{k-1}\cdot {\bf 1}[\gcd(a,b)=1] $$ The notation ${\bf 1}[P]$ is equal to $1$ if the property $P$ is true, and zero otherwise. This is just a way to say that we only sum over pairs $(a,b)$ with $\gcd(a,b)=1$.

Since the number of vertically aligned sets of $k$ points is $n\cdot \binom{m}k$, and the number of horizontally aligned sets of $k$ points is $m\cdot \binom{n}k$, we add $n\cdot \binom{m}k+m\cdot \binom{n}k$ to get the total number of triplets. Then, we divide by $\binom{mn}{k}$ to get the probability that $k$ randomly selected points without replacement are in a line. The final answer is $$ \frac1{\binom{mn}k}\left(n\cdot \binom{m}k+m\cdot \binom{n}k+\frac2k\sum_{x_0=0}^{m-1}\sum_{y_0=0}^{n-1}\sum_{a=1}^{m-1}\sum_{b=1}^{n-1}\binom{f(x_0,y_0,a,b)}{k-1}\cdot {\bf 1}[\gcd(a,b)=1]\right). $$


As a final note, I take offense to your combinatorics professors saying that this is "not a true combinatorics problem". This is a problem about counting a discrete set, of course it is a combinatorics problem! Sure, it may note have a nice solution, and computing the solution might be intractable for practical values of $m$ and $n$, but that does not mean it is not a problem worth considering.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .