Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I guess this is a Pigeonhole Principle application. I tried dividing the cube in various ways, but got nowhere. Maybe there is another approach.

In a cube of side of length $9$ there are $1981$ points. Prove that there exist two of them situated at distance at most $1$ from each other.

share|improve this question
1  
Cute problem (+1). Where did you find it? –  Jonas Teuwen Oct 25 '11 at 21:15
    
@JonasTeuwen: Someone gave it to me, but I think it comes from a Romanian Olympiad. –  Beni Bogosel Oct 26 '11 at 8:31

2 Answers 2

up vote 7 down vote accepted

If there would exist such a configuration with all distances $>1$ one could place 1981 balls of radius ${1\over2}$ in a cube $Q$ of side length 10 (move all faces of the given cube ${1\over2}$ outwards). But these balls have a total volume of $1037.24\ldots\ $.

In fact the number $1981$ can be improved to $1415$: If there are $N$ points with mutual distance $>1$ in the $9^3$-cube, then $N$ balls of radius ${1\over2}$ fit in the $10^3$-cube $Q$. These balls consume the fraction $$\delta={N\cdot{\pi\over6}\over 1000}$$ of ${\rm vol}(Q)$. By repeating this configuration periodically one obtains a sphere packing of space with this density; therefore by Hales' theorem one has $$\delta\leq{\pi\over 3\sqrt{2}}$$ or $N\leq1000\sqrt{2}\doteq1414.2$. This implies that for $N\geq1415$ such a configuration is impossible.

share|improve this answer
    
I was 56 seconds behind $\ldots$ –  Christian Blatter Oct 25 '11 at 20:54

Assume $n$ points in the cube are each at distance at least $1$ from the others. Then the balls of radius $\frac12$ centered at these points are disjoint. Their total volume is $n$ times the volume $\frac43\pi\left(\frac12\right)^3=\frac16\pi$ of a ball of radius $\frac12$. On the other hand every point in one of these balls is at distance at most $\frac12$ from the cube of side $9$, in particular all the balls are included in a cube of side $10$. Hence $\frac16\pi n\leqslant 10^3$, that is, $n\leqslant1909$.

share|improve this answer
    
Ok. That's an interesting approach. Thank you. :) –  Beni Bogosel Oct 25 '11 at 21:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.