TUYMAADA 2005 Problem 2

Six members of the team of Fatalia for the International Mathematical Olympiad are selected from $13$ candidates. At the TST the candidates got $a_1,a_2, \ldots, a_{13}$ points with $a_i \neq a_j$ if $i \neq j$ .

The team leader has already $6$ candidates and now wants to see them and nobody other in the team. With that end in view he constructs a polynomial $P(x)$ and finds the creative potential of each candidate by the formula $c_i = P(a_i)$ .

For what minimum $n$ can he always find a polynomial $P(x)$ of degree not exceeding $n$ such that the creative potential of all $6$ candidates is strictly more than that of the $7$ others?

Proposed by F. Petrov, K. Sukhov