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
Source: All-Russian MO 2024 10.3
Tags: algebra, polynomial, Polynomials, algebra proposed
internationalnick123456
24.04.2024 12:29
If $k=2n+1$, then obviously by Pigeonhole principle Lenya can achieve the goal. If $k=2n$, let $\begin{cases} P\left(x\right) = 2\left(x-x_1\right)...\left(x-x_n\right) + \left(x-x_{n+1}\right)...\left(x-x_{2n}\right) \\ Q\left(x\right) = \left(x-x_1\right)...\left(x-x_n\right) \\ S\left(x\right) =2\left(x-x_1\right)...\left(x-x_n\right) \\ R\left(x\right) =\left(x-x_1\right)...\left(x-x_n\right)+\left(x-x_{n+1}\right)...\left(x-x_{2n}\right) \end{cases}$. Then $\left\{P,Q\right\}\neq \left\{S, R\right\}$. Considering two tables $$\begin{matrix}P\left(x_1\right) & P\left(x_2\right) & ... & P\left(x_n\right) & Q\left(x_{n+1}\right) & Q\left(x_{n+2}\right) & ... & Q\left(x_{2n}\right) \\ Q\left(x_1\right) & Q\left(x_2\right) & ... & Q\left(x_n\right) & P\left(x_{n+1}\right) & P\left(x_{n+2}\right) & ... & P\left(x_{2n}\right) \end{matrix}$$and $$\begin{matrix}R\left(x_1\right) & R\left(x_2\right) & ... & R\left(x_n\right) & R\left(x_{n+1}\right) & R\left(x_{n+2}\right) & ... & R\left(x_{2n}\right) \\ S\left(x_1\right) & S\left(x_2\right) & ... & S\left(x_n\right) & S\left(x_{n+1}\right) & S\left(x_{n+2}\right) & ... & S\left(x_{2n}\right) \end{matrix}$$we see that the corresponding entries on the tables are identical. Thus, $k_{\min} = 2n+1$.
NO_SQUARES
07.06.2024 17:03
Answer: $k=2n+1$. Let $P$ and $Q$ be polynomials of one of the people (of Ilya or Sasha). Define $T(x)=P(x)+Q(x)$ and $S(x)^2=\left ( P(x)-Q(x) \right) ^2$ (so $S(x)$ is defined up to the sign). Note that $deg \ T \leqslant n$ and $deg \ S^2 \leqslant 2n$, so these polynomials are uniquely set by their values at $2n+1$ point. By this reason Lenya can find $T(x)$ and $S(x)$ (up to the sign) if $k=2n+1$. In this case we have that $\{ P(x), Q(x) \} = \{ (T(x)+S(x))/2, (T(x)-S(x))/2) \}$ and so Lenya can achieve his goal. But if $k=2n$ then for some polynomials $P,Q$ there exist at least two possible variants for $S(x)^2$. Really, if $S(x)^2$ is possible, then for some $\beta \not = 0$ we have that $S_1=(S(x)^2+\beta (x-x_1)...(x-x_{2n})$ is also works: let $R(x)=(x-x_1)...(x-x_{2n})$. It is enough to have $A(x)^2=S(x)^2+\beta R(x)$ for some $A(x)$ or $\beta R(x) = \left( A(x)-S(x) \right) \left (A(x)+S(x) \right)$ which is clearly possible: we can choose $H_1(x), H_2(x), \beta_1 , \beta _2 \not = 0$ such a $deg \ H_1=deg \ H_2=n$ and $R=H_1 \cdot H_2$ and take $\beta =\beta _1 \cdot \beta_2$ and $A(x)-S(x)= \beta_1 H_1(x), A(x)+S(x)=\beta_2 H_2(x)$. For some $\beta_1 , \beta _2$ we will have $deg \ A = deg \ S = n$. Now we can choose $T(x)$ of degree $n$ such a $deg \ (T(x) \pm S(x))/2 =n$ for both variations of $S$ and $S_1$ and Ilya should write in $\ell$-th column $(T(x_\ell) \pm S(x_\ell))/2$, while Sasha $(T(x_\ell) \pm S_1(x_\ell))/2$. In this case Lenya can't achieve his goal.