On a Crossnumber Clue

In the Chalkdust Crossnumber #4, the deadline for which was last week, one of the first clues I looked at and thought “I can work that out easily enough” was this one:

27. The number of straight lines that go through at least two points of a 10 × 10 grid of points. (4)

It turned out to be the second-to-last one in, and I thought I’d share how I eventually solved it in Python, and another approach I could have tried.

Obviously, this post contains spoilers. If you still plan to do the crossnumber, you might prefer not to read on.

What I did

My first thought was “that’s easy, just count the number of ways to go from any point in the grid to any other – 100 points, 99 other points, so 9900 vectors; halve it, 4,950, job done.”

Job very much not done: for example, the line $y=x$ goes through ten of the points in question, and accounts for 45 of those vectors, while only for one line. I would have to do something smarter.

So, enter Python. ((In reality, I didn’t do this as nicely first time, and hacked the whole thing together. But never mind that.))

There are two objects I’m interested in: points and lines.

Points are easy; all I need is an x-coordinate, a y-coordinate and a check on whether two points are the same. class Point: def __init__(self, x, y): self.x = x self.y = y def __eq__(self, other): return (self.x == other.x and self.y == other.y) There’s not much more I care about, pointwise, except whether they lie on a line; without much thought, I decided to make that a method of the Line class.

Any pair of points defines a unique line. My first thought was to classify lines by their equations (since we’re working with an integer grid, all of the lines can be written in the form $ax + by + c = 0$ with coprime integer coefficients, and $a \ge 0$). Later, I realised this was more work than I wanted: I could simply check if each new pair of points lies on the line.

To do that, as any A-level student knows (I hope), you would check whether $\frac{y-y_1}{x-x_1} = \frac{y_2-y_1}{x_2-x_1}$, which is the gradient of the line. However, there’s a problem here: we’re not engineers ((“Problem?” For heaven’s sake.)), so we don’t like to divide by 0, which we’d need to do in the case of a vertical line. We can work with an equivalent check, though: does $(y-y_1)(x_2-x_1)=(x-x_1)(y_2-y_1)$?

So here’s the my Line class: class Line: def __init__(self, p1, p2): # a line that passes through p1 & p2 if p1 == p2: raise ValueError("Initialising points must be different") self.p1 = p1 self.p2 = p2 def containsPoint(self, p): # point is on line if (y - y1)/(x-x1) = (y2 - y1)/(x2 - x1) x1, y1, x2, y2 = self.p1.x, self.p1.y, self.p2.x, self.p2.y x,y = p.x, p.y return (y-y1)*(x2 - x1) == (y2 - y1)*(x-x1)

Now it’s just a case of running through all of the possible point pairs and checking which ones work. Comments below explain the process:

def gridLines( n = 10): # list all of the points in an n by n lattice p = [ Point( i % n, i / n ) for i in range(n**2) ] # showing off, really out = set() # a set to store all of the lines in. for p1 in p: for p2 in p: # loop through each pair of points if p1 != p2: # as long as they're different toAdd = True # add them to the set by default, but... for L in out: # first check all the lines in the set... if L.containsPoint(p1) and L.containsPoint(p2): toAdd = False # ... and if they're already on a line, don't add a new one. if toAdd: out.add(Line(p1, p2)) # on the other hand, if they're not on any lines, add away! return len(out) # how many lines are in the set?

Running gridLines(10) gives the correct answer, 2306!

A simpler approach

There are no lines that go through a pair of points in a 0 by 0 or 1 by 1 grid.

Six lines do for 2 by 2.

Three by three is a bit harder: there are three vertical, three horizontal, six with gradient 1 or -1, and eight with gradient $\pm2$ or $\pm \frac{1}{2}$, making 20 in all.

Now we have a few terms, it’s OEIS to the rescue!. The third entry is this one, which is a) exactly what we’re after and b) gives us the tenth term directly (it’s still 2306).

Interestingly, it doesn’t look like there’s an especially nice formula for it.

* Thanks to @mscroggs and @chalkdustmag for an entertaining puzzle!