MathDB

Let

n

be a positive integer. Ilya and Sasha both choose a pair of different polynomials of degree

n

with real coefficients. Lenya knows

n

, his goal is to find out whether Ilya and Sasha have the same pair of polynomials. Lenya selects a set of

k

real numbers

x_1<x_2<\dots<x_k

and reports these numbers. Then Ilya fills out a

2 \times k

table: For each

i=1,2,\dots,k

he writes a pair of numbers

P(x_i),Q(x_i)

(in any of the two possible orders) intwo the two cells of the

i

-th column, where

P

and

Q

are his polynomials. Sasha fills out a similar table. What is the minimal

k

such that Lenya can surely achieve the goal by looking at the tables? Proposed by L. Shatunov

Problem Statement