CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location: 
       

Solutions and Comments



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 a1 x1 + a2 x2 ++ an xn . 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 =100 x1 + 1002 x2 ++ 100n xn .

Note that

| 100 x1 + 1002 x2 ++ 100n-1 xn-1 100n | 100 x1 + 1002 x2 ++ 100n-1 xn-1 100n 9(100+ 1002 ++ 100n-1 ) 100n < 102n-1 102n = 1 10 .

Hence

| Sn 100n - xn |= 100 x1 + 1002 x2 ++ 100n-1 xn-1 100n < 1 10 ,

and xn can be obtained. Now, we can find the sum

Sn-1 = Sn - 100n xn =100 x1 + 1002 x2 ++ 100n-1 xn-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)= k=1 n-1 ak+1 - ak + an - a1 .

With an+1 = a1 and ε0 = εn , we find that

f(a)= k=1 n εk ( ak+1 - ak )= k=1 n( εk-1 - εk ) ak

where ε1 , ε2 , , εn are all equal to 1 or -1. Thus

f(a)= k=1 n βk k.

where each βk is one of -2, 0, 2, and k=1 n βk =0 (there are the same number of positive and negative numbers among the βk ).
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 n 2 (n- n 2 ).

This value is attained by taking

a=(s+1,1,s+2,2,,2s,s)whenn=2s

and

a=(s+2,1,s+3,2,,2s+1,s,s+1)whenn=2s+1.

Since an - a1 =1 for these permutations, the maximum value of the given expression is

2 n 2 (n- n 2 )-1.

This is equal to 2 s2 -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-1 xn-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-2 an for n=1,2,. Prove that
(a) an 0 for each positive integer n;
(b) there is no integer p1 for which an+p = an for every integer n1 (i.e., the sequence is not periodic).
Solution. (a) We prove that an =tannα where α=arctan2 by mathematical induction. This is true for n=1. Assume that it holds for n=k. Then

ak+1 = 2+ an 1-2 an = tanα+tannα 1-tanαtannα =tan(n+1)α,

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

a2m =tan2mα= 2tanmα 1-tan2 mα = 2 am 1- am 2 ,

whence

2 am 1- am 2 =-2&lrArr; am = 1±5 2 ,

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)α= 2tan 2k-1 (2m+1) 1-tan2 2k-1 (2m+1) = 2 an/2 1- an/2 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)α-tannα= sinpα cos(n+p)αcosnα =0.

Therefore sinpα=0 and so ap =tanpα=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

k=1 n 1 s- 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

a1 b1 ++ an bn n a1 ++ an n · b1 ++ bn n ;

(2) if the vectors ( a1 , a2 ,, an ) and ( b1 , b2 ,, bn ) are oppositely sorted (that is, one rising and the other falling), then

a1 b1 ++ an bn n a1 ++ an n · b1 ++ bn n .

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

i=1,ik n xi n = i=1,ik n xi n-1 xi 1 n-1 ( i=1,ik n xi ) ( i=1,ik n xi n-1 ).

The Arithmetic-Geometric Means Inequality yields

i=1,ik n xi n-1 (n-1) x1 xk-1 xk+1 xn ,

for k=1,,n. Therefore,

i=1,ik n xi n ( x1 xk-1 xk+1 xn ) i=1,ik n xi .

for each k«.This inequality can also be written

x1 n ++ xk-1 n + xk+1 n + xn n + x1 x2 xn


x1 xk-1 xk+1 xn ( x1 + x2 ++ xn ),

or

1 x1 x2 xn + x1 n ++ xk-1 n + xk+1 n ++ xn n 1 x1 + x2 ++ xn · 1 x1 xk-1 xk+1 xn .

Adding up these inequalities, for 1kn, we get

k=1 n 1 x1 x2 xn + x1 n ++ xk-1 n + xk+1 n + xn n 1 x1 x2 xn .

Now, let the xk n be equal to the ak in increasing order to obtain the desired result.


48.
Let A1 A2 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= A1 B1 2 ++ An Bn 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 ( 1kn). Then the ak are solutions of the equation zn =λ, where λ is a complex number with λ=1. Since Ak and Bk are symmetrical with respect to the real axis, the affix of Bk is ak &OverLine; , the complex conjugate of ak , for 1kn, Thus

Ak Bk 2 = ak - ak &OverLine; 2 =( ak - ak &OverLine; )( ak &OverLine; - ak )=2 ak ak &OverLine; - ak 2 - ak &OverLine; 2 =2- ak - ak &OverLine; 2 .

Summing these inequalities yields that

k=1 n Ak Bk 2 =2n- k=1 n ak 2 - k=1 n ak &OverLine; 2 .

Since { ak :1kn} is a complete set of solutions of the equation zn =λ, their sum and the sum of their pairwise products vanishes. Hence

0= k=1 n ak 2 = k=1 n ak &OverLine; 2 .

Hence k=1 n Ak Bk 2 =2n.


© Canadian Mathematical Society, 2014 : http://www.cms.math.ca/