Happy Line

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:

$\text {• } n = 1 \text { : } k \in \text { {1, 2, 3, 4} 4 solutions}$

$\text {• } n = 2 \text { : } k \in \text { {1, 2, 3} 3 solutions}$

$\text {• } n = 3 \text { : } k \in \text { {-1, 1, 2, 3} 4 solutions}$

$\text {• } n = 4 \text { : } k \in \text { {-1, 1, 2} 3 solutions}$

$\text {• } n = 5 \text { : } k \in \text { {-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 = 32$

Hence, the total number of happy lines in our 3 × 9 grid:

$3 + 9 + 32 = \boxed {44}$