Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# Solutions for advanced problems "A" in October, 2003

In this page only the sketch of the solutions are published; in some cases only the final results. To achieve the maximum score in the competition more detailed solutions needed.

A. 326. Assume that x1,x2,...,xn are integers with no common divisor greater than 1, and let sk= x1k+ ...+xnk for all positive integer k. Prove that $\displaystyle \mathop{\rm gcd}\,(s_1,s_2,\dots,s_n)$ divides $\displaystyle \mathop{\rm lcm}\,(1,2,\dots,n)$.

Solution. Let $\displaystyle p^\alpha$ be an arbitrary prime power divisor of lcm(s1,...,sn). The goal is to prove $\displaystyle p^\alpha\le n$.

First, we show that $\displaystyle p^\alpha|s_k$ holds also for k>n. Let f(t)=tn+a1tn-1+...+an-1t+an the polynomial which has the roots x1,...,xn. The coefficients in this polynomial are all integers, and for each k>n,

$\displaystyle s_k+a_1s_{k-1}+\dots+a_ns_{k-n}=\sum_{i=1}^nx_i^{k-n}f(x_i)=0.$

Hence, if sk-1,...,sk-n are divisible by $\displaystyle p^\alpha$, then sk is divisible, too. The first n values, s1,...,sn have this property; by induction, this implies the statement for all values of k.

Now set $\displaystyle k=\alpha\cdot\varphi(p^\alpha)\big)$. For an arbitrary integer x, we have $\displaystyle x^k\equiv0\pmod{p^\alpha}$ if p|x and $\displaystyle x^k\equiv1\pmod{p^\alpha}$ otherwise. If $\displaystyle p^\alph$n">, then $\displaystyle p^\alpha|s_k=x_1^k+\dots+x_n^k$ is possible only if x1,...,xn are all divisible by p, which contradicts gcd(x1,...,xn)=1. Hence, $\displaystyle p^\alpha\le n$.

A. 327. Let f(z)=anzn+an-1zn-1+...+a1z+a0 be a polynomial of degree n (n$\displaystyle \ge$3) with real coefficients. Prove that if all (real and complex) roots of f lie in the left half-plane $\displaystyle \{z\in\mathbb{C}\colon\mathop{\rm Re}z<0\}$ then akak+3<ak+1ak+2 holds for every k=0,1,...,n-3. (IMC 10, Cluj-Napoca, 2003)

Solution. The polynomial f is a product of linear and quadratic factors, $\displaystyle f(z)=\prod_i(k_iz+l_i)\cdot\prod_j(p_jz^2+q_jz+r_j)$, with $\displaystyle k_i,l_i,p_j,q_j,r_j\in\mathbb{R}$. Since all roots are in the left half-plane, for each i, ki and li are of the same sign, and for each j, pj,qj, rj are of the same sign, too. Hence, multiplying f by -1 if necessary, the roots of f don't change and f becomes the polynomial with all positive coefficients.

For the simplicity, we extend the sequence of coefficients by an+1=an+2=...=0 and a-1=a-2=...=0 and prove the same statement for -1$\displaystyle \le$k$\displaystyle \le$n-2 by induction.

For n$\displaystyle \le$2 the statement is obvious: ak+1 and ak+2 are positive and at least one of ak-1 and ak+3 is 0; hence, ak+1ak+2>akak+3=0.

Now assume that n$\displaystyle \ge$3 and the statement is true for all smaller values of n. Take a divisor of f(z) which has the form z2+pz+q where p and q are positive real numbers. (Such a divisor can be obtained from a conjugate pair of roots or two real roots.) Then we can write

$\displaystyle f(z)=(z^2+pz+q)(b_{n-2}z^{n-2}+\dots+b_1z+b_0)=(z^2+pz+q)g(x).\eqno(1)$

The roots polynomial g(z) are in the left half-plane, so we have bk+1bk+2<bkbk+3 for all -1$\displaystyle \le$k$\displaystyle \le$n-4. Defining bn-1=bn=...=0 and b-1=b-2=...=0 as well, we also have bk+1bk+2$\displaystyle \le$bkbk+3 for all integer k.

Now we prove ak+1ak+2>akak+3. If k=-1 or k=n-2 then this is obvious since ak+1ak+2 is positive and akak+3=0. Thus, assume 0$\displaystyle \le$k$\displaystyle \le$n-3. By an easy computation,

ak+1ak+2-akak+3=

=(qbk+1+pbk+bk-1)(qbk+2+pbk+1+bk)-(qbk+pbk-1+bk-2) (qbk+3+pbk+2+bk+1)=

=(bk-1bk-bk-2bk+1)+p(bk2-bk-2bk+2)+q(bk-1bk+2-bk-2bk+3)+

+p2(bkbk+1-bk-1bk+2)+q2(bk+1bk+2-bkbk+3)+pq(bk+12-bk-1bk+3).

We prove that all the six terms are non-negative and at least one is positive. Term p2(bkbk+1-bk-1bk+2) is positive since 0$\displaystyle \le$k$\displaystyle \le$n-3. Also terms bk-1bk-bk-2bk+1 and q2(bk+1bk+2-bkbk+3) are non-negative by the induction hypothesis.

To check the sign of p(bk2-bk-2bk+2) consider

bk-1(bk2-bk-2bk+2)=bk-2(bkbk+1-bk-1bk+2)+bk(bk-1bk-bk-2bk+1)$\displaystyle \ge$0.

If bk-1>0 we can divide by it to obtain bk2-bk-2bk+2$\displaystyle \ge$0. Otherwise, if bk-1=0, either bk-2=0 or bk+2=0 and thus bk2-bk-2bk+2=bk2$\displaystyle \ge$0. Therefore, p(bk2-bk-2bk+2)$\displaystyle \ge$0 for all k. Similarly, pq(bk+12-bk-1bk+3)$\displaystyle \ge$0.

The sign of q(bk-1bk+2-bk-2bk+3) can be checked in a similar way. Consider

bk+1(bk-1bk+2-bk-2bk+3)=bk-1(bk+1bk+2-bkbk+3)+bk+3(bk-1bk-bk-2bk+1)$\displaystyle \ge$0.

If bk+1>0, we can divide by it. Otherwise either bk-2=0 or bk+3=0. In all cases, we obtain bk-1bk+2-bk-2bk+3$\displaystyle \ge$0.

Now the signs of all terms are checked and the proof is complete.

A. 328. Find all functions $\displaystyle f\colon(0,\infty)\to(0,\infty)$ such that f(f(x)+y)=xf(1+xy) for all positive real numbers xy.

Solution. We will show that the only solution is the function f(x)=1/x.

Lemma 1. The function f is non-increasing.

Proof. Assume that 0<u<v and f(u)<f(v). Set $\displaystyle w={vf(v)-uf(u)\over v-u}$. Then w>f(v)>f(u), since $\displaystyle w-f(v)={u(f(v)-f(u))\over v-u}$. Substituting x=u, y=w-f(u) and x=v, y=w-f(v), we obtain

$\displaystyle f(w)=f(f(u)+(w-f(u)))=uf(1+u(w-f(u))) =uf\left(1+{uv(f(v)-f(u))\over v-u}\right);$

$\displaystyle f(w)=f(f(v)+(w-f(v)))=vf(1+v(w-f(v))) =vf\left(1+{uv(f(v)-f(u))\over v-u}\right).$

This is a contradiction, since u$\displaystyle \ne$v. Hence, u<v implies f(u)$\displaystyle \ge$f(v).

Lemma 2. f(1)=1.

Proof. Assume f(1)$\displaystyle \ne$1. Substituting (x=1) into the function equation, f(f(1)+y)=f(1+y), thus f(u+|f(1)-1|)=f(u) for all u>1. Then the function is periodic in the interval (1,$\displaystyle \infty$), the period is |f(1)-1|. The monotone and periodic properties together imply that f is constant in (1,$\displaystyle \infty$). But then, for all x,y>1, the left-hand size of the equation, f(f(x)+y) is a constant but the right-hand size, xf(1+xy) is not. Thus, f(1) cannot be any other value but 1.

Lemma 3. $\displaystyle f(x)={1\over x}$.

Proof. First assume x>1 and substitute $\displaystyle y=1-{1\over x}$:

$\displaystyle f\left(f(x)-{1\over x}+1\right)=xf(x).$

If $\displaystyle f(x${1\over x}"> then $\displaystyle f(x)-{1\over x}+$1"> and, by the monotonity, $\displaystyle f\left(f(x)-{1\over x}+1\right)\le1$; at the same time xf(x)>1 which is a contradiction. Reversing the direction of the inequalities, the case $\displaystyle f(x)<{1\over x}$ leads to contradiction in the same way. Hence, $\displaystyle f(x)={1\over x}$ if x>1.

Now let x>0 be arbitrary and y=1. Then

$\displaystyle f(f(x)+1)={1\over f(x)+1}=xf(1+x)={x\over1+x},$

$\displaystyle f(x)={1+x\over x}-1={1\over x}.$

Lemma 4. The function f(x)=1/x is really a solution.

Proof. f(f(x)+y)=f(1/x+y)=f((1+xy)/x)=x/(1+xy)=xf(1+xy).