3
$\begingroup$

I need help with this question

I have problem like this: I have rectangle with fixed size NxM, such that N, M are positive natural numbers. And this rectangle of size NxM is splited on squares with size 1x1, actually if the rectangle sizes are 3x3, it is splited on 9 squares. This picture is showing.

picture

And actually the picture is also showing the thing i want to find, the number of small squares in which the diagonal of the rectangle is passing. In all 4 variants it is passing in 4 squares.

Thanks in advance.

$\endgroup$
4
$\begingroup$

First, suppose that $N$ and $M$ have no common factor. Then the diagonal line doesn't go through any intersections, so each time it crosses a horizontal or vertical grid line, it adds $1$ to the number of squares touched. And to get from the top left to the bottom right, it must pass through $N-1$ vertical grid lines and $M-1$ horizintal grid lines. Counting the orginal square in the top left, this gives a total of $1+(N-1)+(M-1)=N+M-1$ squares touched. This formula applies to your first and second diagrams.

Now suppose that $N$ and $M$ have a common factor. Let $q=(N,M)$ be the largest common factor of $N$ and $M$. Then $N/q$ and $M/q$ have no common factor, so we can break the problem up into $q$ smaller rectangles strung along the diagonal, each of size $N/q\times M/q$; and in each such rectangle the number of squares visited is $N/q+M/q-1$. So the total number of squares visited is $q\times(N/q+M/q-1) = N+M-q$.

Hence in all cases the number of squares touched is

$$N+M-(N,M)$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.