Ternary Polynomial

A polynomial with integer coefficients is called "ternary" if its coefficients are all 1, -1, or zero.

First Question:
Find two polynomials $P(x)$ and $Q(x)$ with integer coefficients where at least one coefficient is larger than 2010, such that $P(x)Q(x)$ is ternary.

Second Question:
Does there exist a ternary multiple of $F(x) = x^2 - 3x + 1$ ?

Solution

First Question

Note that the polynomial $(x-1)(x^2-1)(x^4-1)(x^8-1) ... (x^{2^n}-1)$ is ternary. Indeed, because the coefficient of $x^k$ can only be formed in exactly one way. For digits in the binary representation of $k$ that is one, we take the $x^{2^i}$ term, and for the other digits, we take the $-1$ term.

Now, that polynomial can be factored. For example:
$$(x-1)(x^2-1)(x^4-1)(x^8-1)$$
$$=(x-1)^{4} (x+1) (x^3+x^2+x+1) (x^7+...+1)$$
$$=(x-1)^{4) (x+1) (x+1)(x^2+1) (x+1)(x^2+1)(x^4+1)$$
$$=(x-1)^4 (x+1)^3 (x^2+1)^2 (x^4+1)$$

So similarly,
$$(x-1)(x^2-1)(x^4-1)(x^8-1) ... (x^{2^n}-1)$$
$$ = (x-1)^{n+1} (x+1)^n (x^2+1)^{n-1} ... (x^{2^{n-1}}+1) $$

If we let $P(x) = (x-1)^{n+1}$ and $Q(x)$ to be the rest, we claim that we can make the largest coefficient in $P$ and $Q$ to be arbitrarily large by setting $n$ large enough. For $P$, it is clear due to binomial expansion. For $Q$, the factor $(x+1)^n$ will have a large enough coefficient, while the rest of the factors all consist of positive signs (no negative signs).

So by setting $n$ large enough, we could find $P$ and $Q$ that satisfy the desired conditions.

Second Question

We start by proving a lemma: if $s > 2$ then $s^n > s^{n-1} + ...+ s + 1$. This lemma can be proved by induction:
$s^{n+1} > 2s^n = s^n + s^n > s^n + ... + s + 1$

Now, we note that the larger root of $F$ is greater than 2, so let $r$ be this larger root. ( $r = (3 + \sqrt{13})/2 > 2$ ).

Suppose $P$ is a ternary polynomial such that $P(x) = F(x) G(x)$ for some integer polynomial $G$, then $P(r) = 0$.

But that is impossible if $r > 2$, due to the lemma above, since the largest term in $P$ cannot be offset by the rest of the terms. A contradiction.

Largest k for arbitrary function

Find the largest number $k$ that satisfies the following property:

For every real-valued function $f$ defined over $[0,1]$, there exist $a,b,c \in [0,1]$ such that:
$$|f(ab) + f(bc) + f(ca) - abc | \geq k$$

Solution

First we show that $k = 1/6$ satisfies the condition of the problem.

For $k=1/6$, suppose to the contrary that for all $a,b,c$ chosen in the interval $[0,1]$ we have:
$$|f(ab) + f(bc) + f(ca) - abc | < \frac{1}{6}$$

Let $y = f(0),y=f(1)$.
Plugging in $a=b=c=0$ we have $|3x| < 1/6 \iff |x| < 1/18$
Plugging in $a=b=c=1$ we have $|3y-1| < 1/6$
Plugging in $a=b=1, c=0$ we have $2x+y| < 1/6$

That means $y = (2x+y) - 2x < 1/6 + 2/18 = 5/18$
But also $3y-1 > -1/6 \iff y > 5/18$, a contradiction.

Thus $k= \frac{1}{6}$ satisfies the condition of the problem.

Now we show that it is the largest such constant. We choose a function $f(x) = \frac{6x^\frac{3}{2} - 1}{18}$ and prove that
$$ -\frac{1}{6} \leq f(ab)+f(bc)+f(ca) - abc \leq \frac{1}{6}$$
for all $a,b,c \in [0,1]$

Indeed, the first inequality is equivalent to
$$(ab)^\frac{3}{2} + (bc)^\frac{3}{2} + (ca)^\frac{3}{2} \geq 3abc$$ which is true by AM-GM.

The second inequality is equivalent to
$$(ab)^\frac{3}{2} + (bc)^\frac{3}{2} + (ca)^\frac{3}{2} - 3abc \leq 1$$

Now consider the LHS, and try to find its maximum value over $a,b,c \in [0,1]$
First, we try a substitution $x = \sqrt{ab}, y = \sqrt{ac}, z = \sqrt{bc}, x,y,z \in [0,1]$ and WLOG, we may assume that $x \geq y \geq z$ (which corresponds to $a \geq b \geq c$)
So now our objective function becomes $x^3 + y^3 + z^3 - 3xyz$.

Let $g(x) = x^3 + y^3 + z^3 - 3xyz$, and fix $y,z$.
$$g(1) - g(x) = (1-x^3) - 3yx(1-x) = (1-x)(1 + x + x^2 - 3yz)$$
Because $x \leq 1$, then $1-x \geq 0$
$1+x+x^2-3yz \geq 1 + 2x^2-3yz = (1-yz) + 2(x^2 - yz) \geq 0$
So $g(1) \geq g(x)$.

So the maximum happens when the largest of 3 variables equals to 1. But this means that $ab = 1$ which implies $a=b=1$. Then $y = z = \sqrt{c}$. Our objective function now becomes:
$$x^3 + y^3 + z^3 - 3xyz = 2y^3 - 3y^2 +1$$
Let $h(y) = 2y^3 - 3y^2 + 1$, then $h(y) - h(0) = y^2(2y-3) < 0$ because $y \geq 1$. So the maximum happens when $y = 0$

In conclusion, our maximum happens when $x = 1, y=z=0$ and that's when $a=b=1, c= 0$. At this point, the maximum value is 1, thus proving our assertion.

Another way to determine the maximum value of the function above is by observing that it is a convex function on each of its variable, and all three variables are freely chosen from the interval $[0,1]$. Thus, the maximum must happen when all of its variables are zero or one. Plugging in all permutations of $(0,0,0), (0,0,1), (0,1,1), (1,1,1)$, we find that the maximum is indeed 1.

Integer Inequality

For any positive real number $t$, prove that there are integers $a,b,c,d$ such that

$! a^3b+b^3c+c^3d < tabcd$

Solution: http://dharmath.thehendrata.com/2009/11/30/solution-integer-inequality/