The Gateway to Computer Science Excellence

+10 votes

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 ?

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

+13 votes

Best answer

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

- $(x_1, y_1) = (1,10)$
- $(x_2, y_2) = (2,2)$
- $(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.

0

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

0

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..

0

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?

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?

+4

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.

"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.

+6 votes

Answer: C

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

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

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

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

+1 vote

Answer is (A) part.

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

+1 vote

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

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

52,345 questions

60,497 answers

201,858 comments

95,315 users