Initially, a non-constant polynomial $S(x)$ with real coefficients is written down on a board. Whenever the board contains a polynomial $P(x)$, not necessarily alone, one can write down on the board any polynomial of the form $P(C + x)$ or $C + P(x)$ where $C$ is a real constant. Moreover, if the board contains two (not necessarily distinct) polynomials $P(x)$ and $Q(x)$, one can write $P(Q(x))$ and $P(x) + Q(x)$ down on the board. No polynomial is ever erased from the board. Given two sets of real numbers, $A = \{ a_1, a_2, \dots, a_n \}$ and $B = \{ b_1, \dots, b_n \}$, a polynomial $f(x)$ with real coefficients is $(A,B)$-nice if $f(A) = B$, where $f(A) = \{ f(a_i) : i = 1, 2, \dots, n \}$. Determine all polynomials $S(x)$ that can initially be written down on the board such that, for any two finite sets $A$ and $B$ of real numbers, with $|A| = |B|$, one can produce an $(A,B)$-nice polynomial in a finite number of steps. Proposed by Navid Safaei, Iran
Problem
Source: RMM 2021/6
Tags: polynomial, algebra, RMM
08.11.2021 10:15
Organized solution from my mock test: The answer is all $S(x)$ for either $\deg S$ even, or $\deg S\ge 3$, $\deg S$ odd and S having negative leading coefficient. First I show all other polynomials fail. Linear polynoms fail because all polys obtained are linear or constant. Therefore, if A is an arithmetic progression and B is not, we are done. If $\deg S\ge 3$ is odd and $S$ has a positive leading coefficient, we can induct to show all polynomials on the board have odd degree and positive leading coefficients. Claim: There exist $0<d<e$ such that for all $Q$ on the board, $D\ge d, x\in \mathbb{R},$ $$Q(x)-Q(x-D)>e$$ Pf: Base Case: Note $Q$ increases at a quadratic rate when it is strictly increasing, and the interval when it is not strictly increasing is finite, as needed. Inductive Step: Suppose $P,Q$ work. $P(x+C), P(x)+C, P(x)+Q(x)$ clearly work. Since $Q(x)-Q(x-D)>e>d$, then $P(Q(x))-P(Q(x-D))>e$. Therefore, if $A=\{a_1,a_1+2d\}, B=\{b_1, b_1+\epsilon\}$, no polynomial on the board will be $(A,B)-$good. Now I'll show that all other polynomials work. We induct on $|A|$ to show for any $A=\{a_1,\cdots,a_n\},B=\{b_1,\cdots,b_n\}$ we can write a polynomial such that $f(a_i)=b_i$ for all $1\le i\le n$. Base Case: $|A|=2$ If $\deg P$ is even, then let $d=a_2-a_1, e=b_2-b_1$. Since $P(x)-P(x-d)$ is a polynomial of odd degree, it is surjective by the intermediate value theorem, so there exists $P(x)-P(x-d)=e$. Now a proper translation/shift works. If $\deg P$ is odd and $P$ has a negative leading coefficient, consider polynomials of the form $Q(x)=DP(P(x))+CP(x)$ for $D,C\in \mathbb{N}$. WLOG, $d>0$ Since $P(P(x))$ has a positive leading coefficient and degree $(\deg P)^2$, $\lim\limits_{x\to \pm \infty} Q(x)-Q(x-d)=\infty$. Therefore, it suffices to find $D,C$ such that there exists $x$ where $Q(x)-Q(x-d)<e$. Picking $D=1, C$ large enough would suffice. Inductive Step: Assume statement true for $|A|=n-1$. This means for any pairwise distinct reals $a_1,\cdots,a_{n-1}$, we can write a polynomial on the board such that $P(a_i)=b_i$ for $1\le i<n$ for any $b_i$. WTS: statement is true for $|A|=n$ Let's carefully examine what we have here. We can "control" any $n-1$ outputs at the same time, but there is little we can do to control the $n$th output if I blindly apply only the inductive hypothesis. There is an idea where I set $n-1$ outputs to be $0$, but that is too strong. We want to control $n$ elements with as weak of a guaranteed polynomial construction as possible. Note we are only 1 away from what we need. After flailing around, if I set $R(a_1)=R(a_2)$ and $R(a_2), R(a_3),\cdots, R(a_n)$ pairwise distinct (no extra conditions needed), I am done because I can draw a polynomial $Q(R(x))+T(x)$ as long as I have $T(a_1)-T(a_2)=b_1-b_2$ because I can freely set $Q(R(a_2)), Q(R(a_3)), \cdots, Q(R(a_n))$ by inductive hypothesis. Now we use some polynomial tricks. For $\deg S$ even, we will only resolve positive leading coefficients because we can get polynomials with even degree and positive leading coefficients if we start with a polynomial of even degree and negative leading coefficient. We consider $Q(x)=P(P(x)+K)$ where $K$ is a very large real such that $P$ is monotonically increasing from $x=a_1$. Let $d=Q(a_2)-Q(a_1)$. We can select $R$ and $x$ such that $R(x)=R(x-d)$. We can choose $P(a_2)<<P(a_3)<<P(a_4)<<\cdots<<P(a_n)$ and $R(Q(x))$ with an appropriate transformation works as $R$ becomes monotone. For $\deg S$ odd, the idea is to get the sum of a positive term and a negative term with a similar argument. I need to sleep and will edit this tomorrow...
09.03.2022 20:38
Here is a solution with a different inductive step. Part 1 is mine and Part 2 is a collaboration with L567. Also, I do not understand the above argument for polynomials $S(x) \in \mathbb{R}[x]$ such that $deg(S)$ is odd and the leading coefficient of $S$ is positive. CANBANKAN wrote: If $\deg S$ is odd and $S$ has a positive leading coefficient, we can induct to show all polynomials on the board have odd degree and positive leading coefficients. Therefore, if A is an arithmetic progression and B is not, we are done. $\textbf{Part 1: Reduction to Pairs}$ We have the following unexpected claim. $\textbf{Lemma 1:}$ Any function $f: \mathbb{R} \to \mathbb{R}$ satisfies the condition iff it satisfies it for all $|A| = |B| = 2$ and $|A| = |B| = 3$. $\textbf{Proof)}$ We will assume that we can satisfy the condition for $|A| = 2$, otherwise, clearly, $S$ does not satisfy the condition itself (implying one of the directions). We will induct on $|A|$, assume that $|A| = k+1$ and that the condition is satisfied for all other $|A| = |B| \leq k$, we will construct the following functions by our inductive hypothesis (ignore the polynomial-esque names given to the functions). $f: \mathbb{R} \to \mathbb{R}$ such that $f(a_1) = f(a_2) = \cdots = f(a_{k-1}) = 0, f(a_k) = 1$, define $T_1\vcentcolon =f(a_{k+1})$ $g: \mathbb{R} \to \mathbb{R}$ such that $g(a_i) = b_i$ for all $i \in {1, \cdots, k}$ and define $T_2 \vcentcolon = g(a_{k+1})$ $P: \mathbb{R} \to \mathbb{R}$ such that $P(0) = 0, P(1) = 0$ and $P(T_1) = b_{k+1}-T_2$ if $T_1 \neq 0$ $g' : \mathbb{R} \to \mathbb{R}$ such that $g(a_i) = b_i$ for all $i \in \{1, \cdots, k-1, k+1\}$ and $T_3 \vcentcolon = g(a_k)$ $P': \mathbb{R} \to \mathbb{R}$ such that $P'(0) =0$ and $P'(1) = b_k-T_3$ We can clearly write such functions down by the inductive hypothesis because the cardinalities of the interpolated points are at most $max(k,3)$, we split into two cases depending on whether $T_1$ is zero or not. $\textbf{Case 1)}$ $T_1 = 0$ Now, write $Q(x) = P'(f(x))$, then $Q(a_i) = P(f(a_i)) = P(0)$ for all $i \in \{1, \cdots, k-1,k+1\}$ and $Q(a_{k}) = P'(1) = b_k-T_3$ by the definitions of $f$ and $P'$. Finally, write down $h(x) = g'(x) + Q(x)$. Then $$h(a_i) = g'(a_i)+Q(a_i) = b_i+P(0) = b_i$$for all $i \in \{1, \cdots, k-1,k+1\}$ and $$h(a_k) = g'(a_k)+Q(a_{k}) = T_3 + P'(1) = T_3+(b_{k}-T_3) = b_{k}$$meaning that $h$ is $(A,B)$-nice. $\blacksquare$ $\textbf{Case 2)}$ $T_1 \neq 0$ In this case, again define $Q(x) = P(f(x))$, then $Q(a_i) = P(f(a_i)) \in \{P(0),P(1)\}$ for all $i \in \{1, \cdots, k\}$ meaning that $Q(a_i) = 0$ for all $i \in \{1, \cdots, k\}$, and $Q(a_{k+1}) = P(f(a_{k+1})) = P(T_1) = b_{k+1}-T_2$, then write down $h(x) = g(x)+Q(x)$. $h(a_i) = g(a_i)+Q(a_i) = b_i+0 = b_i$ for all $i \in \{1, \cdots, k\}$ and $h(a_{k+1}) = g(a_{k+1})+Q(a_{k+1}) = T_2+(b_{k+1}-T_2) = b_{k+1}$ means that $h$ is $(A,B)$-nice. $\blacksquare$ $\textbf{Part 2: Classification of Polynomials with Desired Property}$ We now have to find the polynomials that satisfy the condition in $\textbf{Lemma 1}$. We will only check $|A| = |B| = 2$, the $|A| = |B| = 3$ case follows similarly. $\textbf{Lemma 2: RMM 2021, P6}$ For any $|A| = |B|$, we can produce an $(A,B)$-nice polynomial for all non-linear polynomials $S(x)$ with even degree and those with odd degree such that the leading coefficient of $S$ is negative. $\textbf{Proof)}$ We naturally have two parts for the proof. $\textbf{Claim:}$ Polynomials $S(x) \in \mathbb{R}[x]$ such that $deg(S)$ is odd and the leading coefficient of $S$ is positive do not satisfy the condition. Moreover, linear polynomials do not satisfy the condition. $\textbf{Proof)}$ We will take $A = \{0, T\}$ and $B = \{0, \frac{T}{2}\}$ for some $T \in \mathbb{R}^{+}$ which is to be determined later. Firstly, we prove a lemma. $\textbf{Lemma 2.1:}$ There exists some $c \in \mathbb{R}$ such that for all polynomials $R(x) \in \mathbb{R}[x]$ on the board, $R'(x) > 0$ and $R(x) > x$ for all $x > c$ . $\textbf{Proof)}$ Firstly, notice that such a $c \in \mathbb{R}^{+}$ exists for $S(x)$ (the initial polynomial on the board) because $S$ is of odd degree and has positive leading coefficient, also notice that all the polynomials that are ever written on the board will have odd degree and positive leading coefficient. Now, vertical or horizontal shifts will have to be undone the eventual polynomial will have to output $P(0) = 0$, now notice that for any two polynomials $P,R$ on the board, $P'(x), R'(x) > 0$ for all $x > c$, then $G(x) = P(x) + R(x)$ will also satisfy $G'(x) = P'(x) + R'(x) > 0$ for all $x > c$, furthermore $T(x) = P(R(x))$ will also satisfy the condition because we know that $R(x) > x$ implies that $T'(x) > P'(R(x)) > P'(x) > 0$, as desired. $\blacksquare$ Now, we are immediately done by taking $T = c$. Furthermore, for linear polynomials, we may simply take $A = \{0, 1, 2\}$ and $B = \{0,1,4\}$ and clearly all the polynomials on the board are linear meaning that the image of $A$ will be an arithmetic progression which $B$ is not. $\blacksquare$ $\textbf{Claim:}$ All other polynomials satisfy the condition. $\textbf{Proof)}$ Suppose $S$ is of even degree, consider the polynomial $S(x+a) - S(x)$, it has odd degree and is therefore surjective, so we can find a $z$ such that $S(z+a) - S(z) = b$, generate the polynomial $P(x) = S(x+z) - S(z)$, which satisfies $P(0) = 0, P(a) = b$. Suppose $S$ is now of odd degree and has negative leading coefficient, then we can generate $S(S(x))$ which has odd degree and positive leading coefficient. Consider two numbers such that $X+Y = b$ such that $X$ is sufficiently positive and $Y$ is sufficiently negative; since $S(x+a) - S(x)$ covers all sufficiently negative numbers and $S(S(x+a)) - S(S(x))$ covers all sufficiently positive numbers, we can find $z_1$ such that $S(z_1 + a) - S(z_1) = Y$ and $z_2$ such that $S(S(z_2+a)) - S(S(z_2)) = X$, now generate the polynomial $Q(x) = S(x+z_1) + S(S(x+z_2))$, an appropriate shift will satisfy the condition. $\blacksquare$ @2below I have edited Lemma 1 appropriately, thanks for pointing this slight gap out.
10.03.2022 03:14
bora_olmez wrote: Here is a solution with a different and in my opinion simpler inductive step. Part 1 is mine and Part 2 is a collaboration with L567. CANBANKAN wrote: If $\deg S$ is odd and $S$ has a positive leading coefficient, we can induct to show all polynomials on the board have odd degree and positive leading coefficients. Therefore, if A is an arithmetic progression and B is not, we are done. My bad, I think I messed up the order. This is for linear polynms.
14.05.2022 13:35
Question: In the solution from post #3, in the proof of Lemma 1, I don't understand how $P$ can be always defined. If it happens that $T_1=0$, then how can we guarantee that both \[P(0)=0\ \text{and}\ P(T_1)=b_{k+1}-T_2\]hold?
16.11.2023 23:12
Solved with lrjr24. Linear $S$ obviously do not work, because all of our operations preserve this linearity property, and we can easily pick two sets $A$ and $B$ of magnitude so that we cannot pick three collinear points. (e.g. $A={0,1,2}, B={0,100,1434}$). Henceforth assume $S$ is nonlinear. The answer is $S(x)$ works unless it is odd degree with positive leading coefficient. Call a polynomial $N$-cool if for all $y$ at least $N$ and for all $x$, $P(x+y) \ge P(x)+N$ Step 1: All odd degree polynomials with positive coefficients are $N$-cool for some positive $N$ If you take the derivative of $P(x)$ it is a positive constant coefficient even degree polynomial, so the derivative is only less than $2$ for a finite length interval, and it is bounded below. This means that if we choose a large enough interval, we can guarantee that the average derivative on this interval is at least $1$ no matter where this interval is positioned. Let $N$ be such that all intervals of length $N$ have average derivative at least $1$. This is equivalent to $N$-coolness by fundamental theorem of calculus. Step 2: $N$-coolness is preserved by all of our operations. Clearly it should be preserved by the shifting operations. If $P$ and $Q$ are both $N$-cool, then for $y \ge N$ we have $P(x+y)+Q(x+y) \ge P(x)+Q(x)+2N \ge P(x)+Q(x)+N$. Let $y\ge N$. Observe that $Q(x+y) \ge Q(x)+N$. Let $Q(x+y)=Q(x)+y'$ for $y' \ge N$. Then $P(Q(x+y))=P(Q(x)+y') \ge P(Q(x))+N$, so $N$-coolness is also preserved by composition. Step 3: Odd degree polynomials with positive coefficients don't work. Let $N$ be such that $S(x)$ is $N$-cool. Simply choose $A=0,N$ and $B=0,\frac{N}{2}$. This violates $N$-coolness, which is preserved. I now claim that for the remaining polynomials that I have not already excluded, we can in fact hit any set of $n$ ordered pairs of points as long as their $x$-coordinates are all distinct. Step 4: If $S(x)$ is not an odd degree positive leading coefficient polynomial, then we can solve the $n=2$ case Let $a=a_2-a_1$, and let $b=b_2-b_1$. Because we are allowed to shift, we merely want to write a polynomial on the board that satisfies $S(x+a)=S(x)+b$. If $P$ is of even degree, then $S(x+a)-S(x)-b$ is a polynomial that has a real root because it is odd degree, so we are done. If $S(x)$ is odd degree and negative leading coefficient, let $B$ be the set of possible values of $P(x+a)-P(x)$, where $P$ is a polynomial that could be written on the blackboard. I claim $B$ is all real numbers. Because $B$ is additive, it suffices to show that there exists an interval in $B$ which contains positive numbers and an interval in $B$ which contains negative numbers. Once we have these, we can add them together in some integer combination to hit all the real numbers. Because $S(x)$ has a negative leading coefficient and is of odd degree $>1$, $S(x+a)-S(x)$ is eventually arbitrarily negative, which implies by continuity we have an interval in $B$ which contains negatives. Similarly, $S(S(x))$ has a positive leading coefficient, so $S(x+a)-S(x)$ is eventually arbitrarily positive. Again by continuity we get an interval in $B$ which contains positive numbers. Thus we are done. Step 5: The $n=2$ case implies that we can solve it for all $n>2$. We prove this by induction. Assume the ordered pair version of the problem has been solved up to $n=k\ge 2$ for some $S(x)$. Let our ordered pairs be $(a_i,0)$ for $1 \le i \le k$ and let the $k+1$th pair be $(a_{k+1},b_{k+1})$. Using polynomial addition on these sets of ordered pairs with only one nonzero y-value we can get all sets of ordered pairs. By the $n=k$ case, we can write a polynomial $P(x)$ such that $P(a_i)=0$ for $1 \le i \le k$. By the $n=2$ case we can write a polynomial $Q(x)$ such that $Q(P(a_{k+1}))=Q(0)+b_{k+1}$ for some $x$. Now consider the polynomial $Q(P(x))-Q(0)$. For $1 \le i \le k$ we have $Q(P(a_i))-Q(0)=Q(0)-Q(0)=0$, and we also have $Q(P(a_{k+1}))-Q(0)=b_{k+1}$ by our above choice. Thus the $k+1$ case is proven. After all this, I'm still not sure if I learned anything from this problem except that algebra is the worst subject. (EDIT: As written, this solution does not work, as it contains the problem pointed out by the post above, and it is slightly annoying to patch. It suffices to show that for $a_{k+1}$, we can find some $P(x)$ such that $P(a_{k+1})$ is unique among the outputs of $P(a_i)$, and that at least two other elements of $A$, say $a_i$ and $a_j$ satisfy $P(a_i)=P(a_j)$. With a little bit of work, we can get that this is possible provided we have already solved the $n=4$ case. Now this solution sort of devolves into a bash. I'm essentially trying to use the inductive argument from step 5, but patching up the holes as I go. Using the $n=2$ case we can get the $n=3$ case by spamming additivity and getting that for some polynomial $P$ we can write down $(a_1,P(a_1)), (a_2,P(a_2), (a_3,P(a_3))$ must be collinear if our argument breaks down and the problem mentioned above arises. The $n=4$ case is much easier now that we have $n=3$. Even if the problem arises, we can do a bit of additivity stuff cyclically and shift to get the thing we want. I might write this up later, but knowing myself, I probably won't.)