I placed 120 unit squares inside a $20\times 25$ rectangle. Prove that it is possible to place a circle with an unit diameter (with a diameter witj length 1), such that it doesn’t have a common point with any of the squares!

I love combinatorical problems, but I couldn’t solve it. I don’t know how to start. Maybe coloring? I am sure it uses pigeonhole/principle.

  • $\begingroup$ A circle with unit diameter is contained inside an unit square. Then a $20\times 25$ rectangle could contain up to $500$ unit square then after you've added all the $120$ squares remain certainly space for another square (and then for a circle). $\endgroup$ – Jihlbert Nov 21 '18 at 22:11
  • $\begingroup$ Are the vertices of the squares required to have integer coordinates? (I suspect that it's true without this requirement, but that it will be quite a bit trickier to prove.) $\endgroup$ – Rob Arthan Nov 21 '18 at 22:12

I think the best way to approach this is to reframe the question. Instead of trying to stop a circle from overlapping unit squares, we're going to start with the set of points in which we're "allowed" to place the center of the circle and slowly remove points. If there are any points left when we're done, we know we can place the center of the square there.

First note that the center of the circle needs to be at least 0.5 units away from the edge of the rectangle, so we're working with an area of $19*24 = 456$ square units.

Consider a single unit square and imagine a 2x2 square forcefield surrounding the unit square, but round the corners of the force field so they become quarter circles as pictured below.

enter image description here

If you place the center of the circle anywhere in this region, the center of the circle will be within 0.5 units from some point in the unit square, which means the circle will overlap the square. So we can't put the center of the circle in any of these points. The area of this set of points is $3+\frac{\pi}{4}\approx3.785$ units (One unit square, four rectangles, four quarter-circles). We can surround each unit square with a set of disallowed points like this for a total area of $120 * (3+\frac{\pi}{3}) \approx 454$ units. But the area we started with was $456$ units, so even if we are able to optimally spread out the unit squares so that no two of the forcefields overlap, there will still be a small area left over in which we can put the center of the circle.

  • $\begingroup$ +1 good hint.... $\endgroup$ – achille hui Nov 22 '18 at 0:01
  • $\begingroup$ I couldn’t finish your solution... Can you please post the full solution? Thanks $\endgroup$ – Ti Tu Lea Nov 22 '18 at 5:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.