TransWikia.com

How many circles needed to pass through each of 5x5 lattice points?

Puzzling Asked on May 27, 2021

enter image description here

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?

One Answer

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP