×

Anything's possible, am I right?

The polynomials $$x^2 + 2$$ and $$x^2+x-1$$ are written on a board. If the polynomials $$f(x)$$ and $$g(x)$$ are already on the board ($$f(x)$$ may equal to $$g(x)$$) we are allowed to add any of $$f(x) g(x), f(x) -g(x)$$ or $$f(x) + g(x)$$ to the board.

(a) Can the polynomial $$x$$ ever be made to appear on the board?

(b) Can the polynomial $$4x-1$$ ever be made to appear on the board?

Give proof.

• $$f(x)$$ and $$g(x)$$ can represent any two polynomials on the board

Note by Sharky Kesa
1 year, 7 months ago

Sort by:

(a) Suppose $$a, b$$ are integers. If $$f(a), g(a)$$ are divisible by $$b$$, then $$f(a)+g(a), f(a)-g(a), f(a)g(a)$$ are all divisible by $$b$$ as well. Thus the property "divisible by $$b$$ at $$x = a$$" is an invariant; they will hold for all polynomials generated.* At $$x = 3$$, $$f(x) = g(x) = 11$$ and thus both of them are divisible by $$11$$, so all polynomials generated will be divisible by $$11$$ on $$x=3$$. But $$x$$ doesn't satisfy this (since it gives $$3$$ on $$x=3$$). So it cannot appear.

(*) We can use induction to formalize this, inducting on the number of operations required to generate a polynomial. The base case is $$f, g$$ that takes zero steps; the induction step lies on the fact that if a polynomial $$p$$ can be generated (in the shortest way) from either of $$f+g, f-g, fg$$, then $$f,g$$ must be generated before $$p$$, so we can use induction there.

(b) It can appear. Let $$F_1(x) = x^2 + 2, F_2(x) = x^2 + x - 1$$. Then,

• $$F_3(x) = F_1(x) - F_2(x) = x - 3$$
• $$F_4(x) = F_3(x) F_3(x) = x^2 - 6x + 9$$
• $$F_5(x) = F_1(x) - F_4(x) = 7x - 10$$
• $$F_6(x) = ((F_5(x) - F_3(x)) - F_3(x)) - F_3(x) = 4x - 1$$
· 1 year, 7 months ago

What is the reason for choosing $$x = 3$$? In particular, if we were given 2 other (quadratic) polynomials, how do we know what to use?

Can we classify the set of polynomials which can be reached through these operations?

Hint: Bezout's Identity. Staff · 1 year, 7 months ago

Nice question :)

Hint: Find an Invariant.

Hint: Evaluate the polynomial functions at a particular point. Staff · 1 year, 7 months ago

I don't really get your problem. What are g(x) and f(x)? Are g(x) and f(x) equal to $$x^{2}+1$$ and/or $$x^{2} +x-1$$ · 1 year, 7 months ago

$$f(x)$$ and $$g(x)$$ are any two polynomials on the board. · 1 year, 7 months ago

It's any $$f(x), g(x)$$ that is written on the board. · 1 year, 7 months ago

I think f(x) and g(x) some other polynomial function · 1 year, 7 months ago

×