| medium | discrete |
A rectangular table has 100 coins with unit radius, placed on it such that none of the coins overlap, and it is impossible to place any more coins on the table without causing an overlap. Using this specific configuration, find a special configuration of 400 coins which covers the table with overlaps.
Covering means for every point on table there is a coin above it.
Create coins of radius 2 from the center of all coins. Notice that these coins fill up entire table, they are just bigger than what we are given.
Consider just one of these coins, with center P. It follows that the center Q of any other coin cannot lie within the coin of radius 2 with center P because it must be at least 2 units away. Thus, we construct all of these coins of radius 2, concurrent with each of the coins of radius 1. If the set of coins of radius 2 did not cover the rectangle entirely, then we could place a coin of radius 1 in this region, contradiction. Thus, the set of coins of radius 2 entirely covers the rectangle.
We now have 100 coins of radius 2 that entirely covers the rectangle. Scale this by a factor of 1/2 in both planar dimensions. Now we have 100 coins of radius 1 that entirely covers a rectangle that is a quadrant of the original rectangle. By placing four of these sets together, we get 400 coins of radius 1 that entirely covers the original rectangle.