Given a set of points in space, a jump consists of taking two points in the set, $P$ and $Q$ , removing $P$ from the set, and replacing it with the reflection of $P$ over $Q$ . Find the smallest number $n$ such that for any set of $n$ lattice points in $10$ -dimensional-space, it is possible to perform a finite number of jumps so that some two points coincide.

This problem is from the OMO.

The answer is 1025.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

Notice that the parity of a point’s coordinates does not change when it undergoes a jump, so if we take the unit $10$ dimensional cube (all coordinates at $0$ or $1$ ), we have $2^{10} = 1024$ points, and no two will ever coincide because that would imply their parities are the same. Thus the answer is at least $1025$ .

To show that $1025$ works, we use induction on the number of dimensions.

Base Case: Any $3$ points in $1$ -dimensional space can be moved so that some two coincide.Proof: Jump an outer point over the middle point, maximum distance decreases. So, eventually some two will coincide.Inductive step: Consider any $2^{n+1} + 1$ points in $(n+ 1)$ -dimensional space. We’re going to show that we can make some $2^{n} + 1$ of them lie in an $n$ -dimensional “plane,” so that we can apply the inductive step.Let’s project the points down onto $1$ -dimensional space; say, by looking only at the first coordinate.

Then any jump in $(n+1)$ -space corresponds directly to a jump of the projected points (feet) in $1$ -space.

Now divide up the points into two sets $A$ and $B$ based on the parity of the first coordinate. We can assume WLOG that both $A$ and $B$ are non-empty, else we can either divide by $2$ , or shift over and divide by $2$ , and the sequence of moves remains the same. By pigeonhole, we know that one of the sets has at least $2^n + 1$ elements, let that be $A$ . Now, choose any element $P$ of $B$ . By manipulating the feet of any two elements $a_1, a_2 \in A$ and $P$ , we can get the feet of $a_1$ and $a_2$ to coincide (by the base case, and parity) and thus $a_1$ and $a_2$ lie in the same $n$ -dimensional plane. Now we repeat this algorithm, subsequently always treating $a_1$ and $a_2$ as a unit (so that they remain in the same plane whenever they jump over another point).

Thus, by repeatedly manipulating the feet of $P$ and two elements from $A$ , we can accumulate all the points in $A$ into $n$ -space, and we are done. Thus, the answer is $\boxed{1025}$ .