The amount of unit squares being covered

37 Views Asked by At

enter image description here

$L$ and $i$ are integers, $L$ is the length of edge of outermost square and $i$ is the minimum length divided from $L$. And there are cells or unit squares consisting the whole block.

There is a statement:

For each right triangle, the number of cells which are crossed by an edge of the triangle is $L - \gcd(i, L)$

Why does this stand?

1

There are 1 best solutions below

0
On BEST ANSWER

Each time the line crosses a lattice line it enters a new cell. The line starts at $(0,0)$ and ends at $(L-i,i)$. We ignore the final intersection at $(L-i,i)$ but not the first at $(0,0)$. It intersects $L-i$ vertical lines and $i$ horizontal lines, so $L$ in total. But when it passes through a point $(m,n)$ it crosses two lines at once, so we need to deduct the number of such points that it passes through. But that is just the gcd of $i$ and $L$.