Ponder This

IBM Research has put up the July challenge on their Ponder This site.

Update: Here is the problem:

Upon a rectangular table of finite dimensions L by W, we place n identical, circular coins; some of the coins may be not entirely on the table, and some may overlap. The placement is such that no new coin can be added (with its center on the table) without overlapping one of the old coins. Prove that the entire surface of the table can be covered completely by 4n coins.

6 thoughts on “Ponder This

  1. You start with n coins on the table.

    Actually, I liked this problem better than some of the previous ones. More metric spaces and less combinatorics :)

  2. It’s close enough to the end of the month … here is my solution:

    Let x_1, x_2, …, x_n be the centres of the coins and r be their radius.

    Since placing a new coin on the table will overlap with a coin already on the table, we have: for all x (on the table), there exists x_i such that |xx_i| < r.

    Hence the n balls B(x_i, 2r) cover the table.

    Shrink this be a factor of 2 in each direction, and we get a cover of a L/2 x W/2 table by n balls of radius r.

    Four of these gives us 4n coins covering a table of size L x W.

  3. Pingback: Ars Mathematica

  4. If you have a coin on a table so that you cannot put another coin (with it’s centre) on the table without overlapping the first coin, then I think you’ll find four coins will be enough to cover the table.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>