4
$\begingroup$

I have got a problem and I am unable to think how to proceed.

$a$ and $b$ are natural numbers. Let $f(a, b)$ be the number of cells that the line joining $(a, b)$ to $(0, 0)$ cuts in the region $0 ≤ x ≤ a$ and $0 ≤ y ≤ b$. For example $f(1, 1)$ is $1$ because the line joining $(1, 1)$ and $(0, 0)$ cuts just one cell. Similarly $f(2, 1)$ is $2$ and $f(3, 2) = 4$.

Find $f(343, 56)$.

I have tried by making the equation of line joining $(0,0)$ and $(343, 56)$.

I got the equation as $8x = 49y$.
Now I tried it by randomly putting the values of $x$ and $y$ which are both less that $343$ and $56$ respectively.

But I am unable to get it.

Is there is any better approach?

Thanks in advance.

3 Answers 3

5

A start: Note that $343=7\cdot 49$, and $56=7\cdot 8$. First find $f(49,8)$.

More: If $a$ and $b$ are relatively prime, draw an $a\times b$ chessboard, and think of the chessboard squares you travel through as you go from the beginning to the end.

  • 0
    @vikiiii: I don't understand the $f(6\cdot 12+1)$. Think of a car driving, but only East or North. How many "blocks" will it travel through? Or else colour in red the squares you travel through up to $(49,8)$. The red squares from a zigzag path.2012-10-19
1

Hint The line joining these to points can be parametrized as $l(t)=( 7 \cdot 7 \cdot 7t,8 \cdot 7 t).$ Now the number which that line cut cells is the number that when an ordinate change from non integer to integer. This can be easily understood if you draw the grid. The only thing you should be careful is not to count twice the times when both ordinates turn to integer because it the time when you hit a vertex. So you should count only one time. Denote $N(x)$ the number when the first ordinate goes is integer and $N(y)$ the times when the second ordinate is integer. So what you need is when one ordinate is integer or when the other ordinate is integer. $N(x \cup y)= N(x)+N(y)-N(x \cap y)$.

  • 0
    @vikiiii This is very similar to my answer, put more formally.2012-10-19
1

Each time your line passes through a vertical or horizontal gridline it enters a new square. Count the horizontals and verticals it crosses.

When it hits a corner it goes through a vertical and a horizontal at the same time so you need to adjust for corners. This is determined by considering the common factors of $a$ and $b$.

The first square is given to you, so add 1.

  • 0
    The squares might also $b$e black/red2012-10-19