4
$\begingroup$

I have a task to formulate approach and calculate how many different lines are defined by points in 8x8 grid (so 2 or more points lies on the line). Points are evenly distributed ([0,0], [0,1], ..., [1,0], [1,1], ..., [7,7]).

I tried to partition into groups, use symmetry, think about it as sequences of numbers and then use combinatorics but it always explodes into a lot combinations and I get different results every time. Can someone point me how to approach this task?

$\endgroup$
  • 1
    $\begingroup$ I think the simplest way to figure out all possible slopes of such a line, and count how many lines there are of each slope. $\endgroup$ – Mike Earnest Jan 25 at 18:58
  • $\begingroup$ @MikeEarnest If I understand you correctly, I tried to do it, but its a lot options and I got lost in it. $\endgroup$ – eXPRESS Jan 25 at 19:06
  • $\begingroup$ Have you tried solving a simpler version of the same problem? Say, for a $3×3$ grid, or a $4×4$ grid? $\endgroup$ – MJD Jan 25 at 19:58
  • $\begingroup$ @MJD Yes and the simplest method there was just to count all line types sum it together but as points are added number of groups increases fast and not only the same groups shifted but completely new ones and it seems unfeasible to do it this way and I got completely lost. Even the picture gets just so messy I cannot work with it. I believe there is some mathematical abstraction which I am missing. $\endgroup$ – eXPRESS Jan 25 at 20:23
2
$\begingroup$

EDIT: Found A018808 $0, 0, 6, 20, 62, 140, 306, 536, \color{green}{938}, 1492, 2306$

My counts were incorrect beyond 7x7.

$\endgroup$
  • $\begingroup$ How did you (1) make sure you got all possible lines and (2) avoid counting lines twice? $\endgroup$ – marty cohen Jan 25 at 23:10
  • $\begingroup$ @martycohen I checked all pairs of points, counting all lines with unique slope/intercept or unique x-value for vertical lines. There was some error, though, as my counts for 8x8 and above were incorrect. $\endgroup$ – Daniel Mathias Jan 25 at 23:14
  • $\begingroup$ Yep. Easy to generate all possible lines, harder to eliminate duplicates. $\endgroup$ – marty cohen Jan 25 at 23:23
  • $\begingroup$ well, in any case A018808 is titled to be what required, nice work (+1) $\endgroup$ – G Cab Jan 26 at 1:22
  • $\begingroup$ @DanielMathias Thanks for very useful link, now I just need to figure out what that formula means so I can explain it in my words. :) $\endgroup$ – eXPRESS Jan 26 at 9:13
1
$\begingroup$

Number the lattice points from $1$ to $N$. Count the number of lines that pass through lattice points $i$ and $j$ that do not pass through any lattice point $k$, $1 \le i \lt j \lt k \le N$.

That is obviously just restating the original requirement, and does not take advantage of the symmetries in the regular lattice, nor the combinatorial nature of the problem.


For a regular rectangular grid, I realized there is a much better approach, as I woke up this morning. (Your subconscious is your friend; let it do all the hard work! :)

Start with the simplest nondegenerate case, a 2×2 grid. This has six unique lines: two horizontal, two vertical, and two diagonal. (1×1 grid has no lines because there is not enough points, and single-row or single-column grids have exactly one line.)

Then, find out how many additional lines you get when you increase the width or height by one. Assume that you already know the number of lines in an $N \times K$ grid, and find out the number of unique lines added when $N$ is incremented by one. (Because of symmetries, this is the only case you need to find out.)

Let's say that you find that number in analytical form, say $\tau(N, K)$ when the grid size was $N \times K$ and $N$ is being incremented by one; and $N, K \ge 2$. The way/direction you grow the grid does not matter, and $\tau(N, K)$ is obviously symmetric with respect to $N$ and $K$. Thus, the total number of lines is $$\bbox{ T(N, K) = \begin{cases} 0, & N \le 1, K \le 1 \\ 1, & N = 1 \text{ and/or } K = 1 \\ 6, & N = 2, K = 2 \\ \displaystyle 6 + \sum_{n=2}^{N-1} \tau(n,2), & N \ge 3, K = 2 \\ \displaystyle 6 + \sum_{k=2}^{K-1} \tau(k,2), & N = 2, K \ge 3 \\ \displaystyle 6 + \sum_{n=2}^{N-1} \tau(n,2) + \sum_{k=2}^{K-1} \tau(k,N), & N \ge 3, K \ge 3 \\ \end{cases} }$$

That leaves the "hard" part, $\tau(N, K)$ (but we only need to consider it for $N \ge 2$, $K \ge 2$, as the grid size increases from $N \times K$ to $(N + 1) \times K$; for simplicity, let's assume it grows a new column, that $N$ is the number of columns in the old grid, and $K$ is the number of rows).

There is always at least one added line, the one along the new column of grid points. Every other new unique line $i$ has a slope $s_i \ne 0$. Because of symmetries, you'll find that for every positive $s_i$ there is a corresponding line with the same slope but negative, and vice versa. Therefore $\tau(N, K) = 1 + 2 p(N, K)$, and you only need to count new unique lines with positive slope, $p(N, K)$.

One way we can define $p(N, K)$ is just as a sum, where each summand indicates whether the line is new: $$\bbox{ p(N, K) = \sum_{n=1}^N \sum_{k=1}^{K} \sum_{i=1}^K U\bigr((n, k), (N + 1, i)\bigr) }$$ where $U\bigr((a, b), (c, d)\bigr)$ is 0 if the line between $(a,b)$ and $(c,d)$ passes through any lattice point $(i, j)$, and 1 if not (so such a line is new and unique).

To stop myself from finding the complete answer, I shall stop here. (More honestly, this is where I woke up, just as my subconscious was muttering something about $U$ and using greatest common denominators in finding whether there exists $j/i = h/w$, via $j = i h / w$ or something.)

$\endgroup$
  • $\begingroup$ If I understand you correctly, I tried that and I got lost in enumerating the combinations as there was no easy way to group these things up and it was just huge ammount of places to insert possible error (the number i got was not 938 which should be the correct answer - as in provided online resource by D. Mathias. because I definitely missed something). $\endgroup$ – eXPRESS Jan 26 at 9:25
  • 1
    $\begingroup$ @eXPRESS: As I woke up this morning, my subconscious had found a better approach. Try that. $\endgroup$ – Nominal Animal Jan 26 at 12:06
  • $\begingroup$ Thank you very much. I will try to look into that tomorrow (I have my paper til Monday and there are other tasks I did not finish yet). Meanwhile what I did was I calculated all lines as (64*63)/2 and substracted all duplicate lines of 3 - 8 points lines. As I glanced over your answer, some of your remarks seems familiar with how I was thinking. Somehow I ended up on number 938 but it is little bit messy so if I will manage in time I will go through your answer in depth. And you are right, taking a step back from it definitely helped. :) $\endgroup$ – eXPRESS Jan 26 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.