, 2014

Solution 1

The ratio of side lengths in the given $4 \times 6$ grid is $4:6$ which is equivalent to $2:3$.

The ratio of side lengths in the desired $30 \times 45$ grid is $30:45$ which is also equivalent to $2:3$.

Therefore, the $30 \times 45$ grid can be built using $2\times 3$ blocks; the resulting grid can be seen as a $15 \times 15$ array of $2\times 3$ blocks.

The diagonal line of the $30 \times 45$ grid has slope $\frac{30}{45} = \frac{2}{3}$ and so passes through the lower left and upper right corners of each of the diagonal blocks of the $15 \times 15$ array of $2 \times 3$ blocks. Each of these corners is a lattice point. The diagonal line does not pass through any other lattice point within each of these diagonal blocks, as can be seen in the $4 \times 6$ grid.

We note that the upper right corner of a diagonal block is the same point as the lower left corner of the next such block. This means that we have to be careful with our counting.

There are 15 diagonal blocks. The diagonal line passes through the bottom left corner of the grid and passes through the upper right corner of each of the diagonal blocks.

This means that the diagonal line passes through $1+15=16$ lattice points.

Solution 2

We assign coordinates to the desired $30 \times 45$ grid, with the bottom left corner at the origin $(0,0)$, the vertical side lying along the positive $y$-axis from $(0,0)$ to $(0,30)$ and the horizontal side lying along the positive $x$-axis from $(0,0)$ to $(45,0)$.

The upper right corner of the grid has coordinates $(45,30)$. The grid lines are the horizontal lines $y=0$, $y=1$, $\ldots$, $y=29$, $y=30$ and the vertical lines $x=0$, $x=1$, $\ldots$, $x=44$, $x=45$.

The lattice points in the grid are the points with integer coordinates.

Consider the diagonal that joins $(0,0)$ to $(45,30)$.

The slope of this line is $\frac{30-0}{45-0}=\frac{2}{3}$.

Since the diagonal passes through the origin, its equation is $y=\frac{2}{3}x$.

Thus, we must determine the number of lattice points that lie on the line $y=\frac{2}{3}x$ with$x$-coordinates between $x=0$ and $x=45$, inclusive.

Suppose that $(a,b)$ is a lattice point on the line; that is, $a$ and $b$ are both integers.

Since $b = \frac{2}{3}a$, then for $b$ to be an integer, it must be the case that $a$ is a multiple of 3.

The multiples of 3 between $0$ and $45$, inclusive, are $0,3,6,\ldots, 42, 45$.

Since $45 = 15(3)$, then there are 16 numbers in the list.

Each of these values for $a$ gives an integer for $b$ and so gives a lattice point on the line.

Thus, there are 16 lattice points on the diagonal.