TIFR CSE 2015 | Part A | Question: 13

Question

Imagine the first quadrant of the real plane as consisting of unit squares. A typical square has $4$ corners: $(i, j), (i+1, j), (i+1, j+1),$and $(i, j+1)$, where $(i, j)$ is a pair of non-negative integers. Suppose a line segment $l$ connecting $(0, 0)$ to $(90, 1100)$ is drawn. We say that $l$ passes through a unit square if it passes through a point in the interior of the square. How many unit squares does $l$ pass through?

• A. $98,990$
• B. $9,900$
• C. $1,190$
• D. $1,180$
• E. $1,010$

Comments

explain it please

Answer 1

Answer will be (d) 1,180

If a line segment passes through unit square from $(0,0)$ to $(i,j)$ the line intersects $(i+j-gcd(i,j))$

no. of squares =$ (90+1100-10)=1180.$

Comments

@srestha Apart from the below stackexchange link, you do have any standard reference explaining the formulae you have used to answer?

My logic yields $1170$ as the number of units the given line passes through. Please check my logic.

Slope of the line connecting $(0, 0) \text{ and } (90, 1100) = \frac{1100-0}{90-0} = 12.22...$

This means, per $1$ unit of the x-axis, the line passes through $13$ units across the y-axis.

$\therefore$ The line passes through $13 \times 90 = 1170$ unit squares. 

---

@zeeshanmohnavi

For line connecting (0,0) and (4,3).

Using your method:

$Slope = \frac{3-0}{4-0} = 0.75$

The line passes through $1 * 4 = 4$ unit squares.

Using the formula given in the link:

The line passes through $4 + 3 - gcd(4,3) = 7 - 1 = 6$ unit squares.

And it is correct. See figure below.

Answer 2

I think (B) answer will be 99000

(0,0) to(90,1100) total rowwise 91 points and columnwise 1101 points

Each 2 points makes 1 square

So, total no. of unit square are 90* 1100 = 99000 

Comments

I think then it would become a curve instead of line segment... Also the ans still remains to be 1180..

---

Got a generalized ans for this ques in this link-

http://math.stackexchange.com/questions/1151261/how-many-unit-squares-does-this-line-pass-through

---

yes u have to put formula for doing this