Ответ. $k = [n/2]$.

Лемма. Для любых точек $A_i = (x_i, y_i)$ ($1 \le i \le n$) на плоскости, никакие три из которых не лежат на одной прямой, найдётся такой многочлен $P(x, y)$ степени не больше $[n/2]$, что $P(x_n, y_n) = 1$ и $P(x_i, y_i) = 0$ при $i = 1, \dots, n-1$.

Доказательство. Заметим, что существуют такие $d = [n/2]$ прямых, что точка $A_n$ не лежит ни на одной из них, а каждая из точек $A_1, \dots, A_{n-1}$ лежит хотя бы на одной (при нечётном $n$ это прямые $A_1A_2, A_3A_4, \dots, A_{n-2}A_{n-1}$, а при чётном $n$ — прямые $A_1A_2, A_3A_4, \dots, A_{n-3}A_{n-2}, A_{n-2}A_{n-1}$). Пусть $k_i x + \ell_i y + m_i = 0$ — уравнение $i$-й прямой ($i = 1, \dots, d$). Тогда многочлен
$$Q(x, y) = \frac{(k_1x + \ell_1y + m_1) \dots (k_dx + \ell_dy + m_d)}{(k_1x_n + \ell_1y_n + m_1) \dots (k_dx_n + \ell_dy_n + m_d)}$$
является искомым. $\square$

Покажем, что число $k = [n/2]$ подходит. При каждом $i = 1, \dots, n$ найдём согласно лемме многочлен $P_i(x, y)$, обращающийся в ноль во всех точках $A_1, \dots, A_n$, кроме $A_i$, причём $P_i(x_i, y_i) = 1$. Тогда многочлен $P(x) = c_1P_1(x, y) + \dots + c_nP_n(x, y)$ принимает требуемые значения во всех точках $A_1, \dots, A_n$.

Осталось показать, что при $k < [n/2]$ утверждение неверно. Рассмотрим точки $A_i(i, i^2)$ ($i = 1, \dots, n$), лежащие на параболе $y = x^2$, и положим $c_1 = \dots = c_{n-1} = 0$, $c_n = 1$. Поскольку парабола пересекается с прямой не более, чем по двум точкам, точки $A_i$ удовлетворяют условию. Предположим, что существует многочлен $P(x, y)$ степени, не превосходящей $k$, для которого $P(x_i, y_i) = c_i$. Положим $Q(x) = P(x, x^2)$; тогда степень $Q(x)$ не превосходит $2k$. По нашему предположению, $Q(1) = Q(2) = \dots = Q(n-1) = 0$ и $Q(n) = 1$. Таким образом, ненулевой многочлен $Q(x)$ имеет $n-1$ корень, то есть его степень не меньше $n-1$; тогда и $2k \ge n-1$. Это и значит, что $k \ge [n/2]$.