Construct a set $S$ of polynomials inductively by the rules: (i) $x\in S$; (ii) if $f(x)\in S$, then $xf(x)\in S$ and $x+(1-x)f(x)\in S$. Prove that there are no two distinct polynomials in $S$ whose graphs intersect within the region $\{0 < x < 1\}$.
Problem
Source: USAMO 1987 Problem 3
Tags: algebra, polynomial, induction, algebra unsolved
26.07.2011 18:36
Moderator note: the wording of this post originally was the following: Quote: $X$ is the smallest set of polynomials $p(x)$ such that: 1. $p(x) = x$ belongs to $X$. 2. If $r(x)$ belongs to $X$, then $x\cdot r(x)$ and $(x + (1 - x) \cdot r(x) )$ both belong to $X$. Show that if $r(x)$ and $s(x)$ are distinct elements of $X$, then $r(x) \neq s(x)$ for any $0 < x < 1$. Let $\phi, \psi : \mathbb{C}[x] \to \mathbb{C}[x]$ be given by $\phi(f) = xf, \psi(f) = x+(1-x)f$. I claim that: \[ X = X' = \{ g_1(g_2(\cdots(g_n(x)\cdots)) \mid g_i \in \{\phi,\psi\}, n \in \mathbb{N}_0 \} \]By induction we conclude that $X' \subseteq X$, and $X \subseteq X'$ follows from the fact that $X'$ satisfies the 2 conditions in the problem statement. I'll prove that $\forall f \in X, y \in (0,1): f(y) \in (0,1)$. I'll prove it by induction on $\deg f$. For $\deg f = 1$ we get $f=x$ and then $\forall y \in (0,1): f(y) \in (0,1)$ is clear. Assume that it is true for all $f \in X$ s.t. $\deg f \le m$. Let $f \in X$ s.t. $\deg f = m+1$. If $f = \phi(g) = xg$ for some $g \in X$, then $\forall y \in (0,1): f(y) = yg(y) \in (0,1)$ If $f = \psi(g) = x+(1-x)g$ for some $g \in X$, then $\forall y \in (0,1): f(y) = y + (1-y)g(y) \le y+(1-y)y = 1-(1-y)^2 \in (0,1)$. Now assume that there are $f,g \in X, y \in (0,1)$ s.t. $f(y) = g(y)$, with $f = f_1(\cdots(f_r(x))\cdots), g = g_1(\cdots(g_s(x))\cdots), f_i,g_i \in \{\phi,\psi\}$, and choose $f,g$ s.t. $r+s$ is minimal. $f_1 \neq g_1$ since we assumed that $r+s$ was minimal. So wlog assume $f_1 = \phi, g_1 = \psi$, and let $f = \phi(p)=xp, g = \psi(q)=x+(1-x)q$. So $f-g = x(p-1)-(1-x)q$. And hence $(f-g)(y) = f(y)-g(y) = 0$. But $(f-g)(y) = y(p(y)-1)-(1-y)q(y) < 0$. Contradiction. QED