Problem 670

3. On a line, there are 16 points $A_{1}, \ldots A_{16}$, spaced $1 \mathrm{~cm}$ apart. Misha constructs circles according to the following rules:

a) The circles do not intersect or touch.

b) Inside each circle, there is at least one of the specified points $\mathrm{A}_{1}, \ldots \mathrm{A}_{16}$.

c) None of these points lie on the circle.

d) Different circles contain different sets of points. For example, if one circle contains points $\mathrm{A}_{1}$ and $\mathrm{A}_{2}$ inside and the rest outside, then it is not possible to construct another circle that contains only $\mathrm{A}_{1}$ and $\mathrm{A}_{2}$ inside.

What is the maximum number of circles Misha can construct according to these rules?

Answer: 31.