Maths Olympiad Prep

Library / /363 of 520

Algebra Difficulty 7.2 National olympiad, round 2 Prove it

a) Prove that there are two polynomials in Z[x] \mathbb Z[x] with at least one coefficient larger than 1387 such that coefficients of their product is in the set {\minus1,0,1} \{\minus{}1,0,1\}.
b) Does there exist a multiple of x2\minus3x\plus1 x^2\minus{}3x\plus{}1 such that all of its coefficient are in the set {\minus1,0,1} \{\minus{}1,0,1\}

Solution

### Part (a)
1. Consider the polynomial:
f(x)=(x1)(x21)(x41)(x2n1) f(x) = (x - 1)(x^2 - 1)(x^4 - 1) \cdots (x^{2^n} - 1)
The coefficients of this polynomial are in the set {1,0,1}\{-1, 0, 1\}.

2. We can write f(x)f(x) as a product of two polynomials:
f(x)=g(x)h(x) f(x) = g(x)h(x)
where:
g(x)=(x1)n g(x) = (x - 1)^n
and
h(x)=(x+1)(x3+x2+x+1)(x2n1++1) h(x) = (x + 1)(x^3 + x^2 + x + 1) \cdots (x^{2^n - 1} + \cdots + 1)

3. By choosing nn sufficiently large, both g(x)g(x) and h(x)h(x) will have coefficients larger than 1387. This is because the coefficients of (x1)n(x - 1)^n and the terms in h(x)h(x) grow as nn increases.

4. Therefore, there exist two polynomials in Z[x]\mathbb{Z}[x] with at least one coefficient larger than 1387 such that the coefficients of their product are in the set {1,0,1}\{-1, 0, 1\}.

\blacksquare

### Part (b)
1. Assume that there exists a polynomial f(x)f(x) such that:
f(x)=(x23x+1)g(x) f(x) = (x^2 - 3x + 1)g(x)
where all coefficients of f(x)f(x) are in the set {1,0,1}\{-1, 0, 1\} and g(x)0g(x) \neq 0.

2. Write f(x)f(x) as:
f(x)=anxn+an1xn1++a1x+a0 f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0
where an>0a_n > 0.

3. Consider the lemma: If s2s \geq 2, then:
sn>sn1+sn2++s+1 s^n > s^{n-1} + s^{n-2} + \cdots + s + 1

4. Let r=3+52>2r = \frac{3 + \sqrt{5}}{2} > 2. We know that:
r23r+1=0 r^2 - 3r + 1 = 0
Therefore, rr is a root of x23x+1x^2 - 3x + 1.

5. Since f(x)=(x23x+1)g(x)f(x) = (x^2 - 3x + 1)g(x), we must have f(r)=0f(r) = 0.

6. However, all coefficients of f(x)f(x) are in the set {1,0,1}\{-1, 0, 1\} and an>0a_n > 0. Thus, we must have an=1a_n = 1.

7. By the lemma, we can prove that f(r)>0f(r) > 0, which leads to a contradiction.

8. Therefore, there does not exist a multiple of x23x+1x^2 - 3x + 1 such that all of its coefficients are in the set {1,0,1}\{-1, 0, 1\}.

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.