Puzzling Asked on May 27, 2021
You are given a 5×5 set of lattice points. What is the minimum number
of circles, which pass through each of the 25 points at least once?
Here's a proof we can't do it with less than
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.
Correct answer by xnor on May 27, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP