Evolving Polynomial

On the Cartesian field, each lattice point $(x,y)$ is initially assigned the number $x^2+y^2-1$.

At each step, if $A(x,y)$ represents the number on $(x,y)$, that number is increased by: $$\frac{(x-y) \left( A(x+1,y) + A(x,y-1) - A(x-1,y) - A(x,y+1) \right)}{4}$$

All the additions are done simultaneously.

1. Prove that the numbers at each point are always integers

2. Prove that, aside from the initial configuration, there is never a number that is divisible by 3

Solution

The recursion formula guarantees that $A(x,y)$ is always a polynomial in $x,y$, with real coefficients. In the initial configuration, $B(x,y) = A(x,y) + 1 = x^2+y^2$ is homogeneous in $x,y$ with degree 2. That is, $B(kx,ky) = k^2 A(x,y)$. We will show that this homogeneity is maintained by the recursion formula, and therefore will hold true at all times.

Suppose $A(x,y) = P.x^2 + Q.xy + R.y^2 - 1$ for some real numbers $P,Q,R$ then the recursion formula maintains it. This is because $A(x+1,y) - A(x-1,y)$ cancels out the $x^2,xy,y^2,1$ terms, so only $x,y$ terms are left. Similarly $A(x,y+1) - A(x,y-1)$ will also only preserve $x,y$ terms. So the second factor is homogenous with degree 1, but the factor $(x-y)$ is also homogenous with degree 1, so the added number is homogeneous with degree 2. Therefore, the final number is still of the form $A(x,y) = P'.x^2 + Q'.xy + R'.y^2 - 1$ (for some $P',Q',R'$ constants that may be different from the previous iteration).

Now we also notice that $A(x,y) = A(y,x)$ for all time. This property is preserved in the beginning, but also preserved by the recursion, so the numbers are symmetric with respect to $x,y$. Therefore $P = R$.

Next, we notice that for $x=y$, the additions are always zeros, so $A(x,x) = 2x^2-1$ for all time. Therefore $A(x,x) = (2P+Q)x^2-1 = 2x^2-1$ so $2P+Q = 2$.

This means that, because $Q = 2- 2P$, $A(x,y) = Px^2 + (2-2P)xy + Py^2 - 1= (x^2+y^2 - 1) + (P-1)(x-y)^2$ for some $P$ real (not necessarily integer) that depends on $t$. So we've shown that $A(x,y)$ has the form $(x^2+y^2-1) + K_t(x-y)^2$ for some $K_t$, where $K_0 = 0$.

Then, plugging in to the original recursion formula, we can see: $$(K_{t+1} - K_t)(x-y)^2 = \frac{x-y}{4} ( 4x - 4y +K_t(2(x-y+1)^2 -2(x-y-1)^2))$$ $$(K_{t+1} - K_t)(x-y)^2 = \frac{x-y}{4} ( 4x - 4y +8K_t(x-y))$$ $$K_{t+1} = 3K_t + 1$$ From there, it's a simple matter to see that $K_t = \frac{3^t-1}{2}$ because $K_0 = 0$, but we didn't need to solve the recursion. The fact that $K_0 = 0$ is enough to prove that $K_t$ is always an integer, and that, except for $t=0$, it's always $\equiv 1 \mod 3$.

Because $K_t$ is always an integer then $A(x,y)$ is also integral everywhere. And because $K_t \equiv 1 \mod 3$ then we can check that for any combinations of $x,y \mod 3$, $A(x,y)$ will never be $\equiv 0 \mod 3$.

Symmetric Function in 3 Variables

A function $f$ is defined from a triplet of positive reals to a positive real number $f:R_+^3 \to R_+$ and satisfies the following:

1. $f$ is symmetric in all 3 variables. That is $f(a,b,c) = f(b,a,c) = f(a,c,b) = ...$
2. For any positive real $t$, $f(ta,tb,tc) = tf(a,b,c)$
3. $f(1/a, 1/b, 1/c) = 2011^2/f(a,b,c)$
4. $f(a,b,c) = f(\sqrt{ab}, \sqrt{ab}, c)$

Determine how many triplet of positive integers $(x,y,z)$ are there such that $f(1/x,1/y,1/z) = 1$

Solution

From rule 3, we have $f(1,1,1) = 2011^2/f(1,1,1)$, so $f(1,1,1) = 2011$.

Now, for any $u,v > 0$,
$f(u,v,1/(uv)) = f(\sqrt{uv}, \sqrt{uv}, 1/(uv))$ using rule 4
and
$f(uv,1,1/(uv)) = f(\sqrt{uv}, \sqrt{uv}, 1/(uv))$ using rule 4
So
$f(u,v,1/(uv)) = f(uv,1,1/(uv)) = f(uv, 1/(uv), 1) = f(1,1,1) = 2011$

Now, for any $t,u,v$, let $k = \sqrt[3]{tuv}$, then $t = k^3/uv$
$f(t,u,v) = f(k^3/uv, u, v) = kf(k^2/uv, u/k, v/k) = kf(u/k, v/k, 1/((u/k)(v/k))) = 2011k = 2011\sqrt[3]{tuv}$

Thus $f(t,u,v) = 2011\sqrt[3]{tuv}$ for all $t,u,v$.

Now we need to determine the number of positive integer triples $(x,y,z)$ such that
$$f(1/x,1/y,1/z) = \frac{2011}{\sqrt[3]{xyz}} = 1$$
$$xyz = 2011^3$$
Since 2011 is a prime, there are only the following possibilities:
1. $(1,1,2011^3)$ and all its permutations, there are three triplets.
2. $(1,2011, 2011^2)$ and all its permutations, there are six triplets.
3. $(2011,2011,2011)$, there is one triplet.

So in total, there are ten triplets that satisfy the condition.

The above conditions could be tailored to fit any symmetric functions. For example, for $f = a^2 + b^2 + c^2 + k$ one can have the following conditions:

1. $f$ is symmetric
2. $f(\sqrt{a^2+t},b,c) = f(a,b,c) + t$
3. Any condition that would determine $f(0,0,0)$
4. $f(a,b,c) = f(\sqrt{(a^2+b^2)/2},\sqrt{(a^2+b^2)/2},c)$

Likewise, for $f = ab+bc+ca$ one can have the following conditions (really hard):
1. $f$ is symmetric
2. $f(a+t,b,c) = f(a,b,c) + t(b+c)$
3. Any condition that would determine $f(0,0,0)$
4. $f(a,b,c) = f(k,k,c)$ where $k = \sqrt{(a+c)(b+c)}-c$

a,b,c integers and cubic number

Suppose $a,b,c$ are positive integers such that $\frac{a}{b} + \frac{b}{c} + \frac{c}{a}$ is an integer. Prove that $abc$ is a cubic number.

Solution

We have $ab^2 + bc^2 + ca^2 = kabc$ for some k.

Let $d = \gcd(a,b,c)$. We can replace $a,b,c$ by $a/d, b/d, c/d$ respectively and the problem does not change. Thus, without loss of generality, we may assume that $d = 1$.

Let $p$ be a prime that divides $abc$, which means $p$ divides at least one of $a,b,c$. We also know that $p$ cannot divide all three, since $d = 1$.

If $p$ divides exactly one of $a,b,c$, for example $a$, then $ab^2, ca^2, kabc$ are all divisible by $p$, but not $bc^2$. Impossible. Thus, $p$ must divide exactly two of $a,b,c$.

Suppose $p$ divides $a$ and $b$. Furthermore, let $x$ be the largest integer such that $p^x$ divides $a$. Likewise, let $y$ be the largest integer such that $p^y$ divides $b$.

Since $ab^2, bc^2, kabc$ are all divisible by $b$, then so is $ca^2$. Thus $y \leq 2x$.

Since $ab^2, ca^2, kabc$ are all divisible by $a$, then so is $bc^2$, Thus $y \geq x$, which means $x \leq y \leq 2x$.

Now, since $ab^2, ca^2, kabc$ are all divisible by $p^{2x}$, then so is $bc^2$, which means $y \geq 2x$.

Therefore, $y = 2x$, which means that the degree of $p$ in the factorization of $abc$ is $x+y = 3x$.

For each prime $p$ that divides $abc$, it must occur as a cubic number in its prime factorization. Thus $abc$ is a cubic number.

A non-trivial example is $a=1,b=2,c=4$.

Triangle Inequality

In a triangle $ABC$, let $a = BC, b = AC, c = AB$. For any point $M$ and real numbers $x,y,z$, show that

$(x+y+z)(xMA^2 + yMB^2 + zMC^2) \geq xyc^2 + xzb^2 + yza^2$

Solution
We shall show that the inequality above is equivalent to
$$(x \vec{MA} + y \vec{MB} + z \vec{MC})^2 \geq 0$$

Indeed, since:
$$2\vec{MA} \vec{MB} = MA^2 + MB^2 - c^2$$
so
$$2xy\vec{MA} \vec{MB} = xyMA^2 + xyMB^2 - xyc^2$$
$$2yz\vec{MB} \vec{MC} = yzMB^2 + yzMC^2 - yza^2$$
$$2zx\vec{MC} \vec{MA} = zxMC^2 + zxMA^2 - zxb^2$$

Adding them, we obtain:
$$RHS = \sum x(y+z)MA^2 - 2\sum xy \vec{MA} \vec{MB}$$

So
$$LHS - RHS = \sum x^2MA^2 + \sum x(y+z)MA^2 - RHS = \sum x^2 MA^2 + 2\sum xy \vec{MA} \vec{MB}$$
$$= (x \vec{MA} + y \vec{MB} + z \vec{MC})^2 \geq 0 $$

Inequality

For positive real number $a,b,c$ prove that

$2\sqrt{ab+bc+ca} \leq \sqrt{3} \sqrt[3]{(a+b)(b+c)(c+a)}$

solution: http://dharmath.thehendrata.com/2009/12/02/solution-inequality/

Polynomial Algorithm

Credit for this problem goes to Zeke Chin

Does there exist an algorithm for the decision problem:

Given a polynomial over $n$ variables $x_1,\cdots,x_n$ with positive integer coefficients, and a positive integer $c$, is it true that $cx_1\cdots x_n \leq P(x_1,\cdots,x_n)$ for all assignments of positive integers to $x_1,\cdots,x_n$?

For example, for $P = x_1^2 + x_2^2$ and $c=2$, the algorithm should return "Yes" since $2x_1x_2 \leq x_1^2 + x_2^2$

3 Variable Inequality

For $a,b,c > 0$, prove that:

$! (ab(a+b) + bc(b+c) + ca(c+a))^2 \geq 4abc(a+b+c)(a^2+b^2+c^2)$

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

KBB2 Problem 9

Find the maximum $k$ such that

$\displaystyle (a^4 + b^4+c^4+d^4) + 4kabcd \geq \frac{k+1}{4}(a^2+b^2+c^2+d^2)^2$

always holds for $a,b,c,d$ positive reals.