## 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 *x*_{1},*x*_{2},...,*x*_{n} are integers with no common divisor greater than 1, and let *s*_{k}= *x*_{1}^{k}+ ...+*x*_{n}^{k} 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*(*s*_{1},...,*s*_{n}). 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*)=*t*^{n}+*a*_{1}*t*^{n-1}+...+*a*_{n-1}*t*+*a*_{n} the polynomial which has the roots *x*_{1},...,*x*_{n}. 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 *s*_{k-1},...,*s*_{k-n} are divisible by \(\displaystyle p^\alpha\), then *s*_{k} is divisible, too. The first *n* values, *s*_{1},...,*s*_{n} 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 *x*_{1},...,*x*_{n} are all divisible by *p*, which contradicts *gcd*(*x*_{1},...,*x*_{n})=1. Hence, \(\displaystyle p^\alpha\le n\).

**A. 327.** Let *f*(*z*)=*a*_{n}*z*^{n}+*a*_{n-1}*z*^{n-1}+...+*a*_{1}*z*+*a*_{0} 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 *a*_{k}*a*_{k+3}<*a*_{k+1}*a*_{k+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*, *k*_{i} and *l*_{i} are of the same sign, and for each *j*, *p*_{j},*q*_{j}, *r*_{j} 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 *a*_{n+1}=*a*_{n+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: *a*_{k+1} and *a*_{k+2} are positive and at least one of *a*_{k-1} and *a*_{k+3} is 0; hence, *a*_{k+1}*a*_{k+2}>*a*_{k}*a*_{k+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 *z*^{2}+*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 *b*_{k+1}*b*_{k+2}<*b*_{k}*b*_{k+3} for all -1\(\displaystyle \le\)*k*\(\displaystyle \le\)*n*-4. Defining *b*_{n-1}=*b*_{n}=...=0 and *b*_{-1}=*b*_{-2}=...=0 as well, we also have *b*_{k+1}*b*_{k+2}\(\displaystyle \le\)*b*_{k}*b*_{k+3} for all integer *k*.

Now we prove *a*_{k+1}*a*_{k+2}>*a*_{k}*a*_{k+3}. If *k*=-1 or *k*=*n*-2 then this is obvious since *a*_{k+1}*a*_{k+2} is positive and *a*_{k}*a*_{k+3}=0. Thus, assume 0\(\displaystyle \le\)*k*\(\displaystyle \le\)*n*-3. By an easy computation,

*a*_{k+1}*a*_{k+2}-*a*_{k}*a*_{k+3}=

=(*qb*_{k+1}+*pb*_{k}+*b*_{k-1})(*qb*_{k+2}+*pb*_{k+1}+*b*_{k})-(*qb*_{k}+*pb*_{k-1}+*b*_{k-2}) (*qb*_{k+3}+*pb*_{k+2}+*b*_{k+1})=

=(*b*_{k-1}*b*_{k}-*b*_{k-2}*b*_{k+1})+*p*(*b*_{k}^{2}-*b*_{k-2}*b*_{k+2})+*q*(*b*_{k-1}*b*_{k+2}-*b*_{k-2}*b*_{k+3})+

+*p*^{2}(*b*_{k}*b*_{k+1}-*b*_{k-1}*b*_{k+2})+*q*^{2}(*b*_{k+1}*b*_{k+2}-*b*_{k}*b*_{k+3})+*pq*(*b*_{k+1}^{2}-*b*_{k-1}*b*_{k+3}).

We prove that all the six terms are non-negative and at least one is positive. Term *p*^{2}(*b*_{k}*b*_{k+1}-*b*_{k-1}*b*_{k+2}) is positive since 0\(\displaystyle \le\)*k*\(\displaystyle \le\)*n*-3. Also terms *b*_{k-1}*b*_{k}-*b*_{k-2}*b*_{k+1} and *q*^{2}(*b*_{k+1}*b*_{k+2}-*b*_{k}*b*_{k+3}) are non-negative by the induction hypothesis.

To check the sign of *p*(*b*_{k}^{2}-*b*_{k-2}*b*_{k+2}) consider

*b*_{k-1}(*b*_{k}^{2}-*b*_{k-2}*b*_{k+2})=*b*_{k-2}(*b*_{k}*b*_{k+1}-*b*_{k-1}*b*_{k+2})+*b*_{k}(*b*_{k-1}*b*_{k}-*b*_{k-2}*b*_{k+1})\(\displaystyle \ge\)0.

If *b*_{k-1}>0 we can divide by it to obtain *b*_{k}^{2}-*b*_{k-2}*b*_{k+2}\(\displaystyle \ge\)0. Otherwise, if *b*_{k-1}=0, either *b*_{k-2}=0 or *b*_{k+2}=0 and thus *b*_{k}^{2}-*b*_{k-2}*b*_{k+2}=*b*_{k}^{2}\(\displaystyle \ge\)0. Therefore, *p*(*b*_{k}^{2}-*b*_{k-2}*b*_{k+2})\(\displaystyle \ge\)0 for all *k*. Similarly, *pq*(*b*_{k+1}^{2}-*b*_{k-1}*b*_{k+3})\(\displaystyle \ge\)0.

The sign of *q*(*b*_{k-1}*b*_{k+2}-*b*_{k-2}*b*_{k+3}) can be checked in a similar way. Consider

*b*_{k+1}(*b*_{k-1}*b*_{k+2}-*b*_{k-2}*b*_{k+3})=*b*_{k-1}(*b*_{k+1}*b*_{k+2}-*b*_{k}*b*_{k+3})+*b*_{k+3}(*b*_{k-1}*b*_{k}-*b*_{k-2}*b*_{k+1})\(\displaystyle \ge\)0.

If *b*_{k+1}>0, we can divide by it. Otherwise either *b*_{k-2}=0 or *b*_{k+3}=0. In all cases, we obtain *b*_{k-1}*b*_{k+2}-*b*_{k-2}*b*_{k+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 *x*, *y*.

**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*).