Given 1985 points inside a unit cube, show that we can always choose 32 such that any polygon with these points as vertices has perimeter less than 8√3.
Solution
64 x 31 = 1984. So if we divide the cube into 64 cubes side 1/4, then one of the small cubes must contain 32 points. Each pair of points in the cube is at most a distance (√3)/4 apart, so the 32-gon has perimeter less than 8√3 (if all pairs had distance (√3)/4 then some of the points would be coincident).
© John Scholes
jscholes@kalva.demon.co.uk
11 Sep 2002