# Find the value of f(343, 56)?

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?

-

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.

-
Sir , So according to your answer f(4,4) = f(1.1) . But f(4,4) passes through 4 blocks. and f(1,1) pass through 4 blocks. – vikiiii Oct 19 '12 at 16:36
@vikiiii: no, he suggested the pattern will repeat. – Ross Millikan Oct 19 '12 at 16:41
@vikiiii: Your line will go through $(49,8)$, $(98,16)$, $(147,24)$, and so on. Once you figure out what happens up to $(49,8)$, everything will be clear. – André Nicolas Oct 19 '12 at 16:48
@Andreas Thanks for the answer . And also Ross Millikan who cleared my doubt . Now i have got the answer. In my next comment i will tell you how i got it . But i want to ask is it a right way . – vikiiii Oct 19 '12 at 16:48
What i did is take your suggestion Find f(49,8) . So Ross told pattern will repeat 7 times. So instead of finding f(49,8) . I found f(6.12 , 1 ) . So this passes exactly through 7 blocks you can imagine this . So f(343,56) will be 7 * 8 * 7 = 392 which is the answer. – vikiiii Oct 19 '12 at 16:51

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)$.

-
Your answer is beyond my thinking. Anyways thanks for answering. – vikiiii Oct 19 '12 at 16:55
@vikiiii This is very similar to my answer, put more formally. – Mark Bennet Oct 19 '12 at 21:27

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.

-
It is then possible to derive a formula for the number of squares - if $hcf(a,b)=h$ then the line crosses $h-1$ corners so we get $(a-1)+(b-1)-(h-1)+1=a+b-h$. There are questions involving a black/white checkerboard grid asking how many black squares you cross - note that black and white alternate except for a parity change at corners. [Note that 392=343+56-7] – Mark Bennet Oct 19 '12 at 18:49
The squares might also be black/red – Mark Bennet Oct 19 '12 at 21:28