Solutions and Comments

Solutions and Comments

43.: Two players play a game: the first player thinks of n integers x₁, x₂, ¼, x_n, each with one digit, and the second player selects some numbers a₁, a₂, ¼, a_n and asks what is the value of the sum a₁x₁ + a₂x₂ + ¼+ a_nx_n. What is the minimum number of questions used by the second player to find the integers x₁, x₂, ¼, x_n?

Solution. We are going to prove that the second player needs only one question to find the integers x₁, x₂, ¼, x_n. Indeed, let him choose a₁ = 100, a₂ = 100², ¼, a_n = 100ⁿ and ask for the value of the sum

S_n = 100x₁ + 100² x₂ + ¼+ 100ⁿx_n .

Note that

ê
ê
ê

100x₁ + 100² x₂ + ¼+ 100^n-1x_n-1

100ⁿ

ê
ê
ê

100 |x₁ |+ 100² |x₂ |+ ¼+ 100^n-1 |x_n-1 |

100ⁿ

9(100 + 100² + ¼+ 100^n-1)

100ⁿ

10^2n-1

10²ⁿ

Hence

ê
ê
ê

S_n

100ⁿ

- x_n

ê
ê
ê

100x₁ + 100² x₂ + ¼+ 100^n-1x_n-1

100ⁿ

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

S_n-1 = S_n - 100ⁿ x_n = 100x₁ + 100² x₂+ ¼+ 100^n-1x_n-1

and similarly obtain x_n-1. The procedure continues until all the numbers are found.

44.: Find the permutation { a₁, a₂, ¼, a_n } of the set { 1, 2, ¼, n } for which the sum

S = |a₂ - a₁ |+ |a₃ - a₂ |+ ¼+ |a_n - a_n-1 |

has maximum value.

Solution. Let a = (a₁, a₂, ¼, a_n) be a permutation of { 1, 2, ¼, n } and define

f(a) =

n-1
å
k = 1

|a_k+1 - a_k |+ |a_n - a₁ | .

With a_n+1 = a₁ and e₀ = e_n, we find that

f(a) =

n
å
k = 1

e_k (a_k+1 - a_k) =

n
å
k = 1

(e_k-1 - e_k)a_k

where e₁, e₂, ¼, 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}ⁿ b_k = 0 (there are the same number of positive and negative numbers among the b_k).

Therefore

f(a) = 2(x₁ + x₂ + ¼+ x_m) - 2(y₁ + y₂ + ¼+ y_m)

where x₁, ¼, x_m, y₁, ¼, y_m Î { 1, 2, ¼, n } and are distinct from each other. Hence f(a) is maximum when { x₁, x₂, ¼,x_m } = { n, n-1, ¼, n - m + 1 }, { y₁ , y₂, ¼, y_m } = {1 , 2, ¼, m } with m = ën/2 û, i.e., m is as large as possible. The maximum value is

ê
ê
ë

ú
ú
û

æ
ç
è

n -

ê
ê
ë

ú
ú
û

ö
÷
ø

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 for these permutations, the maximum value of the given expression is

ê
ê
ë

ú
ú
û

æ
ç
è

n -

ê
ê
ë

ú
ú
û

ö
÷
ø

- 1 .

This is equal to 2s² - 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ⁿ + a_n-1x^n-1 + ¼+ a₀ 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)ⁿ - aⁿ]+ a_n-1 [(a + kb)^n-1 - a_n-1] + ¼+ a₁ [(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₁ = 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 = tanna 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² ma

2a_m

1 - a_m²

whence

2a_m

1 - a_m²

= -2 Ûa_m =

1 ±Ö5

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^k-1(2m+1)a =

2tan2^k-1(2m+1)

1 - tan² 2^k-1(2m+1)

2a_n/2

1 - a²_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 sinpa = 0 and so a_p = tanpa = 0, which, as we have shown, is impossible. The desired result follows.

47.: Let a₁, a₂, ¼, a_n be positive real numbers such that a₁ a₂ ¼a_n = 1. Prove that

n
å
k = 1

s - a_k

£ 1

where s = 1 + a₁ + a₂ + ¼+ a_n.

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

(1) if the vectors (a₁, a₂, ¼, a_n) and (b₁, b₂, ¼, b_n) are similarly sorted (that is, both rising or both falling), then

a₁b₁ + ¼+ a_n b_n

a₁ + ¼+ a_n

b₁ + ¼+ b_n

;

(2) if the vectors (a₁, a₂, ¼, a_n) and (b₁, b₂, ¼, b_n) are oppositely sorted (that is, one rising and the other falling), then

a₁b₁ + ¼+ a_n b_n

a₁ + ¼+ a_n

b₁ + ¼+ b_n

If x₁, x₂, ¼, x_n are positive real numbers with x₁ £ x₁ £ ¼ £ x_n, then x₁ⁿ £ x₂ⁿ £ ¼ £ x_nⁿ. From Chebyshev's Inequality (1), we have, for each k = 1, 2, ¼, n, that

n
å
i = 1, i ¹ k

x_iⁿ =

n
å
i = 1, i ¹ k

x_i^n-1x_i ³

n-1

æ
ç
è

n
å
i = 1, i ¹ k

x_i

ö
÷
ø

æ
ç
è

n
å
i = 1, i ¹ k

x_i^n-1

ö
÷
ø

The Arithmetic-Geometric Means Inequality yields

n
å
i = 1, i ¹ k

x_i^n-1 ³ (n-1)x₁ ¼x_k-1x_k+1 ¼x_n ,

for k = 1, ¼, n. Therefore,

n
å
i = 1, i ¹ k

x_iⁿ ³ (x₁ ¼x_k-1x_k+1 ¼x_n)

n
å
i = 1, i ¹ k

x_i .

for each k®. This inequality can also be written

x₁ⁿ + ¼+ x_k-1ⁿ + x_k+1ⁿ + ¼x_nⁿ + x₁ x₂ ¼x_n

³ x₁ ¼x_k-1 x_k+1 ¼x_n(x₁ + x₂ + ¼+ x_n) ,

x₁ x₂ ¼x_n +x₁ⁿ + ¼+ x_k-1ⁿ + x_k+1ⁿ + ¼+ x_nⁿ

x₁ + x₂ + ¼+ x_n

x₁ ¼x_k-1 x_k+1 ¼x_n

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

n
å
k = 1

x₁x₂ ¼x_n + x₁ⁿ + ¼+ x_k-1ⁿ+ x_k+1ⁿ + ... x_nⁿ

x₁ x₂ ¼x_n

Now, let the x_kⁿ be equal to the a_k in increasing order to obtain the desired result.

48.: Let A₁A₂ ¼A_n be a regular n-gon 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₁B₁ |² + ¼+ |A_nB_n |²

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 a_k the the affix (complex number representative) of A_k (1 £ k £ n). Then the a_k are solutions of the equation zⁿ = 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_kB_k² = |a_k -

a_k

|² = (a_k -

a_k

)(

a_k

- a_k) = 2a_k

a_k

- a_k² -

a_k

= 2 - a_k -

a_k

Summing these inequalities yields that

n
å
k = 1

A_k B_k² = 2n -

n
å
k = 1

a_k² -

n
å
k = 1

a_k

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

0 =

n
å
k = 1

a_k² =

n
å
k = 1

a_k

Hence å_{k = 1}ⁿ A_k B_k² = 2n .