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₁,x₂,...,x_n are integers with no common divisor greater than 1, and let s_k= x₁^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₁,...,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ⁿ+a₁t^n-1+...+a_n-1t+a_n the polynomial which has the roots x₁,...,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₁,...,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₁,...,x_n are all divisible by p, which contradicts gcd(x₁,...,x_n)=1. Hence, \(\displaystyle p^\alpha\le n\).

A. 327. Let f(z)=a_nzⁿ+a_n-1z^n-1+...+a₁z+a₀ 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_ka_k+3<a_k+1a_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+1a_k+2>a_ka_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²+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+1b_k+2<b_kb_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+1b_k+2\(\displaystyle \le\)b_kb_k+3 for all integer k.

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

a_k+1a_k+2-a_ka_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-1b_k-b_k-2b_k+1)+p(b_k²-b_k-2b_k+2)+q(b_k-1b_k+2-b_k-2b_k+3)+

+p²(b_kb_k+1-b_k-1b_k+2)+q²(b_k+1b_k+2-b_kb_k+3)+pq(b_k+1²-b_k-1b_k+3).

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

To check the sign of p(b_k²-b_k-2b_k+2) consider

b_k-1(b_k²-b_k-2b_k+2)=b_k-2(b_kb_k+1-b_k-1b_k+2)+b_k(b_k-1b_k-b_k-2b_k+1)\(\displaystyle \ge\)0.

If b_k-1>0 we can divide by it to obtain b_k²-b_k-2b_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²-b_k-2b_k+2=b_k²\(\displaystyle \ge\)0. Therefore, p(b_k²-b_k-2b_k+2)\(\displaystyle \ge\)0 for all k. Similarly, pq(b_k+1²-b_k-1b_k+3)\(\displaystyle \ge\)0.

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

b_k+1(b_k-1b_k+2-b_k-2b_k+3)=b_k-1(b_k+1b_k+2-b_kb_k+3)+b_k+3(b_k-1b_k-b_k-2b_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-1b_k+2-b_k-2b_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).