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
    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.2012-10-19
  • 0
    @vikiiii: no, he suggested the pattern will repeat.2012-10-19
  • 0
    @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.2012-10-19
  • 0
    @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 .2012-10-19
  • 0
    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.2012-10-19
  • 0
    @Andreas If i am wrong please explain a little more as i am unable to understand chessboard and prime number concept2012-10-19
  • 0
    @vikiiii: We find the number of squares travelled through to $(49,8)$, then multiply by $7$. So to get to $(49,8)$, the "next" square is always $1$ to the left or $1$ up from the current square. So we need to take a total of $48$ "left" steps, a total of $7$ up steps. That plus our starting square is $48+7+1=56$. Now multiply by $7$.2012-10-19
  • 0
    In general, take the $m\times n$, and let $d$ be the gcd of $m$ and $n$. Let $a=m/d$, $b=n/d$. The number will be $(a+b-1)d$.2012-10-19
  • 0
    @Andreas Is my logic also correct as i wrote in the comment2012-10-19
  • 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
    Your answer is beyond my thinking. Anyways thanks for answering.2012-10-19
  • 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
    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]2012-10-19
  • 0
    The squares might also be black/red2012-10-19