location:

43.
Two players play a game: the first player thinks of n integers x1, x2, ¼, xn, each with one digit, and the second player selects some numbers a1, a2, ¼, an and asks what is the value of the sum a1x1 + a2x2 + ¼+ anxn. What is the minimum number of questions used by the second player to find the integers x1, x2, ¼, xn?
Solution. We are going to prove that the second player needs only one question to find the integers x1, x2, ¼, xn. Indeed, let him choose a1 = 100, a2 = 1002, ¼, an = 100n and ask for the value of the sum
 Sn = 100x1 + 1002 x2 + ¼+ 100nxn  .
Note that
 êê ê
 100x1 + 1002 x2 + ¼+ 100n-1xn-1100n êê ê
 £ 100 |x1 |+ 1002 |x2 |+ ¼+ 100n-1 |xn-1 |100n
 £ 9(100 + 1002 + ¼+ 100n-1)100n
 < 102n-1102n = 110 .
Hence
 êê ê Sn100n - xn êê ê = 100x1 + 1002 x2 + ¼+ 100n-1xn-1100n < 110 ,
and xn can be obtained. Now, we can find the sum
 Sn-1 = Sn - 100n xn = 100x1 + 1002 x2+ ¼+ 100n-1xn-1
and similarly obtain xn-1. The procedure continues until all the numbers are found.

44.
Find the permutation { a1, a2, ¼, an } of the set { 1, 2, ¼, n } for which the sum
 S = |a2 - a1 |+ |a3 - a2 |+ ¼+ |an - an-1 |
has maximum value.

Solution. Let a = (a1, a2, ¼, an) be a permutation of { 1, 2, ¼, n } and define

 f(a) = n-1 å k = 1 |ak+1 - ak |+ |an - a1 | .
With an+1 = a1 and e0 = en, we find that
 f(a) = n å k = 1 ek (ak+1 - ak) = n å k = 1 (ek-1 - ek)ak
where e1, e2, ¼, en are all equal to 1 or -1. Thus
 f(a) = n å k = 1 bk k .
where each bk is one of -2, 0, 2, and åk = 1n bk = 0 (there are the same number of positive and negative numbers among the bk).

Therefore

 f(a) = 2(x1 + x2 + ¼+ xm) - 2(y1 + y2 + ¼+ ym)
where x1, ¼, xm, y1, ¼, ym Î { 1, 2, ¼, n } and are distinct from each other. Hence f(a) is maximum when { x1, x2, ¼,xm } = { n, n-1, ¼, n - m + 1 }, { y1 , y2, ¼, ym } = {1 , 2, ¼, m } with m = ën/2 û, i.e., m is as large as possible. The maximum value is
 2 êê ë n2 úú û æç è n - êê ë n2 úú û ö÷ ø .
This value is attained by taking
 a = (s+1, 1, s+2, 2, ¼, 2s , s)       when  n = 2s
and
 a = (s+2, 1, s+3, 2, ¼, 2s + 1, s, s+1)       when n = 2s + 1 .
Since |an - a1 | = 1 for these permutations, the maximum value of the given expression is
 2 êê ë n2 úú û æç è n - êê ë n2 úú û ö÷ ø - 1 .
This is equal to 2s2 - 1 when n = 2s, and to 2s(s+1) - 1 when n = 2s + 1.

45.
Prove that there is no nonconstant polynomial p(x) = an xn + an-1xn-1 + ¼+ a0 with integer coefficients ai for which p(m) is a prime number for every integer m.
Solution. Let a be an integer, for which p(a) ¹ -1, 0, 1. (If there is no such a, then p cannot take all prime values.) Suppose that b is a prime divisor of p(a). Now, for any integer k,
 p(a + kb) - p(a) = an [(a + kb)n - an]+ an-1 [(a + kb)n-1 - an-1] + ¼+ a1 [(a + kb) - a] .
It can be seen that b is a divisor of p(a + kb) - p(a) and hence of p(a + kb) for every integer k. Both of the equations p(x) = b and p(x) = -b have at most finitely many roots. So some of the values of p(a + kb) must be composite, and the result follows.

Comment. It should have been stated in the problem that the polynomial was nonconstant, or had positive degree.

46.
Let a1 = 2, an+1 = [(an + 2)/(1 - 2an)] for n = 1, 2, ¼. Prove that
(a) an ¹ 0 for each positive integer n;
(b) there is no integer p ³ 1 for which an+p = an for every integer n ³ 1 (i.e., the sequence is not periodic).
Solution. (a) We prove that an = tanna where a = arctan2 by mathematical induction. This is true for n = 1. Assume that it holds for n = k. Then
 ak+1 = 2 + an1 - 2an = tana+ tanna1 - tanatanna = tan(n+1)a ,
as desired.

Suppose that an = 0 with n = 2m + 1. Then a2m = -2. However,

 a2m = tan2ma = 2tanma1 - tan2 ma = 2am1 - am2 ,
whence
 2am1 - am2 = -2 Ûam = 1 ±Ö52 ,
which is not possible, since am has to be rational.

Suppose that an = 0 with n = 2k(2m+1) for some positive integer k. Then

 0 = an = tan2·2k-1(2m+1)a = 2tan2k-1(2m+1)1 - tan2 2k-1(2m+1) = 2an/21 - a2n/2 ,
so that an/2 = 0. Continuing step by step backward, we finally come to a2m + 1 = 0, which has already been shown as impossible.

(b) Assume, if possible, that the sequence is periodic, i.e., there is a positive integer p such that an+p = an for every positive integer n. Thus

 tan(n+p)a- tanna = sinpacos(n+p)acosna = 0 .
Therefore sinpa = 0 and so ap = tanpa = 0, which, as we have shown, is impossible. The desired result follows.

47.
Let a1, a2, ¼, an be positive real numbers such that a1 a2 ¼an = 1. Prove that
 n å k = 1 1s - ak £ 1
where s = 1 + a1 + a2 + ¼+ an.

Solution. First, we recall that Chebyshev's Inequalities:

(1) if the vectors (a1, a2, ¼, an) and (b1, b2, ¼, bn) are similarly sorted (that is, both rising or both falling), then

 a1b1 + ¼+ an bnn ³ a1 + ¼+ ann · b1 + ¼+ bnn ;
(2) if the vectors (a1, a2, ¼, an) and (b1, b2, ¼, bn) are oppositely sorted (that is, one rising and the other falling), then
 a1b1 + ¼+ an bnn £ a1 + ¼+ ann · b1 + ¼+ bnn .

If x1, x2, ¼, xn are positive real numbers with x1 £ x1 £ ¼ £ xn, then x1n £ x2n £ ¼ £ xnn. From Chebyshev's Inequality (1), we have, for each k = 1, 2, ¼, n, that

 n å i = 1, i ¹ k xin = n å i = 1, i ¹ k xin-1xi ³ 1n-1 æç è n å i = 1, i ¹ k xi ö÷ ø æç è n å i = 1, i ¹ k xin-1 ö÷ ø .
The Arithmetic-Geometric Means Inequality yields
 n å i = 1, i ¹ k xin-1 ³ (n-1)x1 ¼xk-1xk+1 ¼xn ,
for k = 1, ¼, n. Therefore,
 n å i = 1, i ¹ k xin ³ (x1 ¼xk-1xk+1 ¼xn) n å i = 1, i ¹ k xi .
for each k®. This inequality can also be written
 x1n + ¼+ xk-1n + xk+1n + ¼xnn + x1 x2 ¼xn
 ³ x1 ¼xk-1 xk+1 ¼xn(x1 + x2 + ¼+ xn) ,
or
 1x1 x2 ¼xn +x1n + ¼+ xk-1n + xk+1n + ¼+ xnn £ 1x1 + x2 + ¼+ xn · 1x1 ¼xk-1 xk+1 ¼xn .
Adding up these inequalities, for 1 £ k £ n, we get
 n å k = 1 1x1x2 ¼xn + x1n + ¼+ xk-1n+ xk+1n + ... xnn £ 1x1 x2 ¼xn .
Now, let the xkn be equal to the ak in increasing order to obtain the desired result.

48.
Let A1A2 ¼An be a regular n-gon and d an arbitrary line. The parallels through Ai to d intersect its circumcircle respectively at Bi (i = 1, 2, ¼, n. Prove that the sum
 S = |A1B1 |2 + ¼+ |AnBn |2
is independent of d.

Solution. Select a system of coordinates so that O is the centre of the circumcircle and the x-axis (or real axis) is orthogonal to d. Without loss of generality, we may assume that the radius of the circumcircle is of length 1. Let ak the the affix (complex number representative) of Ak (1 £ k £ n). Then the ak are solutions of the equation zn = l, where l is a complex number with |l| = 1. Since Ak and Bk are symmetrical with respect to the real axis, the affix of Bk is [`(ak)], the complex conjugate of ak, for 1 £ k £ n, Thus

 AkBk2 = |ak - ak |2 = (ak - ak )( ak - ak) = 2ak ak - ak2 - ak 2 = 2 - ak - ak 2 .
Summing these inequalities yields that
 n å k = 1 Ak Bk2 = 2n - n å k = 1 ak2 - n å k = 1 ak 2 .
Since { ak : 1 £ k £ n } is a complete set of solutions of the equation zn = l, their sum and the sum of their pairwise products vanishes. Hence
 0 = n å k = 1 ak2 = n å k = 1 ak 2 .
Hence åk = 1n Ak Bk2 = 2n .

 top of page | contact us | privacy | site map |