IIT JEE , AIEEE Forum - Mathematics , Algebra

mirtunjay_svm2007

Consider a chessboard like rectangle of side m ´ n. Draw a diagonal by joining two opposite vertices. How many squares does this

diagonal pass through ?

For e.g. for a 5 ´ 3 board, the diagonal passes through 7 squares while for a 4 ´ 4 board, it passes through 4 squares.

prash_shan_jpr

Tell me the nature of M and N

are they even/odd/one even and one odd ??

elastiboysai

When m=n

its a trivial case a square

so no. of squares it passes through is m

When m not equal to n

Now consider ur rectangle at the origin

The equation of diagonal is y=(m/n)*x

Now position the rectangle such that m>n

All the lines are of the form y= constant or x= constant

and the different lines have areas bounded between them

All you need now is

solutions of the equation y=(m/n)*x

where either of the coordinate is an integer

This can be generalised to y=m+n-1 when m and n are coprime

[1 for (m,n)]

this follows because if coprime

u cant find another ratio p/q = m/n

such that p and q are integers

when m not equal to n and they have a common factor

write 1,2,3,4,5,...m and 1,2,3,4,5...n

find all those points that satisfy y=(m/n)*x where both are integers

(called lattice points)

let the no. of such points be p

now answer in case 2 is m+n-1-p

for a good example

consider a rectangle sides 6/ 3

y= 6/3*x is the equation of the diagonal

now lattice points are (1,2) (2,4) =2

so no of squares the diagonal passes thru is

6+3-1-2 =6

when both are coprime

consider y=(5/3)*x

accordin 2 the logic no of squares= 5+3-1 =7

sboosy

Consider a rectangle of dimensions 1:m

this part is easy to answer .the diagonal passes through m squares

Consider cases where m=n

then obviously we see that it passes thru m squares (bcos there r m symmetric squares and the diagonal itself is symmetric about each square)

Consider dimensions where 1 is not involved ...that is m:n

where m and n are both not equal to 1 and both not equal

Consider the equation of line y=(m/n) x

if they are coprime :

then answer is m+n-1

else

find the number pairs of y/x which satisfy m/n for y belonging to 1 to m-1 and x belonging to 1 to n-1= k(no of pairs)

the answer is m+n-1- k

elastiboysai

I was stuck on the generalization part for p.

but after some disc. wid koni

we have arrived at a conclusion dat p= [n^2/m]+1

here p stands for no. of lattice points on the line -1

Ask & Discuss Questions with Community & Experts