AoPS - Problem

Source: China TST 1988, problem 8

Tags: algebra, polynomial, induction, algebra unsolved

orl

27.06.2005 12:34

There is a broken computer such that only three primitive data $c$, $1$ and $-1$ are reserved. Only allowed operation may take $u$ and $v$ and output $u \cdot v + v.$ At the beginning, $u,v \in \{c, 1, -1\}.$ After then, it can also take the value of the previous step (only one step back) besides $\{c, 1, -1\}$. Prove that for any polynomial $P_{n}(x) = a_0 \cdot x^n + a_1 \cdot x^{n-1} + \ldots + a_n$ with integer coefficients, the value of $P_n(c)$ can be computed using this computer after only finite operation.

Proof:Lemma:For all $n\in Z$,we can compute $x+n$ from $x$ using this computer after only finite operation. the proof of lemma:It's obvious that $n=0$, If $n<0$,let $u=x,v=1$,$uv+v=x+1$,so like this after $n$ operations we have $x+n$. If $n<0$,let $u=x,v=-1$,$uv+v=-x-1$;then let $u=-x-1,v=1$,$uv+v=-x$,like this after $-n$ operations we have $-x-n-1$;then let $u=-x-n-1,v=-1$,$uv+v=x+n$.So we get the lemma. We use induction to prove the origin problem. $n=0$,by lemma,we can compute any $P_0(c)=a_0\in Z$ from $c$ using this computer after only finite operation. Then we suppose that $n=k$ the conclusion is correct. For $n=k+1$,first we can get $y=a_0c^{n-1}+a_1c^{n-2}+\ldots+a_{n-1}-1$ by the assumption. Then let $u=y,v=1$,$uv+v=a_0c^n+a_1c^{n-1}+\ldots+a_{n-1}c$. Then by lemma we can compute $P_n(c)=a_0c^n+a_1c^{n-1}+\ldots+a_{n-1}c+a_n$ from $a_0c^n+a_1c^{n-1}+\ldots+a_{n-1}c$ using this computer after only finite operation.So it's also correct for $n=k+1$ and we know the conclusion is correct for any nonegative integer $n$.