In the following sheet, a $4 \times 6$ grid was drawn and then the diagonal from $A$ to $B$ was traced.

![](https://cdn.mathpix.com/cropped/2024_05_01_d02c2755ad3373bde08ag-12.jpg?height=582&width=889&top_left_y=502&top_left_x=465)

Notice that the diagonal $A B$ intersects the grid at 9 points:

![](https://cdn.mathpix.com/cropped/2024_05_01_d02c2755ad3373bde08ag-12.jpg?height=574&width=862&top_left_y=1209&top_left_x=478)

If the grid were of size $12 \times 17$, how many points would the diagonal $A B$ intersect the grid?

#
Solution

Let's enumerate the vertical and horizontal lines of the grid as follows:

![](https://cdn.mathpix.com/cropped/2024_05_01_d02c2755ad3373bde08ag-40.jpg?height=859&width=1171&top_left_y=691&top_left_x=329)

The diagonal $AB$ intersects each vertical line at exactly one point. This gives us 18 points of intersection. Also, $AB$ intersects each horizontal line at exactly one point. This gives us 13 points of intersection. We know that points $A$ and $B$ are common points of intersection. Therefore, in the sum $18+13$, we are counting each intersection twice. If there were no other common points of intersection, the answer would be

$$
18+13-2=29
$$

Suppose there was another intersection point $P$, as shown in the graph.

![](https://cdn.mathpix.com/cropped/2024_05_01_d02c2755ad3373bde08ag-41.jpg?height=849&width=1172&top_left_y=231&top_left_x=519)

Let's say the side of each small square measures $1 u$. Then it is clear that $|AC|=17$ $u$ and $|BC|=12 u$. The triangles $ABC$ and $PBQ$ are similar because they have the same angles. Therefore, $\frac{|BQ|}{|QP|}=\frac{|BC|}{|CA|}$ or, equivalently,

$$
BQ=\frac{12 \times QP}{17}
$$

If $P$ belonged to a vertical line and a horizontal line, then both $QP$ and $BQ$ should be integers (when written in terms of $u$). For $12 \times |QP| / 17$ to be an integer, 17 must necessarily divide $|QP|$. But if $0<|QP|<17$, this is impossible. We conclude that such a $P$ does not exist. Therefore, the final answer is 29 points of intersection of $AB$ with the grid.