This plane can't crash, it doesn't fly

Probability Level 4

There are $n$ distinct lattice points marked on the 2D plane (2 dimensional).

Find least possible value of $n$ , such that we can always choose 2 points out of $n$ points (wherever they may be marked), such that there's at least one more lattice point on the segment joining them.

Details and assumptions :-

$\bullet$ In the 2D plane (or Cartesian plane), every point can be represented as coordinates $(x,y)$ , where $x,y \in \mathbb{R}$

$\bullet$ Lattice points are points that have integer coordinates.

Harder versions 3D and 5D

The answer is 5.

1 solution

Aditya Raut
Mar 27, 2015

Let a lattice point be $P(x,y)$ .

Both $x$ and $y$ can either be $ODD$ or $EVEN$ . Thus there are $2^2=4$ different combinations possible, they'll be $(o,o),(e,e),(e,o),(o,e)$

If we choose $5$ distinct lattice points, then one of the above parity patterns repeats, so midpoint of the segment joining the 2 points, which will be $\Bigl( \frac{x_1+x_2}{2} , \frac{y_1+y_2}{2}\Bigr)$ will have to be a lattice point (as $x_1$ and $x_2$ have same parity, their sum is divisible by $2$ ).

Hence answer is $2^2+1 = \boxed{5}$

Congo for ur kvpy selection... u are in pace ryt? me too...

Mayank Shrivastava - 6 years, 2 months ago

This plane can't crash, it doesn't fly

The answer is 5.

1 solution

0 pending reports