Given a set
of points in the plane, a line is called
happy
if it contains at least three points in
. By looking at the above picture, we see that the
grid of points shown has
happy lines. How many happy lines are there in a
grid?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
There are 3 vertical and 9 horizontal lines in the 3 × 9 grid (the columns and the rows).
It easy to see, that all other lines (which are neither horizontal, nor vertical) have to have exactly one point in each column.
If we put our grid on a Cartesian plane, then the x coordinate is referring to the column and the y coordinate is referring to the row number.
If we choose a point from the first column from the n th row (1 , n), then the coordinates of the point of the same straight line
• in the second column has to be (2 , n + k), and
• in the third column has to be (3 , n + 2k).
Therefore, we are looking for the number of integer solutions for the system of inequalities:
1 ≤ n ≤ 9
1 ≤ n + 2k ≤ 9
One way to solve this is to count the gridpoints in the feasible region after graphing these inequalities (4 lines) in an (n , k) coordinate system.
Another way is to determine the number of non-zero integer solutions (k) for each value of n algebraically:
• n = 1 : k ∈ 1 , 2 , 3 , 4 4 solutions
• n = 2 : k ∈ 1 , 2 , 3 3 solutions
• n = 3 : k ∈ - 1 , 1 , 2 , 3 4 solutions
• n = 4 : k ∈ - 1 , 1 , 2 3 solutions
• n = 5 : k ∈ - 2 , - 1 , 1 , 2 4 solutions
Now, we can see that due to symmetry (we can turn our grid upside down, getting the opposite ( × (-1) ) values for k), we get the same number of solutions for n = 4 and n = 6; n = 3 and n = 7 and so on.
Therefore the number of straight lines, which are neither horizontal, nor vertical:
2 × ( 4 + 3 + 4 + 3 ) + 4 = 3 2
Hence, the total number of happy lines in our 3 × 9 grid:
3 + 9 + 3 2 = 4 4