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

LbyW, we placenidentical, 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 4ncoins.

I don’t understand the problem. What’s the n in 4n?

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

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

Let

x_1,x_2, …,x_nbe the centres of the coins andrbe 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 existsx_isuch that |x–x_i| < r.Hence the

nballs 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 xW/2 table bynballs of radiusr.Four of these gives us 4

ncoins covering a table of sizeLxW.Pingback: Ars Mathematica

I don’t think it’s possible for n = 1.

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.