Pigeonhole principle - cutting a square out of a rectangle

Question

Paper sized 10cm x 100cm was filled with 999 points. Show that you can cut a 1cm x 1cm square out of the paper without touching any of the points.

Can anyone help me understand this problem..I know how to solve problems where you have to show that some points are less than some unit away from each other but how to show that there is at least 1cm between 4 of them.

Answer 1

A 10 * 100 rectangle would have 1000 squares of side 1 cm.

• If all points were clustered into one of these squares, then the remaining 999 could be safely cut out.
• If we were to take it as 1 point per square, there's still 1 square left without a point.

All other permutations lie between these 2 extremes. Therefore, you can cut one 1*1 square without touching any of the points.