Counting Lines

My lunchtime math problem solving group was going through some old American Mathematics Competition problems, and we came across one that asked, in slightly more complicated language, "How many lines can be drawn that intersect at least two points in a 3x3 rectangular array?".

Most of the kids who understood the wording got the answer, and when I asked them how, they said they counted... they drew the dots, drew the lines, and counted them...

So I asked, how would you do it if they had a ten-by-ten array?

Counting the number of lines in an nxn array that contain the maximum number of points, n, is pretty straightforward. There are n horizontal lines that contain n points, and another n vertical lines, and two diagonals. For nxn there are 2n+2 lines that contain n points. In the 3x3 case, there are 2(3)+2 = 8 lines that contain exactly three points. So how to count the 2x2.

After a while I decided that there would be a maximum of n choose 2 lines if no two were collinear, so at most, a set of nine points could contain 9 choose 2 = 36 lines. Now each of the lines that had three points, would use up three different lines from this 36.. think of a line with points A, B, and C all collinear. Instead of three lines, they fall on one, so each line of three points would reduce the possible total of 36 by two... and since there are 8 of these lines, we need to eliminate 8x2=16 lines from the 36 to get a total of 20, 8 with three points, 12 more with only two points.

This verified the students solution by counting, but didn't bring us much closer to the general ten x ten case. For instance in a 4x4 there are some lines with four points (10 of them) and some more with three points (a quick look assured me there would be four) and the rest with only two points. By Starting with 16 choose 2 and eliminating duplication as before, I figured out that there would be 48 of the lines with two points.

By the next time we meet, Conner S. had counted up the number of lines with exactly two points by hand up to n=5 (and had a small error in the n=5 case finding only 100 when there are 108... Examining the case for n=5 is influential, but still, we don't get a really good clue of a general pattern. The sequence for the number of total lines from n=2 to n=5 is 6, 20, 62, 140... you might want to try to find the next one.. I couldn't, and the pattern of lines with exactly two points was equally wild... 6, 12, 48, 108??? (For my students, I will show how the counting technique used above to the possible lines given by n choose 2 to find the number of lines with two points. In most cases (such as the five by five) it is not too hard to count the number of lines that contain three, four, or five points.)

I guess I can be ok with my kids not being able to find the pattern, as it seems that the pattern didn't have any simple solution at all, and was eventually extended, it seems, beyond the hand countable cases by computer search. Afterward they did find a summation notation that is way complicated. I finally searched the On-line integer data base and found the actual numbers... don't look if you are still figuring out the pattern for yourself. This triangular array gives the number of lines containing exactly k points in an nxn array.. At the top of the triangle is n=2, k=2, and as you go down each row the n goes up one... so the numbers in the fourth row(for n=5, a 5x5 array), {108, 16, 4, 12} is the number of lines containing 2, 3, 4, and 5 points.




Interesting to look down the center at the sequence of 4's, as long as the number of points in the line is more than (n+1)/2 and less than n, there will be four such lines. Predicting the rest of the table as yet is beyond me.. if you see a simple way to calculate these values, do please advise.