10.10. Petya thought of two polynomials $f(x)$ and $g(x)$, each of the form $a x^{2} + b x + c$ (i.e., the degree of each polynomial does not exceed 2). On each turn, Vasya names a number $t$, and Petya tells him (at his discretion) one of the values $f(t)$ or $g(t)$ (without specifying which one he reported). After $n$ turns, Vasya must determine one of Petya's polynomials. For what smallest $n$ does Vasya have a strategy that guarantees he can achieve this?

(M. Antipov)
Answer. When $n=8$.

Solution. We will call a polynomial of the form $a x^{2}+b x+c$ simply a polynomial, and the graph of such a polynomial - simply a graph. We will use the following well-known lemma.

Lemma. Through any three points $\left(a_{i}, b_{i}\right)(i=1,2,3)$ with different abscissas, there passes exactly one graph.

Proof. One graph passing through these points always exists - it is not difficult to verify that the polynomial

$$
\begin{aligned}
b_{1} \frac{\left(x-a_{2}\right)\left(x-a_{3}\right)}{\left(a_{1}-a_{2}\right)\left(a_{1}-a_{3}\right)} & +b_{2} \frac{\left(x-a_{1}\right)\left(x-a_{3}\right)}{\left(a_{2}-a_{1}\right)\left(a_{2}-a_{3}\right)}+ \\
& +b_{3} \frac{\left(x-a_{1}\right)\left(x-a_{2}\right)}{\left(a_{3}-a_{1}\right)\left(a_{3}-a_{2}\right)}
\end{aligned}
$$

fits. On the other hand, if two different polynomials $f(x)$ and $g(x)$ pass through three points, then the difference $f(x)-g(x)$ has three roots $a_{1}, a_{2}, a_{3}$, which is impossible.

From the lemma, it follows that through any two points with different abscissas, there pass infinitely many graphs, and any two of them intersect only at these two points.

Let's move on to the solution. We will assume that Petya thought of two graphs, and Vasya names a number $t$ to Petya on each move, and Petya marks a point with abscissa $t$ on one of the graphs. We can assume that on different moves, Vasya names different $t$ (otherwise, Petya will repeat the answer).

Consider the situation after $k$ moves. We will call a pair of graphs suitable if the union of these graphs contains all the points marked by Petya.

1) We will show that $k \geqslant 8$. We will assume that Petya initially does not draw any graphs, but simply marks some points with given abscissas. We will show how he can act so that after 7 moves, there are two suitable pairs of graphs such that all 4 graphs are different; this will mean that Vasya did not manage to achieve the required, because Petya could have drawn any of these pairs.

We will denote the point appearing after the $i$-th move as $A_{i}=\left(a_{i}, b_{i}\right)$. On the first two moves, Petya chooses $b_{1}=b_{2}=0$. On the next 4 moves, Petya marks points $A_{3}$ and $A_{4}$ on the graph $F_{+}$ of the polynomial $f_{+}(x)=\left(x-a_{1}\right)\left(x-a_{2}\right)$ and points $A_{5}$ and $A_{6}$ - on the graph $F_{-}$ of the polynomial $f_{-}(x)=-\left(x-a_{1}\right)\left(x-a_{2}\right)$.

On the seventh move, Petya chooses a point $A_{7}$ that does not lie on any graph passing through any three points from $A_{1}, A_{2}, A_{3}, A_{4}, A_{5}$, and $A_{6}$. Then there exist graphs $G_{+}$ and $G_{-}$ passing through the triplets of points $A_{5}, A_{6}, A_{7}$ and $A_{3}, A_{4}, A_{7}$; according to our choice, these graphs are different and distinct from $F_{+}$ and $F_{-}$. Thus, the pairs $\left(F_{+}, G_{+}\right)$ and $\left(F_{-}, G_{-}\right)$ are suitable and all these four graphs are different, which means that Vasya will not be able to achieve the required.

2) We will show how Vasya can achieve the required in 8 moves. On the first 7 moves, he names 7 arbitrary different numbers. We will call a graph suspicious if it passes through at least three points marked by Petya on these moves. We will call a number $a$ bad if two different suspicious graphs have a common point with abscissa $a$. There are only a finite number of suspicious graphs and, consequently, only a finite number of bad numbers.

On the eighth move, Vasya names any non-bad number $a_{8}$. After Petya marks the eighth point, there are two cases.

Case 1. There exists a graph $G$ of the polynomial $f(x)$ containing five of the eight marked points. Three of these points lie on one of Petya's graphs; by the lemma, this graph coincides with $G$. Therefore, Vasya only needs to name the polynomial $f(x)$.

Case 2. Such a graph does not exist. This means that on each of Petya's graphs, there lie exactly 4 marked points; therefore, both of these graphs are suspicious. We will prove that there is a unique pair of suspicious graphs containing all 8 marked points in total; then Vasya only needs to name any of the corresponding polynomials.

Let $\left(G_{1}, H_{1}\right)$ and $\left(G_{2}, H_{2}\right)$ be two such pairs, where $H_{1}$ and $H_{2}$ contain $A_{8}$. According to the choice of the number $a_{8}$, this can only happen if $H_{1}=H_{2}$. But then each of the graphs $G_{1}$ and $G_{2}$ passes through 4 marked points not lying on $H_{1}$, and they coincide according to the lemma. Therefore, our pairs coincide.

Remark 1. If Petya does not mark 4 points lying on one graph in the first 6 moves, then Vasya will be able to find one of the polynomials on the seventh move, acting similarly to the described above.

Remark 2. With the described strategy of Vasya, it can happen that there are two different pairs of suspicious pairs, each of which contains all 8 marked points in total. For example, if points $A_{3}, A_{4}, \ldots, A_{8}$ lie on one graph $F$, and the triplets of points $\left(A_{1}, A_{2}, A_{3}\right)$ and $\left(A_{1}, A_{2}, A_{4}\right)$ define graphs $G_{1}$ and $G_{2}$, then the pairs $\left(F, G_{1}\right)$ and $\left(F, G_{2}\right)$ are suitable.

Comment. The lemma from the solution above is considered well-known; no points are deducted for the absence of its proof, and no points are awarded for its presence.

Only the answer - 0 points.

Any complete solution consists of two parts; points obtained for different parts are added together.

Part 1: Proof that Vasya will not be able to achieve the required in 7 questions (maximum 4 points).

Complete proof - 4 points.

Only proved that Vasya will not be able to achieve the required in 6 moves - 1 point (not added to points for other progress in this part).

Part 2: Proof that Vasya will be able to achieve the required in 8 moves (maximum 3 points).

Complete proof - 3 points.

An algorithm is provided that allows Vasya to achieve the required, but the justification is absent or incorrect - 1 point.

There is no correct algorithm, but there is an idea of choosing the last number $a_{k}$ named by Vasya so that no two suspicious graphs intersect at a point with abscissa $a_{k}-1$ point (not added to the previous).

If the justification of the correct algorithm works in one of the cases considered above, but misses another case (or is incorrect in this case) - 1 point is deducted.

It is not difficult to prove that Vasya will be able to achieve the required in 9 moves (since two pairs of graphs have only 8 common points). If in Part 2 only this is proved - 1 point is given. This point is not added to other progress in this part.