Shrink and Conquer

I recently came across this problem, and I knew it was one of the neatest problems I’d ever seen and had to write a post about it. The visual thinking necessary to come across its solution is pretty great. A seemingly intricate geometric situation, there is almost no formal mathematics required but simply a series of logical observations.

Given that there are 100 coins on a rectangular table such that there are no overlaps, and no additional coin can be placed on the table without causing an overlap, prove that using 400 coins and allowing for overlaps we can cover the whole table.

Some assumptions include:

– Each coin’s center is on the table

– The coins are normal and circular

– To cover the whole table every point needs to be at least one coin above every point on the table

As always, I have outlined my take on the problem after the picture, so don’t scroll!

2012-12-12-Coins.jpg

To first tackle the problem, I think it’s best just to visualize the situation. We have the 100 coins, with gaps in between them but no gaps which have the area of the coin (which we can take as a circle of radius 1 cm for simplicity’s sake.

Now, to start to prove why 400 coins would cover the table, we can directly see a relation between 100 and 400 – a factor of 4, which would be achieved in terms of area of the coins by doubling the radius. So let us theoretically expand each of the coins, in its same position, to a coin of radius 2 cm.

Now, what if there is a gap on the table, which is not covered by any coin? This would mean that originally all centers of the coins near that point were more than 1 cm away (in all directions). This means that there would have been a gap large enough to fit in a coin without causing overlaps, which is a contradiction.

Therefore it is not possible for a gap to exist, and all points on the table are covered. But the question wasn’t to show that 100 coins of 4 times the area completely cover the table, but that 400 coins of 1 cm radius cover it completely. But if we shrink the table’s dimensions and all the coins by a factor of 2, which see a table of size 1/4th the original size which is covered by 100 coins of radius 1 cm. 4 of these tables placed side by side achieve that same exact size of the original table, and we know that it is covered completely by 400 of the original coins because we proved each of the individual tables has to be covered completely.

I had to share this problem, because I love the way we have to take the concept of proving by contradiction and apply the idea that we have a larger version of the situation we desire. Basically, this is one of my favorite problems.

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s