5
$\begingroup$

If $m,n \in \mathbb{N}$ . Let $g(m, n)$ be the number of cells that the line joining $(m, n)$ to $(0, 0)$ cuts in the region $0 \le x \le m$ and $0 \le y ≤ n$.

For example $g(1, 1)$ is $1$ because the line joining $(1, 1)$ and $(0, 0)$ cuts just one cell. Similarly $g(2, 1)$ is $2$ and $g(3, 2) = 4$.

Find $g(343, 56)$.

I am trying to derive a formula for any $g(m,n)$. I noticed that for $m=n$ the answer is $m$ but for $m \neq n$ the answer seems be $(m+n-1)$ in general but this does not holds for all. Any ideas how to generalize $m \neq n$ restriction?

  • 1
    This is related to [Bresenham's line algorithm](http://en.wikipedia.org/wiki/Bresenham's_line_algorithm). There some paper about the relationship between Bresenham's algorithm and Euclid's algorithm for gcd but I can't find it right now.2011-12-15

3 Answers 3

3

If ${\rm gcd}(m,n) = d \neq 1$, then you can say that $g(m,n) = d \cdot g(\frac{m}{d},\frac{n}{d})$ as the line can be divided in $d$ parts, each starting at $(0,0)$ and ending at $(\frac{m}{d},\frac{n}{d})$. If however ${\rm gcd}(m,n) = 1$ then you are essentially walking in a rectangle of $m \times n$, starting at the bottom left, ending at the top right corner, and only moving up or right. This takes exactly $m + n - 1$ squares. So if $d = {\rm gcd}(m,n)$ then

$g(m,n) = d \cdot \left(\frac{m}{d} + \frac{n}{d} - 1\right) = m + n - d$

In particular, ${\rm gcd}(343,56) = 7$, so $g(m,n) = 343 + 56 - 7 = 392$.

2

Let $r = {\rm gcd}(m,n)$. The line segment from $(0,0)$ to $(m,n)$ cuts $m-1$ vertical lattice lines and $n-1$ horizontal ones (not including those at the endpoints), but has $r-1$ intersections of horizontal and vertical lines, so $g(m,n) = (m-1) + (n-1) - (r-1) + 1 = m + n - r$.

1

It's only $m+n-1$ if $m$ and $n$ are relatively prime. If $m$ and $n$ are relatively prime, then the only lattice points that the line segment between $(0,0)$ and $(m,n)$ are touch are those two points themselves. Since it never touches another lattice point, it must cross $m$ squares in the horizontal direction and $n$ squares in the vertical direction, but this double counts one square (the upper right most one) so we must throw it out.

If $m$ and $n$ are not relatively prime, then assume that $(m,n)=d$. Our line segment will now cross through $(0,0)$ and $d$ additional lattice points. Thus, we have $d$ blocks that are of size $(m/d,n/d)$. Since $m/d$ and $n/d$ are relatively prime, within each block we cut $m/d+n/d-1$ squares, so our final solution is $d(m/d+n/d-1) = m+n-d$.