Not many, just 5 dimensions

Probability Level 2

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

Details and assumptions :-

In the 5D space, every point can be represented as coordinates $(a,b,c,d,e)$ , where $a,b,c,d,e,f \in \mathbb{R}$
Lattice points are points that have integer coordinates.

The answer is 33.

3 solutions

Sasha Chabanov
Apr 28, 2016

This might be only me being a non-native speaker and misunderstanding the problem, but shouldn't be there "... out of n lattice points..."? Cause near the point with all non-integer coordinates, one can fit any number of points with also non-integer coordinates such that there is obviously no lattice point in between any two.

Joel Tan
Mar 28, 2015

Consider the parities of each of the coordinates. If two points have the same parity for each of the 5 coordinates, their midpoint is also a lattice coordinate. When $n=2^{5}+1=33$ this will definitely happen.

If $n=32$ , consider all possible lattice points with each coordinate 0 or 1. Clearly a point joining two of them will not pass through a lattice point. Thus $n=33$ is the answer.

Vaibhav Prasad
Mar 27, 2015

Let $N$ be the minimium number of points to be chosen out of $r$ D space, such that there are 2 whose midpoint is a lattice point. Then, I claim that

$N = 2^r + 1$

Here $r=5$ hence $2^5+1=\boxed{33}$

Dude that's right, but there's just one thing you gotta do... You said $k$ as the number of points and later, you used it as the number of choices for a coordinate (i.e. Odd or Even, giving $k=2$ ).... Also, write a complete proof if you can :D

Aditya Raut - 6 years, 2 months ago

Thanks for pointing out the ambiguous notation! I've edited the solution accordingly.

Calvin Lin Staff - 5 years, 7 months ago

Not many, just 5 dimensions

The answer is 33.

3 solutions

1 pending report

Vote up reports you agree with