Solutions and Comments
 43.

Two players play a game: the first player thinks
of n integers x_{1}, x_{2}, ¼, x_{n}, each with one
digit, and the second player selects some numbers
a_{1}, a_{2}, ¼, a_{n} and asks what is the value
of the sum a_{1}x_{1} + a_{2}x_{2} + ¼+ a_{n}x_{n}. What is the
minimum number of questions used by the second player to find
the integers x_{1}, x_{2}, ¼, x_{n}?
Solution. We are going to prove that the second player needs
only one question to find the integers x
_{1}, x
_{2},
¼, x
_{n}.
Indeed, let him choose a
_{1} = 100, a
_{2} = 100
^{2},
¼,
a
_{n} = 100
^{n} and ask for the value of the sum
S_{n} = 100x_{1} + 100^{2} x_{2} + ¼+ 100^{n}x_{n} . 

Note that



100x_{1} + 100^{2} x_{2} + ¼+ 100^{n1}x_{n1} 100^{n}


ê ê
ê


 
£ 
100 x_{1} + 100^{2} x_{2} + ¼+ 100^{n1} x_{n1}  100^{n}


 
£ 
9(100 + 100^{2} + ¼+ 100^{n1}) 100^{n}


 
< 
10^{2n1} 10^{2n}

= 
1 10

. 

 

Hence

ê ê
ê


S_{n} 100^{n}

 x_{n} 
ê ê
ê

= 
100x_{1} + 100^{2} x_{2} + ¼+ 100^{n1}x_{n1} 100^{n}

< 
1 10

, 

and x
_{n} can be obtained.
Now, we can find the sum
S_{n1} = S_{n}  100^{n} x_{n} = 100x_{1} + 100^{2} x_{2}+ ¼+ 100^{n1}x_{n1} 

and similarly obtain x
_{n1}. The procedure continues until
all the numbers are found.
 44.

Find the permutation { a_{1}, a_{2}, ¼, a_{n} }
of the set { 1, 2, ¼, n } for which the sum
S = a_{2}  a_{1} + a_{3}  a_{2} + ¼+ a_{n}  a_{n1}  

has maximum value.
Solution. Let a = (a_{1}, a_{2}, ¼, a_{n})
be a permutation of { 1, 2, ¼, n } and define
f(a) = 
n1 å
k = 1

a_{k+1}  a_{k} + a_{n}  a_{1}  . 

With a
_{n+1} = a
_{1} and
e_{0} =
e_{n}, we find that
f(a) = 
n å
k = 1

e_{k} (a_{k+1}  a_{k}) = 
n å
k = 1

(e_{k1}  e_{k})a_{k} 

where
e_{1},
e_{2},
¼,
e_{n}
are all equal to 1 or 1. Thus
f(a) = 
n å
k = 1

b_{k} k . 

where each
b_{k} is one of 2, 0, 2, and
å_{k = 1}^{n} b_{k} = 0 (there are the same
number of positive and negative numbers among the
b_{k}).
Therefore
f(a) = 2(x_{1} + x_{2} + ¼+ x_{m})  2(y_{1} + y_{2} + ¼+ y_{m}) 

where x
_{1},
¼, x
_{m}, y
_{1},
¼, y
_{m} Î { 1, 2,
¼, n } and are distinct from each other.
Hence f(a) is maximum when { x
_{1}, x
_{2},
¼,x
_{m} } = { n, n1,
¼, n  m + 1 },
{ y
_{1} , y
_{2},
¼, y
_{m} } = {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) when n = 2s 

and
a = (s+2, 1, s+3, 2, ¼, 2s + 1, s, s+1) when n = 2s + 1 . 

Since
a
_{n}  a
_{1}  = 1 for these permutations, the
maximum value of the given expression is
2 
ê ê
ë


n 2


ú ú
û


æ ç
è

n  
ê ê
ë


n 2


ú ú
û


ö ÷
ø

 1 . 

This is equal to 2s
^{2}  1 when n = 2s, and to
2s(s+1)  1 when n = 2s + 1.
 45.

Prove that there is no nonconstant polynomial
p(x) = a_{n} x^{n} + a_{n1}x^{n1} + ¼+ a_{0}
with integer coefficients a_{i} 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) = a_{n} [(a + kb)^{n}  a^{n}]+ a_{n1} [(a + kb)^{n1}  a_{n1}] + ¼+ a_{1} [(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 a_{1} = 2, a_{n+1} = [(a_{n} + 2)/(1  2a_{n})] for n = 1, 2, ¼.
Prove that


(a) a_{n} ¹ 0 for each positive integer n;


(b) there is no integer p ³ 1 for which a_{n+p} = a_{n} for every integer n ³ 1 (i.e., the sequence is
not periodic).
Solution. (a) We prove that a
_{n} = tann
a where
a = arctan2 by mathematical induction. This is true for
n = 1. Assume that it holds for n = k. Then
a_{k+1} = 
2 + a_{n} 1  2a_{n}

= 
tana+ tanna 1  tanatanna

= tan(n+1)a , 

as desired.
Suppose that a_{n} = 0 with n = 2m + 1. Then a_{2m} = 2.
However,
a_{2m} = tan2ma = 
2tanma 1  tan^{2} ma

= 
2a_{m} 1  a_{m}^{2}

, 

whence

2a_{m} 1  a_{m}^{2}

= 2 Ûa_{m} = 
1 ±Ö5 2

, 

which is not possible, since a
_{m} has to be rational.
Suppose that a_{n} = 0 with n = 2^{k}(2m+1) for some positive
integer k. Then
0 = a_{n} = tan2·2^{k1}(2m+1)a = 
2tan2^{k1}(2m+1) 1  tan^{2} 2^{k1}(2m+1)

= 
2a_{n/2} 1  a^{2}_{n/2}

, 

so that a
_{n/2} = 0. Continuing step by step backward,
we finally come to a
_{2m + 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 a_{n+p} = a_{n} for every
positive integer n. Thus
tan(n+p)a tanna = 
sinpa cos(n+p)acosna

= 0 . 

Therefore sinp
a = 0 and so a
_{p} = tanp
a = 0,
which, as we have shown, is impossible. The desired result follows.
 47.

Let a_{1}, a_{2}, ¼, a_{n} be positive real
numbers such that a_{1} a_{2} ¼a_{n} = 1. Prove that
where s = 1 + a
_{1} + a
_{2} +
¼+ a
_{n}.
Solution. First, we recall that Chebyshev's Inequalities:
(1) if the vectors (a_{1}, a_{2}, ¼, a_{n}) and
(b_{1}, b_{2}, ¼, b_{n}) are similarly sorted
(that is, both rising or both falling), then

a_{1}b_{1} + ¼+ a_{n} b_{n} n

³ 
a_{1} + ¼+ a_{n} n

· 
b_{1} + ¼+ b_{n} n

; 

(2) if the vectors (a
_{1}, a
_{2},
¼, a
_{n}) and
(b
_{1}, b
_{2},
¼, b
_{n}) are oppositely sorted
(that is, one rising and the other falling), then

a_{1}b_{1} + ¼+ a_{n} b_{n} n

£ 
a_{1} + ¼+ a_{n} n

· 
b_{1} + ¼+ b_{n} n

. 

If x_{1}, x_{2}, ¼, x_{n} are positive real numbers with
x_{1} £ x_{1} £ ¼ £ x_{n}, then
x_{1}^{n} £ x_{2}^{n} £ ¼ £ x_{n}^{n}. From
Chebyshev's Inequality (1), we have, for each
k = 1, 2, ¼, n, that

n å
i = 1, i ¹ k

x_{i}^{n} = 
n å
i = 1, i ¹ k

x_{i}^{n1}x_{i} ³ 
1 n1


æ ç
è


n å
i = 1, i ¹ k

x_{i} 
ö ÷
ø


æ ç
è


n å
i = 1, i ¹ k

x_{i}^{n1} 
ö ÷
ø

. 

The ArithmeticGeometric Means Inequality yields

n å
i = 1, i ¹ k

x_{i}^{n1} ³ (n1)x_{1} ¼x_{k1}x_{k+1} ¼x_{n} , 

for k = 1,
¼, n. Therefore,

n å
i = 1, i ¹ k

x_{i}^{n} ³ (x_{1} ¼x_{k1}x_{k+1} ¼x_{n}) 
n å
i = 1, i ¹ k

x_{i} . 

for each k®. This inequality can also be written
x_{1}^{n} + ¼+ x_{k1}^{n} + x_{k+1}^{n} + ¼x_{n}^{n} + x_{1} x_{2} ¼x_{n} 

³ x_{1} ¼x_{k1} x_{k+1} ¼x_{n}(x_{1} + x_{2} + ¼+ x_{n}) , 

or

1 x_{1} x_{2} ¼x_{n} +x_{1}^{n} + ¼+ x_{k1}^{n} + x_{k+1}^{n} + ¼+ x_{n}^{n}

£ 
1 x_{1} + x_{2} + ¼+ x_{n}

· 
1 x_{1} ¼x_{k1} x_{k+1} ¼x_{n}

. 

Adding up these inequalities, for 1
£ k
£ n, we get

n å
k = 1


1 x_{1}x_{2} ¼x_{n} + x_{1}^{n} + ¼+ x_{k1}^{n}+ x_{k+1}^{n} + ... x_{n}^{n}

£ 
1 x_{1} x_{2} ¼x_{n}

. 

Now, let the x
_{k}^{n} be equal to the a
_{k} in increasing
order to obtain the desired result.
 48.

Let A_{1}A_{2} ¼A_{n} be a regular ngon and
d an arbitrary line. The parallels through A_{i} to
d intersect its circumcircle respectively at
B_{i} (i = 1, 2, ¼, n. Prove that the sum
S = A_{1}B_{1} ^{2} + ¼+ A_{n}B_{n} ^{2} 

is independent of d.
Solution. Select a system of coordinates so that O is
the centre of the circumcircle and the xaxis (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 a_{k} the the affix (complex
number representative) of A_{k} (1 £ k £ n). Then the
a_{k} are solutions of the equation z^{n} = l, where
l is a complex number with l = 1.
Since A_{k} and B_{k} are symmetrical with respect to the
real axis, the affix of B_{k} is [`(a_{k})], the
complex conjugate of a_{k}, for 1 £ k £ n,
Thus
A_{k}B_{k}^{2} = a_{k}  
a_{k}

^{2} = (a_{k}  
a_{k}

)( 
a_{k}

 a_{k}) = 2a_{k} 
a_{k}

 a_{k}^{2}  
a_{k}

2

= 2  a_{k}  
a_{k}

2

. 

Summing these inequalities yields that

n å
k = 1

A_{k} B_{k}^{2} = 2n  
n å
k = 1

a_{k}^{2}  
n å
k = 1


a_{k}

2

. 

Since { a
_{k} : 1
£ k
£ n } is a complete set of
solutions of the equation z
^{n} =
l, their sum
and the sum of their pairwise products vanishes. Hence
0 = 
n å
k = 1

a_{k}^{2} = 
n å
k = 1


a_{k}

2

. 

Hence
å_{k = 1}^{n} A
_{k} B
_{k}^{2} = 2n .