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.

Improve this question
$\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
    Commented 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
    Commented Apr 1 at 12:03
  • $\begingroup$ Added clarification about meaning of "inside". Added bonus version $\endgroup$
    – Dmitry Kamenetsky
    Commented Apr 1 at 13:29
  • $\begingroup$ @DBS not sure what you mean? $\endgroup$
    – Dmitry Kamenetsky
    Commented Apr 4 at 1:02
  • $\begingroup$ And what happens then? $\endgroup$
    – Dmitry Kamenetsky
    Commented Apr 4 at 16:52

3 Answers 3

Reset to default
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...)

Improve this answer
$\endgroup$
1
  • $\begingroup$ I'm pretty sure this is optimal. $\endgroup$
    – Sny
    Commented Apr 1 at 12:33
10
$\begingroup$

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

enter image description here

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Do the circles go inside the corner cells? $\endgroup$
    – Dmitry Kamenetsky
    Commented 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$
    – Misha Lavrov
    Commented 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
    Commented 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$
    – Dmitry Kamenetsky
    Commented Apr 2 at 11:03
  • 1
    $\begingroup$ Done. Thanks for the suggestion. puzzling.stackexchange.com/questions/126173/… $\endgroup$
    – Dmitry Kamenetsky
    Commented 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.

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

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