# 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
5 years, 6 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

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$

- 5 years, 6 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 - 5 years, 6 months ago

Nice question :)

Hint: Find an Invariant.

Hint: Evaluate the polynomial functions at a particular point.

Staff - 5 years, 6 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$

- 5 years, 6 months ago

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

- 5 years, 6 months ago

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

- 5 years, 6 months ago

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

- 5 years, 6 months ago