Waste less time on Facebook — follow Brilliant.
×

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, 1 month ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

(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\)
Ivan Koswara · 1 year, 1 month ago

Log in to reply

@Ivan Koswara 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. Calvin Lin Staff · 1 year, 1 month ago

Log in to reply

Nice question :)

Hint: Find an Invariant.

Hint: Evaluate the polynomial functions at a particular point. Calvin Lin Staff · 1 year, 1 month ago

Log in to reply

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\) Julian Poon · 1 year, 1 month ago

Log in to reply

@Julian Poon \(f(x)\) and \(g(x)\) are any two polynomials on the board. Sharky Kesa · 1 year, 1 month ago

Log in to reply

@Julian Poon It's any \(f(x), g(x)\) that is written on the board. Jake Lai · 1 year, 1 month ago

Log in to reply

@Julian Poon I think f(x) and g(x) some other polynomial function Lakshya Sinha · 1 year, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...