I'm in the space!

Probability Level 3

There are $n$ distinct lattice points marked in the 3D space.

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 3D space, every point can be represented as coordinates $(x,y,z)$ , where $x,y,z \in \mathbb{R}$

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

Easier version 2D

Harder version 5D

The answer is 9.

2 solutions

Vaibhav Prasad
Mar 27, 2015

Let $k$ be the number of points to be chosen out of $n$ lattice points in $r$ D space, then the least value of $n$ can be given as $k^r +1$

Here $k=2$ and $r=3$ hence $2^3+1=\boxed{9}$

Can you explain the formula?

Agnishom Chattopadhyay - 6 years, 2 months ago

well ....I derived it from the solution to 2D

Vaibhav Prasad - 6 years, 2 months ago

Well yeah, that was exactly why I had written it as $2^2+1 = \boxed{5}$ , so that people understand the trick for $n$ dimensions, it will be $2^n+1$ ...

Aditya Raut - 6 years, 2 months ago

@Aditya Raut – What are the conditions for more than 2 points. That a lattice point must exist along all segments joined by choosing one set of n points?

Trevor Arashiro - 6 years, 2 months ago

@Aditya Raut – The formula can be guessed, as you have said, to be $k^{r} + 1$ , but any rigorous proof by induction or some other kind ?

Venkata Karthik Bandaru - 6 years, 2 months ago

Joel Tan
Mar 28, 2015

Consider the parities of each of the coordinates. If two points have the same parity for each of the 3 coordinates, their midpoint is also a lattice coordinate. When $n=2^{3}+1=9$ this will definitely happen. But when there are 8 points with coordinate 0 or 1 clearly a point passing through two of them will not pass through a lattice point. Thus $n=9$ is the answer.

I'm in the space!

The answer is 9.

2 solutions

0 pending reports