Question

The n- dimensional space is colored with n colors such that every point in the space is assigned a color. Show that there exist two points of the same color exactly a mile away from each other.

Answer 1

For n=1, there is nothing to prove.
For n>!, consider n+1 points p₀, p₁,.......p_n in |Rⁿ (all at a distance of 1 mile from each other) which are affine independent, i.e. p₀ - p₁ , p₀ -p₂ ,....., p₀ - p_n are linearly independent in |Rⁿ (this is always possible as |Rⁿ has dimension n over |R, and we can always get n linearly independent vectors) . Now consider the regular simplex( a simplex, all of whose edges are of length 1 mile) determined by the n+1 points.
For example, in case of n=2, we get an equilateral triangle with vertices p₀ , p₁ and p₂. If n=3, we get a regular tetrahedron with vertices p₀,p₁,p₂ and p₃.

Now, since there are n+1 points and n colours, by the Pigeonhole Principle (Pigeons: Points, Pigeonholes: Colours),
atleast two points, say p_i and p_j are of the same colour. Further, they are 1 mile apart. This proves the result.

PIGEONHOLE PRINCIPLE: If there are k+1 pigeons that need to occupy k pigeonholes, then atleast 2 pigeons share the same pigeonhole.