Can you clarify how you get 2x*2r*2y*2r as a bounding area for the table? I'm not seeing where that is coming from.
x is the number of coins going horizontally, 2r is the diameter of the coin, then I multiply by 2 to take into account not just the length contributed by the coins themselves, but also the length contributed by the spaces between the coins.
Quote:
Here, you are assuming the coins are packed in a grid, but that's not necessarily the case. What if you created a grid but added an infinitely small space between touching coins (ie. space between two coins in x direction and two coins in y direction). You still couldn't place a coin in the space in between the 4 coins, but the centers of the diagonal coins would be more than 2sqrt(2)r apart.
I think you may have misinterpreted what I'm saying here. I didn't say anything about a "packed" grid or the coins touching. I'm talking about moving the coins away from each other horizontally and vertically, to the maximum amount possible without creating enough space to place a coin the created space. This means a diagonal hypotenuse approaching 2r, which means the horizontal/vertical side length becomes sqrt(2)r. This is half the horizontal (or vertical) distance between the center of one coin and the center of the next coin. Hence, the horizontal distance from coin center to coin center approaches 2sqrt(2)r, but can't actually reach that distance, otherwise you can now fit a coin in the space created.
Admittedly, it may be hard to visualize what I'm saying without me actually providing diagrams.
x is the number of coins going horizontally, 2r is the diameter of the coin, then I multiply by 2 to take into account not just the length contributed by the coins themselves, but also the length contributed by the spaces between the coins.
I think you may have misinterpreted what I'm saying here. I didn't say anything about a "packed" grid or the coins touching. I'm talking about moving the coins away from each other horizontally and vertically, to the maximum amount possible without creating enough space to place a coin the created space. This means a diagonal hypotenuse approaching 2r, which means the horizontal/vertical side length becomes sqrt(2)r. This is half the horizontal (or vertical) distance between the center of one coin and the center of the next coin. Hence, the horizontal distance from coin center to coin center approaches 2sqrt(2)r, but can't actually reach that distance, otherwise you can now fit a coin in the space created.
Admittedly, it may be hard to visualize what I'm saying without me actually providing diagrams.
Spoiler!
I think you need to add the 1/root2(D) boarder around your table
Maybe I misunderstood the question. When you say "it is impossible to add another quarter to the table without requiring an overlap" do you mean coins can be slid on the table and shifted around, as long as they never overlap? Or are they all locked into a fixed position?
Maybe I misunderstood the question. When you say "it is impossible to add another quarter to the table without requiring an overlap" do you mean coins can be slid on the table and shifted around, as long as they never overlap? Or are they all locked into a fixed position?
This is a good question, imo.
I misread it initially, and my solution assumed the coins were touching each other, which wasn't stated in the problem.
In many ways this reminds me of a reservoir engineering problem. The spaces in between the coins would be porosity (just 2d instead of 3d). Having the coins not touching would make it a non-physical solution, but you'd have perfectly sorted matrix with exactly equal grain sizes.
I think the answer probably flows from your observation about the distance between the coins. I don't see the solution but have the following observations.
The number of coins given is 400, or 4:1 for the number of initial coins. That ratio isn't physical, but 4 is 2 squared, and we know the distance between the centers of the coins can't be bigger than 2D, because then you could fit another coin.
I think the proof will involve squaring that distance and demonstrating that 4x is enough coins to cover it somehow.
I didn't spoiler this because its just middle of the night musings, and could be completely unhelpful to anyone...
x is the number of coins going horizontally, 2r is the diameter of the coin, then I multiply by 2 to take into account not just the length contributed by the coins themselves, but also the length contributed by the spaces between the coins.
Ok, I understand your argument. It's a bit moot anyways I think since you reduce the maximum area below.
Quote:
I think you may have misinterpreted what I'm saying here. I didn't say anything about a "packed" grid or the coins touching. I'm talking about moving the coins away from each other horizontally and vertically, to the maximum amount possible without creating enough space to place a coin the created space.
Ok, understood.
Quote:
This means a diagonal hypotenuse approaching 2r, which means the horizontal/vertical side length becomes sqrt(2)r. This is half the horizontal (or vertical) distance between the center of one coin and the center of the next coin. Hence, the horizontal distance from coin center to coin center approaches 2sqrt(2)r, but can't actually reach that distance, otherwise you can now fit a coin in the space created.
Ok, I think I understand what you are saying. Yes, a diagram would be helpful.
I think you are saying: let's try to place 3 coins as far apart as possible without allowing a coin to fit between them. You start by placing 2 coins 2r apart (so centre distance is 4r). Draw an imaginary coin between them so the three coins are on the same horizontal line. Then you can place your third coin below the imaginary coin so that the coins form a T. The centre distance between this third coin and the first 2 coins is 2sqrt(2)r.
So my question is does it follow that the least efficient arrangement of coins is 2sqrt(2)rx by 2sqrt(2)ry? I don't know if that is obvious, since in my coin arrangement above, if I placed my first two coins slightly less than 2r apart, then the third coin could be moved much further away and still allow for no coin to rest in between them.
Maybe I misunderstood the question. When you say "it is impossible to add another quarter to the table without requiring an overlap" do you mean coins can be slid on the table and shifted around, as long as they never overlap? Or are they all locked into a fixed position?
No, any given arrangement is fixed. But the proof must hold for all possible arrangements.
I misread it initially, and my solution assumed the coins were touching each other, which wasn't stated in the problem.
In many ways this reminds me of a reservoir engineering problem. The spaces in between the coins would be porosity (just 2d instead of 3d). Having the coins not touching would make it a non-physical solution, but you'd have perfectly sorted matrix with exactly equal grain sizes.
I think the answer probably flows from your observation about the distance between the coins. I don't see the solution but have the following observations.
The number of coins given is 400, or 4:1 for the number of initial coins. That ratio isn't physical, but 4 is 2 squared, and we know the distance between the centers of the coins can't be bigger than 2D, because then you could fit another coin.
I think the proof will involve squaring that distance and demonstrating that 4x is enough coins to cover it somehow.
I didn't spoiler this because its just middle of the night musings, and could be completely unhelpful to anyone...
This is the type of discussion I wanted this thread to encourage. I hope others add their thoughts too!
Seems things have died down on this problem. Here's the solution.
Spoiler!
Let's say the coins are circles of radius 1.
Take one coin on the table. If we draw a circle of radius 2 around that coin's centre, we can guarantee that no other coin's centre is inside that circle (if it were, the coins would be overlapping).
Let's draw circles of radius 2 on all of the coins. Let's assume that these new circles do not cover the table. That means that there exists some space that is not covered by any of the circles of radius 2.
But if that were the case, then we could place a new non-overlapping coin of radius 1 with its centre in that uncovered space, which is a contradiction.
Therefore, the circles of radius 2 completely cover the table.
Let's scale the table and circles down by 1/2 in the x and y direction. The table is now 1/4 of the size of the original table, and the circles of radius 2 are now circles of radius 1 which can be considered coins. We now have 100 coins covering a table 1/4 the size of the original based on the original coin configuration.
We can therefore cover the entire table with 400 coins.
I don’t think that is different than MG saying the Max distance between any two adjacent coins is 1/root2
I think there is a difference.
Spoiler!
In the solution, it only considers the minimum distance to not cause an overlap, which is 2 (centre-centre distance). To me, this is more precise because it doesn't matter what the coins arrangements are - this distance will always hold. An empty space in the radius 2 covering is all areas that are at least 1 unit away from *any* coin edge, which means a coin must be able to be placed there.
MG tried to find the maximum distance between coins, which is less obvious. If two coins are 2sqrt(2) apart (centre-centre distance), is it clear that a coin can fit between them? It might be the case, but it's not obvious - other coins may come into play preventing a coin from being placed.
Maybe I'm misinerpreting what MG is saying - if so, please someone put up a diagram to make it more clear.
In the solution, it only considers the minimum distance to not cause an overlap, which is 2 (centre-centre distance). To me, this is more precise because it doesn't matter what the coins arrangements are - this distance will always hold. An empty space in the radius 2 covering is all areas that are at least 1 unit away from *any* coin edge, which means a coin must be able to be placed there.
MG tried to find the maximum distance between coins, which is less obvious. If two coins are 2sqrt(2) apart (centre-centre distance), is it clear that a coin can fit between them? It might be the case, but it's not obvious - other coins may come into play preventing a coin from being placed.
Maybe I'm misinerpreting what MG is saying - if so, please someone put up a diagram to make it more clear.
I think that’s it’s clear that if there is not a 1/root2 space between adjacent horizontal coins and a diameter diagonal space between diagonal coins.
The expansion to radius 2 of a coin effectively adds a diagonal space of a diameter which is what the root2 spacing is stating.
I agree that your approach is much more precise, direct, and succinct than mine. However, I think there may be a problem with both your solution and mine (and really, the entire premise of the question). The problem is the corners. The center of the closest coin to the corner could be more than 2r away from the corner, yet no new coin could fit in the corner space there becuase it couldn't fit within the edges of the table. Hence, the contradiction you pointed out is not entirely true.
I agree that your approach is much more precise, direct, and succinct than mine. However, I think there may be a problem with both your solution and mine (and really, the entire premise of the question). The problem is the corners. The center of the closest coin to the corner could be more than 2r away from the corner, yet no new coin could fit in the corner space there becuase it couldn't fit within the edges of the table. Hence, the contradiction you pointed out is not entirely true.
I think the edge case is taken care of by the fact that a coin doesn't have to be fully on a table. As long as the centre of a coin is on the table (even if it overhangs the edge) it is considered on the table.
The question could be more precisely stated that 100 coin centres are on the table.
I think the edge case is taken care of by the fact that a coin doesn't have to be fully on a table. As long as the centre of a coin is on the table (even if it overhangs the edge) it is considered on the table.
The question could be more precisely stated that 100 coin centres are on the table.
That still doesn't address what I'm getting at. Say you have a coin whose center is more than 2r away from the corner (no other coin is closer to the corner). That means, according to your solution, that another coin can be added to the table, since its center won't fall in the 2r zone. However, this contradicts what the problem says: "it is impossible to add another quarter to the table without requiring an overlap".
So the wording of the problem is causing the confusion here. When it says "impossible to add", does it mean you can't add another coin such that it rests entirely on the table, or does it mean you can't add a coin such that any part of the coin is on the table at all?
The implication is you can't add a coin to the table without overlapping another coin, and so that the coin can stably remain on the table (ie the center of the coin is on the table). The coin can overhang the table.
I was going to go with no, but then I tested it (sort of cheating I guess) and I found one.
So here's how it works: for all interior angles to be equal, the interior angles must all be 120 degrees. So you have 6 across the top. Attach 1 on the left. Because that's a 60 degree triangle the width of the polygon added for that piece is 0.5. Stick the 2 on the right, horizontal distance added 1.0. Total 7.5. Connect the 5 to the one. 2.5 horizontal travelled. 4 to the 2. Width there is 2.0. Throw the 3 in the middle of the bottom, total horizontal of the bottom three segments is 7.5 again, so they match. Looking at the height of the polygon, you've got 5+1 on one side and 4+2 as the length of your slopes. Whether it is going left or right doesn't matter, the height scales with the total length so the heights of both sides are equal (height is 6*sqrt(3)/2=3*sqrt(3)).
