Quadruple your money

[Paul Howe]

Here's a slightly more mathematical puzzle to see if there's a demand for such things. The solution requires no advanced knowledge (GCSE level is more than adequate) but you do need to think like a mathematician.

100 circular coins, all with the same radius, have been placed on a square table in such a manner that it's impossible to add a new coin (of the same size) without creating an overlap with an existing coin. Can you show that at most 400 such coins are required to completely cover the surface of the table?

A couple of minor technical points: a coin is considered to be on the table if it's centre is on the table, and you can consider the coins to be infinitely thin: this is not a physics puzzle.

[Dinos Sfyris]

Cheers you've given me something fun to think about in what will undoubtedly be a mind-drifty lecture!

[Gavin Chipper]

Does this simply involve proving that one could always cover the table with 400 coins, or that 400 is the lowest number where that is always the case? So, would we need to show that there would be cases where 399 isn't enough?

[Paul Howe]

Does this simply involve proving that one could always cover the table with 400 coins, or that 400 is the lowest number where that is always the case? So, would we need to show that there would be cases where 399 isn't enough?

You have to show that you can always cover the table with 400 coins, not that it's impossible to cover it with fewer. I'd wager you could do it with many fewer but the arguments needed to show that would be much more sophisticated.

[Joseph Bolas]

I don't suppose its something along the line of standing a coin up on all the edges of the coins on the table, so theres 4 upright coins, making a square and each square encloses one of the 100 coins on the table?

[Charlie Reams]

Paul already said it's not a physics puzzle, so the use of the coins and the tables are just to concretely illustrate the mathematical problem.

[Joseph Bolas]

Paul already said it's not a physics puzzle, so the use of the coins and the tables are just to concretely illustrate the mathematical problem.

I had an idea it was wrong, but I posted just on the off-chance that for once I was on the right lines

[David Williams]

I don't exactly have a solution, but here's what I've got.

"Think like a mathematician". This could mean start from the other end. Find a way of covering a table with 400 coins, then demonstrate that you can't get more than 100 on without two touching.

If your coins have radius sqrt(2), then each can cover a square 2x2. Placing 400 of them at co-ordinates (1,1), (1,3), (1,5), . . . (3,1), (3,3) etc. will completely cover a table 40x40.

For it to be impossible to fit another coin on the table without touching another coin, there must be no point on the table that is more than 2xsqrt(2) from the centre of all the coins on the table. This would be true if 100 coins were placed at co-ordinates (2,2), (2,6), (2,10), . . . (6,2), (6,6) etc. But it doesn't prove that there isn't some completely different way of fitting 101 coins on.

An alternative approach is to replace each of the 100 coins in the original set-up with four, probably arranged in a square with the edge of each where the centre of the original coin was. But I can't get this to work.

David W

[Paul Howe]

I don't exactly have a solution, but here's what I've got.

"Think like a mathematician". This could mean start from the other end. Find a way of covering a table with 400 coins, then demonstrate that you can't get more than 100 on without two touching.

If I've understood you correctly, you're saying that if we can reduce any 400 coin covering to 100 coins distributed so it's impossible to add a non-overlapping coin, the problem is solved. This doesn't work because there may be other configurations of 100 coins that can't be reached just by removing coins, and it may be impossible to form a 400-cover starting from one of these configurations. To give a more familiar example, you could use your logic to prove all odd numbers greater than 2 are prime by saying, "well every prime greater than 2 is odd, job done!"

Actually it's a bit worse than that because I could imagine an rXr table completely covered by 400 densely layered radius r coins from which i's clearly impossible to obtain a configuration of 100 nonoverlapping coins. If I've misunderstood you and just delivered a pointless lecture, my sincere apologies! However, it remains true that starting from the other end is not the way to go.

If your coins have radius sqrt(2), then each can cover a square 2x2. Placing 400 of them at co-ordinates (1,1), (1,3), (1,5), . . . (3,1), (3,3) etc. will completely cover a table 40x40.

I'm not sure introducing specific coordinates is going to be helpful, after all we don't know the size of the coins, the table, or how they relate to each other.

For it to be impossible to fit another coin on the table without touching another coin, there must be no point on the table that is more than 2xsqrt(2) from the centre of all the coins on the table.

Now this is more like it! A solution to this problem will undoubtedly contain a statement very similar to this one.

As you say, the fact that 400 = 4*100 is significant. However, trying to somehow arrange 4 coins into a square is a red herring, so don't go with that approach.

[Dinos Sfyris]

Just been thinking to myself on the problem and will now spew out random thoughts on my ponderings in a rather thrown together sort of fashion as articulacy has never been my strong point:

My thoughts at first were a 10x10 grid of coins where the gap between the closest points of 2 diagonal coins was an infinitesimally tiny bit smaller than the diameter of a coin, as this is the largest gap that a coin could just not fit, in my mind.

So we have a diagonal row of 10 coins with 9 gaps, each almost the size of a coin. Then you said:

a coin is considered to be on the table if it's centre is on the table.

Does this count even if it is on the corner of the table? ie Only a quarter of the coin is on the table?

If this is the case then the nearest point of the corner coin is at most half its diameter away from the corner to prevent fitting another one on. So you add half the diameter at each end of the diagonal row and you have a max diagonal length of the table almost 20 diameters, max edge length 10rt2 diameters.

I'm not sure where this leads exactly but I've now thoroughly convinced myself that you require 441 coins, ie a 21x21 square to cover the entire table...

Have to go to a lecture now. Maybe you can make some sense of my thoughts?

[David Williams]

Paul,

All I'm trying to say is that if I have 400 coins and arrange them in a particular way I can completely cover a square of a certain multiple of the radius of one coin. If I could then demonstrate that it's impossible to fit 101 coins into that square without two touching, I'd have solved the problem. But all I can do is find one way to get 100 in.

A good puzzle to me is one that's simple to describe, tantalisingly hard to solve, and obvious when you see the elegant solution. This gets two out of two so far. Let's hope for three out of three.

David

[Paul Howe]

a coin is considered to be on the table if it's centre is on the table.

Does this count even if it is on the corner of the table? ie Only a quarter of the coin is on the table?

If this is the case then the nearest point of the corner coin is at most half its diameter away from the corner to prevent fitting another one on. So you add half the diameter at each end of the diagonal row and you have a max diagonal length of the table almost 20 diameters, max edge length 10rt2 diameters.

I'm not sure where this leads exactly but I've now thoroughly convinced myself that you require 441 coins, ie a 21x21 square to cover the entire table...

Have to go to a lecture now. Maybe you can make some sense of my thoughts?

Dinos, YOU ARE MAKING ME DO TRIGONOMETRY. Under your construction, the table edges have length 10*sqrt(2)*r. If you figure it out with a pen and paper, you should (hopefully, I did it a bit too quickly) find that in order to cover the corner, the coins need to overhang the table (and each other) by at most (1 - 1/sqrt(2))*r, giving an effective table length of 9r*sqrt(2) + 2r. Given this maximum overlap, the "edge coins" can use up (2 - (1 - 1/sqrt(2)))*r = (1 + 1/sqrt(2))*r of the table length and the "middle coins" can use up (2 - 2*(1 - 1/sqrt(2)))*r = sqrt(2)*r. Adding these up gives 8r*sqrt(2) + 2r*(1+1/sqrt(2)) = 9r*sqrt(2) + 2r which is exactly the length of the table with the overhangs included. But as you say, the table has to be infintesimally smaller than this so its OK, the coins will cover the table!

I wouldn't take the above as ironclad mathematical truth as I scribbled it down in a bit of a hurry, but I'm pretty sure it's OK.

Paul,

All I'm trying to say is that if I have 400 coins and arrange them in a particular way I can completely cover a square of a certain multiple of the radius of one coin. If I could then demonstrate that it's impossible to fit 101 coins into that square without two touching, I'd have solved the problem. But all I can do is find one way to get 100 in.

A good puzzle to me is one that's simple to describe, tantalisingly hard to solve, and obvious when you see the elegant solution. This gets two out of two so far. Let's hope for three out of three.

David

Fair enough, I agree that if you constructed the largest possible square that could be covered by 400 coins and then showed it was impossible to fit 101 nonoverlapping coins into it you'd be done.

I think it would be very easy to adopt what I just did above into a solution along these lines, but this is NOT what I'm looking for: what I have in mind is a very simple argument that requires no trigonometry, DINOS.

[Paul Howe]

Right, I've decided to give you all a hint.

There were a couple of suggestions of replacing each coin with 4 new coins and arranging them in some suitable way. This isn't quite right, but consider instead what happens if you make each coin 4 times larger.

[Jason Larsen]

If the table is big enough, then I certainly do believe it!

[Paul Howe]

Doesn't look like this is going to be solved, so here comes the answer:

Let the coins have radius r, and imagine replacing each coin with a new coin having radius 2r and the same centre, so each new coin is on the table. Suppose there is a point P on the table that is not covered by any of these larger coins: then the minimum distance from P to any of the original radius r coins must be greater than r. This means we can put a new radius r coin on the table, centred at P, that doesn't overlap the original coins. But this violates the conditions of the puzzle. So, we've assumed there is a point that is uncovered by the larger coins, and from that assumption derived something impossible. This means the assumption is false, such a point cannot exist, and the radius 2r coins completely cover the table.

Now, we can just scale down: if 100 radius 2r coins cover the table, 100 radius r coins will certainly cover a square quarter of the table, and this can be repeated for each quarter of the table to give an arrangement of 400 radius r coins that completely cover the table.

[Dinos Sfyris]

Ahhhhhh

[Jason Larsen]

I can't say it any better myself, Paul!

[Gavin Chipper]

OK Paul. I have to say though, nothing against your mathematical puzzles as a whole, that I didn't find this one that enticing, and every time I thought I'd have a look at it I couldn't be bothered! Maybe that was just me though.

[David Williams]

Well, I enjoyed it. It's the going down to a quarter size table rather than trying to cover one large coin with four small ones that's obvious when pointed out, but hard (for me, anyway) to see.

David