×

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
2 years ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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$$

- 2 years 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 - 2 years ago

Nice question :)

Hint: Find an Invariant.

Hint: Evaluate the polynomial functions at a particular point.

Staff - 2 years 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$$

- 2 years ago

$$f(x)$$ and $$g(x)$$ are any two polynomials on the board.

- 2 years ago

It's any $$f(x), g(x)$$ that is written on the board.

- 2 years ago

I think f(x) and g(x) some other polynomial function

- 2 years ago