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

Hi Ayush.5,

In your example. BC has the largest slope

---

Other Way around. Click Here 

---

is this in GATE CS syllabus 2027?

 

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

I guess given statement is a one way theorem
They have asked "necessarily satisfied" , i assume thats for necessary condition

steepest slope $\implies$ points are adjacent to each other wrt x co-ordinates
 

but

converse is not true.

---

Got it.

---

Is steepest gradient there in syllabus..?!

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:

 

Comments

Best answer sir

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

Answer 5

Consider 2 point a,c  and line of infinite length passing through them point b can be above line ac or below as 3 point can't be collinear, let us assume that b is below line ac now we find slop ab= Delta p and bc = delta q either of them will be greater ( assume delta p> delta q)

Similary if point b would be above line then result would be exactly opposite (delta q> p)

This is only possible when  are sorted as per their x coordinate

consider 3 points  
A=(x1, y1) = (1,10)
B=(x2, y2) = (2,2)
C=(x3, y3) = (4,22)

Cleary we can never see ab= -8 bc= 10 and ac= 4 so bc it's our gradient.

Thus answer is A

Comments

Can you give example where b is voilated?

Answer 6

correct answer is A

Comments

To solve this problem, we are tasked with determining which property must necessarily be satisfied for two points pa​ and pb​ that define the line Lab​ with the steepest gradient (i.e., the maximum absolute value of the slope) among all pairs of points pi​ and pj.

Analyzing the Options:

1. Option A: pa​ and pb are adjacent to each other with respect to their x-coordinate.

   This is not necessarily true. The steepest gradient could occur between non-adjacent points. For instance, the points could be arranged such that the line connecting them, though not adjacent in terms of x-coordinates, has a larger slope than those connecting adjacent points.

2. Option B: Either pa​ or pb​ has the largest or the smallest y-coordinate among all the points.

   This is also not necessarily true. The steepest line could be formed by points where neither is the extremum in y-coordinates. For example, consider two points that are both comparatively low in y but far apart in x; their line can have a steep slope without having any extreme y-values.

3. Option C: The difference between x-coordinates pa​ and pb is minimum.

   This option is quite compelling. The line with the steepest gradient corresponds to a larger difference in y-coordinates relative to a smaller difference in x-coordinates. Thus, if we are looking for the steepest slope, it often occurs when the horizontal distance (difference in x-coordinates) is minimized, while the vertical difference (y-coordinate) is maximized.

4. Option D: None of the above.

   This option would apply if none of the prior options can be validated.

Conclusion:

After analysis, Option C is indeed the most plausible answer, as minimizing the distance between the x-coordinates while maximizing the distance between y-coordinates could lead to the steepest slope.

Thus, the final answer is C: The difference between x-coordinates pa​ and pb​ is minimum.