GATE IT 2007 | Question: 80

Question

Let $P_{1},P_{2},\ldots,P_{n}$ be $n$ points in the $xy-$plane such that no three of them are collinear. For every pair of points $P_{i}$ and $P_{j}$, let $L_{ij}$ be the line passing through them. Let $L_{ab}$ be the line with the steepest gradient amongst all $\frac{n(n -1)}{2}$ lines.

Which one of the following properties should necessarily be satisfied ?

• A. $P_{a}$ and $P_{b}$ are adjacent to each other with respect to their $x$-coordinate
• B. Either $P_{a}$ or $P_{b}$ has the largest or the smallest $y$-coordinate among all the points
• C. The difference between $x$-coordinates $P_{a}$ and $P_{b}$ is minimum
• D. None of the above

Comments

To prove option A as incorrect, I thought of this counterexample  :P

Let A and be be the two points of steepest slope(see image). Then I can insert another point C in between them such that

$xcordinate$$_{A}$ < $xcordinate$$_{C}$ < $xcordinate$$_{B}$

and 

 $ycordinate$$_{A}$ > $ycordinate$$_{C}$ > $ycordinate$$_{B}$ .

Now option (A) is wrong because points A and B are steepest but are not adacent. So, i thought steepest slope points need not be adjacent.

But now points A and B dont form the steepest slope. It is the pair (B,C) which has steepest slope.

It can be proved that steepest slope can occur only between some pair of adjacent points when the points are sorted in ascending order of their x-cordinate. So, we can sort the  n points in O(nlogn) wrt x cordinate and then find slopes of adjacent points only in O(n) time. So overall complexity will be O(nlogn)+O(n)= O(nlogn)

---

it depends on both axis right? , if points are adjacent to each other with respect to x-axis but y-axis remains the same then what?

---

ayush.5

Regarding your last paragraph, can you prove it? In your diagram, I considered the triangle formed by the 3 points and noticed that the slope of largest side(AB) lies between slopes of other 2 sides (AC and BC). If you consider the sides as vectors and write the largest vector $(\overline{BA})$ as the vector sum of other 2 vectors, one of these 2 vectors has the highest slope. Segment corresponding to largest vector will never have the largest slope. However, I am not able to prove this rigorously. Please help.

Answer 1

A is correct.

If we arrange all points in ascending order of their $x-$ coordinates, then the steepest gradient will be between two adjacent points.

Ref: https://stackoverflow.com/questions/8222108/max-slope-from-set-of-points

Counter example for (C) is as follows:

Consider $3$ points 

1. $(x_1, y_1) = (1,10)$
2. $(x_2, y_2) = (2,2)$
3. $(x_3, y_3) = (4,22)$

$\text{Grad}_{12} = \frac{y_2-y_1}{x_2-x_1}=\frac{2-10}{2-1} = -8/1  = -8$
$\text{Grad}_{32} = \frac{y_2-y_1}{x_2-x_1}=\frac{22-2}{4-2} =  20/2 = 10$
$\text{Grad}_{31} = \frac{y_2-y_1}{x_2-x_1}=\frac{22-10}{4-1} = 12/3 = 4$

Here, $\text{Grad}_{32}$ is steepest, but $x_3-x_2 = 4-2 = 2$ is not minimum.

Comments

So then what should be the answer according to you if it x2-x1 should not be minimum .

---

I think , it shud be A .

---

Amsar Sokt, how is it A either?  If A is the answer, G12 (in your example) should be the steepest. What about D? :p

---

A) is correct. steepest gradient is always between two adjacent (x-axis) points.

---

@reena_kandari @Himanshu1

The difference between x-coordinates Pa and Pb is minimum

I think they are saying difference between x cordinates of Point A and Point B only which is must to get steepest gradient for line passing from A and B

Not the difference between x cordinates of any two points..

 

---

@Himanshu1 are these 3 points of your example situated in same straight line?

---

Then what should be the correct answer A or C?

---

Options A and C seem very similar. Can anyone please point out the difference between them?

Isn't the slope of 2 points lying on the x-axis adjacent to each other = 0? Does it serve as a counter example for Option A?

---

Option (A) means -

"Two points are adjacent" means, i.e. when you plot the points on the graph, there's no third point between the two points which constitute to a line with steepest gradient.

Now, it has one more implicit assumption that, "when two points have SAME $x$ co-ordinates, then they are adjacent".

Option (C) means -

Steepest line always has minimum difference between its two $x$ co-ordinates, which is false since gradient depends on BOTH $x$ and $y$ co-ordinates, and NOT only on the $x$ co-ordinates.

---

when two points have the same x- ordinates then gradient of the line joining these two points having same x -ordinate infinity. Hence the difference is minimum is also an answer.

---

Okk also Gradient of (23) is also steepest it will also be 10 NOW please check your difference of x coordinate.

So correct answer should be C which has no offence in its statement it is clear.

Please reply fast.

---

just to help visually,…

 

as we can see , less distance between x-coordinates means greater slope.Also, slope depends on y-cordinates too, but those options are not present so ans is (
A)

Answer 2

Now understand the question. It is of the form, 

IF Lab is the line with the steepest gradient then (%%%%%%%)
Where %%%%%%% is one of the options in the question.

 

This is what is meant by necessary. It means that for the statements of the form p->q, q has to be true if we have p as true. 

 

Now the question asks which of the options has to be true (definitely) if the premise (i.e. Lab us the line with the steepest gradient) is true.

 

OPTION A:

 

Here adjacent points wrt to x co-ordinates mean, that there exists no point having an x co-ordinate b/w these two points. 

Now based on this, let us see, option A. Suppose for contradiction, assume that option A is not true. Then, for two adjacent points with respect to x co-ordinates, shall not have the steepest slope, rather two nonadjacent points wrt to x co-ordinate will have the steepest slope.

 

 

The (Xp,Yp) is the intermediate point adjacent to (Xa,Xb). We supposed that Lab (the purple line) where Pa and Pb are non-adjacent wrt x co-ordinates is having the steepest gradient, but due to point (Xp.Yp), we got a steeper gradient, indicated by the orange line. So we reach a contradiction.  So OPTION A is correct.

 

OPTION B: it is not a necessary condition for the y co-ordinates to be maximum and or minimum, because, the gradient is given by the ratio delta y/ delta x. So it shall also depend on the difference between the x coordinates.

 

OPTION C:

 

The difference b/w Xa and Xb need not be minimum, necessarily. It shall depend on the y co-ordinates as well. For counter example:

 

Answer 3

Answer: C

Gradient $= \frac{y_{2} - y_{1}}{x_{2} - x_{1}}$

For gradient to be maximum $(x_{2}-x_{1})$ should be minimum.

Answer 4

Answer is (A) part.

Please refer -->https://stackoverflow.com/questions/8222108/max-slope-from-set-of-point