120 unit squares are arbitrarily arranged (and oriented) inside a 20 x 25
rectangle. Prove that it is always possible to place a circle of unit
diameter inside the rectangle without intersecting any of the squares.

SPOILER:






































From - Mon Aug 31 13:23:57 1998
From: dmoews@xraysgi.ims.uconn.edu (David Moews)
Newsgroups: rec.puzzles
Subject: Re: Russian 12 puzzle (SPOILER)
Date: 29 Aug 1998 08:33:27 GMT
Organization: University of Connecticut, IMS

120 unit squares are arbitrarily arranged (and oriented) inside a 20 x 25
rectangle. Prove that it is always possible to place a circle of unit
diameter inside the rectangle without intersecting any of the squares.
 (Solution)
Given a unit square, we can construct the set S of points of distance
<= 1/2 from it.  This set will be a square of side 2 whose corners
have been rounded off into radius 1/2 arcs, and will hence have area
3 + pi/4.  If we transform each of our 120 squares into a copy of
S, the union of all these copies will have area <120.(3 + pi / 4).
However, the rectangle whose sides are inset 1/2 from the large 20 x 25 
rectangle has area 19.24, and since pi < 32/10,

           19.24 - 120.(3 + pi / 4) = 96 - 30 pi > 0.

Therefore, there is a point in the inset rectangle and not in any S, and we
can center our circle on it.
-- 
David Moews                          dmoews@xraysgi.ims.uconn.edu