You are given a 5x5 set of lattice points. What is the minimum number of circles, which pass through each of the 25 points at least once?
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ Is the set a 5x5 rectangle of lattice points, or do we have 25 lattice points all over the place? $\endgroup$– new Q Open WidJan 4, 2021 at 20:56
-
1$\begingroup$ I added a picture to clarify! $\endgroup$– ThomasLJan 4, 2021 at 21:10
-
2$\begingroup$ oeis.org/A262355 $\endgroup$– RobPrattJan 4, 2021 at 22:00
-
$\begingroup$ OEIS acknowledges that doesn't seem to generalize to NxN. Also, for the same problem with circular arcs, see A187679, which doesn't seem to have been investigated at n=7 or beyond. $\endgroup$– smciJan 6, 2021 at 20:50
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
Here's a proof we can't do it with less than
5
circles.
Each circle covers at most 8 points. In fact, the max is 6 points except for these five 8-point circles:
x O x O x x O O x x x x x x x x x x x x x x O O x
O x x x O O x x O x x O O x x x x O O x x O x x O
x x x x x O x x O x O x x O x x O x x O x O x x O
O x x x O x O O x x O x x O x x O x x O x x O O x
x O x O x x x x x x x O O x x x x O O x x x x x x
Note that any two of the 8-point circles overlap at two points. This means that each one beyond the first covers 6 new points at best. So, the total point coverage from 4 circles is at most 8 + 6 + 6 + 6 = 26 points. That's just above 25 points in the grid, but this leave little slack, and we run into trouble covering the corners or center.
One of the five 8-point circles must be present. First, say it's the first-listed one:
x O x O x
O x x x O
x x x x x
O x x x O
x O x O x
Then, it's not possible to cover the center point while covering 4 points not already covered by that 8-point circle. This is because the only >4-point circle covering the center is below, with lowercase o marking redundantly covered points.
O o x x x
x x O x x
x x O x x
o O x x x
x x x x x
If it's one of the other 8-point circle, we can say it's the one below on account of symmetry.
x O O x x
O x x O x
O x x O x
x O O x x
x x x x x
Any circle that covers the top left corner gives at most 4 new points not already covered by this eight-point circle, since the only >4-point circles covering that corner are those below and reflections, with redundant points marked with lowercase o.
O o x x x O x o x x
x x O x x x x x o x
x x O x x x x x x x
O o x x x x x x O x
x x x x x O x O x x
Either way we're limited to 8 + 6 + 6 + 4 = 24 points covered.
-
$\begingroup$ The ASCII representations here were very helpful for understanding the proof. $\endgroup$– bobbleJan 5, 2021 at 2:05
-
$\begingroup$ Though, we have a 4 point circle whose origin is the center and covers the four corners $\endgroup$ Jan 5, 2021 at 2:31
-
$\begingroup$ @zixuanisbadatPuzzling That's fine, as long as there's one circle with 4 points or less, the proof goes through. $\endgroup$– xnorJan 5, 2021 at 2:31
-
$\begingroup$ "That's because the only type of circle covering >4 points including a corner is the 6-point circle below, but it covers only one corner, so we can't cover all four corners while still having our 8-point circle." Looks obviously wrong to me. (Take the large 8 point circle and move it one g.u. either horizontally or vertically.) $\endgroup$ Jan 5, 2021 at 2:32
-
$\begingroup$ @PaulPanzer Good find, let me see if I can fix this. $\endgroup$– xnorJan 5, 2021 at 2:34