Maths Olympiad Prep

Library / /118 of 144

Algebra Difficulty 8.7 Shortlist Find the answer

A magician intends to perform the following trick. She announces a positive integer nn, along with 2n2n real numbers x1<<x2nx_1 < \dots < x_{2n}, to the audience. A member of the audience then secretly chooses a polynomial P(x)P(x) of degree nn with real coefficients, computes the 2n2n values P(x1),,P(x2n)P(x_1), \dots , P(x_{2n}), and writes down these 2n2n values on the blackboard in non-decreasing order. After that the magician announces the secret polynomial to the audience. Can the magician find a strategy to perform such a trick?

A number or a short expression. Spacing and $ signs are ignored.

Solution

To address the problem, let's analyze the strategy needed for the magician to identify the polynomial P(x) P(x) of degree n n based on the 2n 2n values provided in non-decreasing order on the blackboard.

Given:
- The magician knows a positive integer n n .
- The magician knows ordered real numbers x1<x2<<x2n x_1 < x_2 < \dots < x_{2n} .
- The magician is given the non-decreasing values P(x1),P(x2),,P(x2n) P(x_1), P(x_2), \dots, P(x_{2n}) (but not which value corresponds to which xi x_i ).

The polynomial P(x) P(x) of degree n n has real coefficients and is determined by these n+1 n+1 coefficients, which we will refer to as a0,a1,,an a_0, a_1, \ldots, a_n .

Key Insight:
A polynomial P(x) P(x) of degree n n with real coefficients can be expressed as:
P(x)=anxn+an1xn1++a1x+a0. P(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0.

### Requirements and Limitations:

- The main challenge for the magician is that the specific pairing of the 2n 2n values with the xi x_i 's is unknown, due to the reordering in non-decreasing sequence.
- This reordering could correspond to any permutation of the 2n 2n original calculated values, masking the association with the specific xi x_i 's.
- Since a polynomial of degree n n can have at most n n distinct real roots, knowing the specific values doesn't directly provide the necessary associations to determine the coefficients, given the non-unique correspondence from 2n 2n possible matches.

### Conclusion:

Considering the above analysis and constraints, the inability to uniquely determine P(x) P(x) arises from the excess potential permutations and combinations inherent in the non-decreasing untagged order, making it impossible to exactly ascertain the coefficients of the polynomial.

Thus, the magician cannot uniquely determine the polynomial P(x) P(x) with the given setup and constraints. The conclusion is that there is no strategy for the magician to perform the trick successfully.

Hence, the final answer is:
No \boxed{\text{No}}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.