
5. The eight points below are the vertices and the midpoints of the sides of a square. We would like to draw a number of circles through the points, in such a way that each pair of points lie on (at least) one of the circles.

Determine the smallest number of circles needed to do this.



5. Four of the eight points are coloured black and the other four points are coloured white in the way indicated in the figure on the left. The circle through the four black points is denoted $C_{1}$ and the circle through the four white points is denoted $C_{2}$. If two points lie on a circle $C$, we say that $C$ covers that pair of points.
![](https://cdn.mathpix.com/cropped/2024_04_17_468f1668843687551e66g-4.jpg?height=344&width=800&top_left_y=1419&top_left_x=636)

Circle $C_{1}$ covers all pairs of black points and circle $C_{2}$ covers all pairs of white points. It is easy to check that each of the $4 \cdot 4=16$ pairs consisting of a white point and a black point is covered by one of the four circles in the figure on the right. It follows that the six circles form a solution.

We will now prove that five or fewer circles do not suffice. First observe that any circle passing through more than two black points must be equal to $C_{1}$ and that any circle passing through more than two white points must be equal to $C_{2}$. Indeed, a circle is already determined by three points.

A circle passing through 2 or fewer black points covers at most one of the $\frac{4 \cdot 3}{2}=6$ pairs of black points. A solution consisting of only five circles must therefore contain circle $C_{1}$ (since otherwise at most 5 pairs of black points are covered). In the same way we see that such a solution must contain circle $C_{2}$.

Each of the remaining three circles in the (hypothetical) solution contains at most 2 black points and at most 2 white points. Such a circle covers at most $2 \cdot 2=4$ pairs consisting of a white and a black point. In total, the five circles can therefore cover at most $0+0+3 \cdot 4=12$ such pairs, while there are 16 to be covered. The five circles can therefore not form a correct solution after all. We conclude that the smallest number of circles in a solution is 6 .

