Polynomial proof This is another problem from I.M Gelfand's book that I am stuck with.
Problem 169. Assume that $x_1,\ldots,x_{10}$ are different numbers, and $y_1,\ldots,y_{10}$ are arbitrary numbers. Prove that there is one and only one polynomial $P(x)$ of degree not exceeding $9$ such that $P(x_1)=y_1,P(x_2)=y_2,\ldots,P(x_{10})=y_{10}$.
Chapter is about polynomial interpolation. Any kind of hints would be appreciated.
Thanks in advance.
 A: Hint $\rm\ p(x_1) = y_1\Rightarrow\:p(x) - y_1 = (x\!-\!x_1)\, q(x)\:\Rightarrow\: y_k - y_1 = (x_k\!-\!x_1)\, q(x_k),\:$ for $\rm\:x_k\ne x_1.\:$ By induction on degree we can solve this for $\rm\:q\:$ such that $\rm\:q(x_k) = (y_k-y_1)/(x_k-x_1).$
A: Because of a mild allergy to subscripts, I will solve a smaller problem. Let $a,b,c,d$ be distinct numbers, and let $p,q,r,s$ be any numbers. Find a polynomial $P(x)$ of degree $\le 3$ such that $P(a)=p$, $P(b)=q$, $P(c)=r$, and $P(d)=s$.
We use the polynomial
$$P(x)=A(x-b)(x-c)(x-d)+B(x-a)(x-c)(x-d)+C(x-a)(x-b)(x-d)+D(x-a)(x-b)(x-c),$$
where the numbers $A$, $B$, $C$, and $D$ will be chosen soon.
Note that when we substitute $a$ for $x$ in our expression for $P(x)$, the last three terms die. So
$$P(a)=A(a-b)(a-c)(a-d).$$
We want $P(a)=p$. That is easy to arrange by choosing
$$A=\frac{p}{(a-b)(a-c)(a-d)}.$$
In essentially the same way, we can determine $B$, $C$, and $D$. It is no harder to deal with $10$ points, or $100$.
The uniqueness part is standard field theory. 
Remark: If we are in a subscript mood, we can write out a solution of the problem for general $n$. Let 
$$Q_i(x)=\frac{\prod_{j=1}^n (x-x_j)}{x-x_i}.$$
Despite appearances, $Q_i(x)$ is a polynomial, indeed one of degree $n-1$. It is the product of all terms $x-x_j$ except $x-x_i$.
Let 
$$P(x)=A_1Q_1(x)+A_2Q_2(x)+A_3Q_3(x)+\cdots+A_nQ_n(x),$$
where the $A_i$ are constants that will be chosen soon.
If we let
$$A_i=\frac{y_i}{Q(x_i)},$$
then $P(x)$ has the desired properties. Nice compact proof. But it may be hard to see what is really going on without going through a few concrete examples, or general examples but for a small $n$, like the $n=4$ we dealt with above. 
A: In general let $P$ and $Q$ be degree $n$ polynomials that coincide in $n+1$ places, then $P-Q$ is a degree $\le n$ polynomial which is zero in $n+1$ places, but a polynomial can not have more zeros than its degree so $P-Q = 0$ and hence $P=Q$.
A: Let $\mathbb R[X]_{\le 9}$ denote that the $\mathbb R$-vector space of polynomials with degree not exceeding $9$. Consider the $\mathbb R$-linear map $\Phi\colon \mathbb R[X]_{\le 9} \to \mathbb R^{10}$, $\Phi(P) = \bigl(P(x_1), \ldots, P(x_{10})\bigr)$. Then $\Phi$ is one to one: As $P \in \mathbb R[X]_{\le 9}$ with $\Phi(P) = 0$, we have $P(x_1) = \cdots = P(x_{10}) = 0$. As $P$ has degree at most 9, it can have it most 9 zeros (unless $P = 0$). As the $x_i$ are different, $P = 0$. So $\ker \Phi = \{0\}$ and $\Phi$ is one-to-one.
Note now, that we have $\dim \mathbb R[X]_{\le 9} = 10 = \dim\mathbb R^{10}$ (a basis of the former being $1 = X^0$, $X^1, \ldots$, $X^9$), so $\Phi$ is an isomorphism. So for each $y \in \mathbb R^{10}$, $P = \Phi^{-1}(y)$ is the only polynomial with $P(x_{i}) = y_i$ for $1 \le i \le 10$.
A: I want to thank everyone for help. I also discovered another way to prove this, by the method that @Thomas Andrews & @sperners lemma suggested in my earlier question.
Let's suppose that $q(x)$ is a polynomial of degree no greater then 9, such that $q(x_1)=y_1,\ldots ,q(x_{10})=y_{10}$, and also let $r(x)=p(x)-q(x).$ $r(x)$ is polynomial of degree no greater then 9 such that $r(x_1)=p(x_1)-q(x_1)=y_1-y_1=0,\ldots,r(x_{10})=p(x_{10})-q(x_{10})=y_{10}-y_{10}=0$.
So $y_1,\ldots,y_{10}$ are all roots of $r(x)$ which is impossible since $r(x)$ is degree less then 10 unless $r(x)=0$, in which case, $p(x)-q(x)=0$, which means that $p(x)=q(x)$, this proves that there is only one polynomial of degree no greater than 9 that has such values.
