Answer to Question #270345 in Discrete Mathematics for kd bhai

Question

Prove that if 10 points are placed in a 3cm by 3cm squre board than two points must be at least √2

cm apart.

Answer 1

A 3cm by 3cm squre board are divided by nine 1cm by 1cm squares. Since there are 10 points, by the Pigeonhole Principle there is a 1cm by 1cm square that contains at least two points. Since the maximal distance between any two points in the square is equal to the length of a diagonal which is equal to $\sqrt{1^2+1^2}=\sqrt{2}$ for the 1cm by 1cm square, we conclude that two points must be at least $\sqrt2$ cm apart.