13
$\begingroup$

What is the least number of circles you need to draw, such that every cell of an 8x8 grid is crossed? A circle crosses a grid cell if one of the points on its circumference lies completely inside the cell (on the border doesn't count).

Standard version: circles may lie outside the grid. Bonus version: circles cannot lie outside the grid.

$\endgroup$
5
  • $\begingroup$ "one of the points on its circumference lies completely inside the cell": I don't understand what "completely" is meant to exclude. Can part of a point lie inside a cell? $\endgroup$
    – msh210
    Apr 1 at 11:56
  • 1
    $\begingroup$ I think it means it must be inside the cell, not on the border. This excludes literal "corner cases". $\endgroup$
    – Florian F
    Apr 1 at 12:03
  • $\begingroup$ Added clarification about meaning of "inside". Added bonus version $\endgroup$ Apr 1 at 13:29
  • $\begingroup$ @DBS not sure what you mean? $\endgroup$ Apr 4 at 1:02
  • $\begingroup$ And what happens then? $\endgroup$ Apr 4 at 16:52

3 Answers 3

14
$\begingroup$

Here is my first try. I wonder whether one can do better.

enter image description here

(actually it is not true. My first shot was 16 small circles...)

$\endgroup$
1
  • $\begingroup$ I'm pretty sure this is optimal. $\endgroup$
    – Sunny Lu
    Apr 1 at 12:33
10
$\begingroup$

Bonus version: (I claim without proof that this is optimal)

enter image description here

$\endgroup$
8
  • 1
    $\begingroup$ Do the circles go inside the corner cells? $\endgroup$ Apr 1 at 16:00
  • 2
    $\begingroup$ @DmitryKamenetsky It looks they do if the orange circles have radius less than $2+\sqrt2 \approx 3.414$, and on the flips side the four cells diagonally adjacent to the corner cells are hit when the radius is at least $8 - 2\sqrt6 \approx 3.101$, so we have some wiggle room in which every cell is crossed. $\endgroup$ Apr 1 at 22:21
  • 1
    $\begingroup$ Same here. I calculated that with circles having a radius of 3.277 and tangent to the borders, it matches best the image and the corner squares are covered. It works also with 3.166 even though it differs a bit from the image. $\endgroup$
    – Florian F
    Apr 1 at 23:06
  • 1
    $\begingroup$ @Simd I am wondering about this question too. I think it is worthy of a new puzzle, perhaps for n=1 to 20. $\endgroup$ Apr 2 at 11:03
  • 1
    $\begingroup$ Done. Thanks for the suggestion. puzzling.stackexchange.com/questions/126173/… $\endgroup$ Apr 2 at 13:18
0
$\begingroup$

I think the correct answer is 4 but I don't know how to draw the solution. Anyway, you can imagine the 8x8 grid as four 4x4 grid and, for each of these, draw a circle that cross all 4x4 squares, like the blue circle in Sunny Lu's answer.

$\endgroup$
1
  • 2
    $\begingroup$ That would not cover the four corner squares of each 4x4. $\endgroup$
    – RobPratt
    Apr 3 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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