2
$\begingroup$

I'm wondering how many line segments can be drawn from an $n \times n$ square dots. By manual counting, $n = 2$ hence the number of line segments = 6, $n = 3$ the number of line segments is 28... but i dont know if there is a mathematical formula defining such pattern. I started with my basic, that is, n = 2 there are 4 points therefore 4(3)/2 = 6, which is correct but as i tried it to n = 3 which has 9 points, that is, 9(8)/2 = 36... i exceed 8 counts from my manual count of 28.... i realized that some of the line segments crossover the middle point and when I counted it there are 8 long line segments which makes my manual counting correct since 36 - 8 = 28. Any idea will of great help.

$\endgroup$
11
  • 1
    $\begingroup$ just to be clear, you are $not$ asking how many unique vectors can be generated by connecting all possible pairs of endpoints in an $n \times n$ grid $\endgroup$ Jun 17, 2019 at 13:05
  • 1
    $\begingroup$ If we have an integer point (a, b), and an integer point (c, d), then there is an integer point on the segment between them if there exists a common divisor of (c-a) and (d-b) greater than 1. You can use that to exclude the bad segments. $\endgroup$ Jun 17, 2019 at 13:07
  • 2
    $\begingroup$ oeis.org/A141255 $\endgroup$
    – irchans
    Jun 17, 2019 at 13:22
  • 1
    $\begingroup$ Here is a PDF on the subject. survo.fi/papers/LinesInGrid2.pdf $\endgroup$
    – irchans
    Jun 17, 2019 at 13:23
  • 1
    $\begingroup$ Another PDF by the same author survo.fi/papers/PointsInGrid.pdf $\endgroup$
    – irchans
    Jun 17, 2019 at 13:26

1 Answer 1

1
$\begingroup$

There's clearly some ambiguity here as to what is implied by the term "line segment from an $n\times n$ square dots". One thing that's obvious is that a segment joining ANY two points on the $n\times n$ square grid is not the sole criterion as this yields more than 28 segments when $n=3$.

In the following answer, I have worked with the assumption that a line segment on the grid is defined as one on which every point is immediately adjacent (horizontally, vertically or diagonally) to at least one other point on the line and all the points satisfying this requirement lie on a straight line (an obvious requirement). This condition implies that the only possible orientations of straight lines are 0°, 45° and 90° with respect to the horizontal axis. Such a model is simple to work with and agrees well with the given manual counts for the cases $n=2$ and $n=3$.

We try working from a simpler case and build on it gradually. Take a row of $n$ dots. Within this row, it is easily seen that we have $n-1$ line segments of length 2, $n-2$ line segments of length 3, ..., 2 line segments of length $n-1$ and 1 segment of length $n$.

Hence, within each such row, the number of line segments contained would be:

$\sum_{k=0}^{n-1}k = \dfrac{n(n-1)}{2}$

Now, we move on to the case of an $n\times n$ square grid. Every such grid has $n$ rows and $n$ columns of length $n$ each. This gives us a total of:

$2\times n\times\dfrac{n(n-1)}{2} = n^2(n-1)$

line segments, contained in our grid, counting only in the horizontal and vertical directions.

Using the same criteria in diagonal directions, we can also find pairs of line segments of lengths 2, 3,... $n-2$, $n-1$ each and one main diagonal, all of which are parallel. (Approaching the main diagonal from each corner of the square helps visualize this.) This gives us two such families of parallel diagonal line segments as every square has two main diagonals. By equivalence, the total number of line segments in each family would be the same.

For one family, direct application of the above formula gives:

$2\sum_{k=2}^{n-1}(\dfrac{k(k-1)}{2}) + \dfrac{n(n-1)}{2}$

$= \sum_{k=1}^{n-1}(k^2-k+k)$

$= \dfrac{n(n-1)(2n-1)}{6}$

lines so that there are a total of $\dfrac{n(n-1)(2n-1)}{3}$ diagonal line segments in the grid.

This puts the total number of line segments at:

$n^2(n-1) + \dfrac{n(n-1)(2n-1)}{3}$

$= \dfrac{n(n-1)(5n-1)}{3}$

This gives 0 line segments when $n=1$, 6 line segments when $n=2$ and 28 line segments when $n=3$.

I'm afraid there's a good chance this answer might have missed the intended aim of the question. However, hope it helped clarify your doubt to some extent.

$\endgroup$
0

You must log in to answer this question.

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