Problem Set 6
 31.

Find all continuous functions f: R ®R such that
for every
x,
y Î R.
View solution
 32.

Let n ³ 3 be a natural number. Prove that
View solution
 33.

Let n ³ 3 be a positive integer. Are there n positive
integers a_{1}, a_{2}, ¼, a_{n} not all the same
such that for each i with
3 £ i £ n we have
a_{i} + S_{i} = (a_{i}, S_{i}) + [a_{i}, S_{i}] . 

where
S_{i} =
a_{1} +
a_{2} +
¼+
a_{n}, and where (·, ·) and
[ ·, ·] represent the greatest common divisor and
least common multiple respectively?
View solution
 34.

Find all integers p for which there are rational numbers
a and b such that the polynomial x^{5}  px  1 has at least
one root in common with the polynomial x^{2}  ax  b.
View solution
 35.

Let P be an arbitrary interior point of an equilateral
triangle ABC. Prove that
ÐPAB  ÐPAC  ³ ÐPBC ÐPCB  . 

(
Note: This is Problem 2255 in
CM+MM, September, 1997.)
View solution
 36.

Let n be a positive integer and x > 0. Prove that
(1 + x)^{n+1} ³ 
(n+1)^{n+1} n^{n}

x . 

(
Note: This is Problem 2260 in
CM+MM,
September, 1997.)
View solution
Solutions to Problem Set 6
31.
 31.

First solution. Setting (x, y) = (t, 0) yields
f(t + f(0)) = f(t) for all real t. Setting (x, y) = (0, t)
yields f(f(t)) = f(0) + t for all real t. Hence
f(f(f(t))) = f(t) for all real t, i.e., f(f(z)) = z for
each z in the image of f. Let (x, y) = (f(t), f(0)). Then
f(f(t) + f(f(0))) = f(f(t))  f(0) = f(0) + t  f(0) = t 

so that the image of
f contains every real and so
f(
f(
t))
º t for all real
t.


Taking (x, y) = (u, f(v)) yields
since
v =
f(
f(
v)) for all real
u and
v. In particular,
f(0) = 2
f(0), so
f(0) = 0 and 0 =
f(
t +
t) =
f(
t) +
f(
t).
By induction, it can be shown that for each integer
n and each
real
t,
f(
nt) =
nf(
t). In particular, for each rational
r/
s,
f(
r/
s) =
rf(1/
s) = (
r/
s)
f(1). Since
f is continuous,
f(
t) =
f(
t·1) =
tf(1) for all real
t. Let
c =
f(1).
Then 1 =
f(
f(1)) =
f(
c) =
cf(1) =
c^{2} so that
c =
±1. Hence
f(
t)
º t or
f(
t)
º 
t. Checking reveals that both
these solutions work. (For
f(
t)
º 
t,
f(
x +
f(
y)) = 
x 
f(
y) =
f(
x) +
y, as required.)
 31.

Second solution. Taking (x, y) = (0, 0), we find
that
f(0) = 0 + f(0) Þ f(f(0)) = f(0 + f(0)) = f(0) + f(f(0))Þ f(0) = 0 . 

Taking (
x,
y) = (0,
t) yields
f(
f(
t)) =
t for all real
t.
Hence
f(
x +
y) =
f(
x +
f(
f(
y)) =
f(
x) +
f(
y) for all
x,
y, and
we can complete the solution as in the
First Solution.
 31.

Third solution. Taking (x, y) = (0, 0) yields
f(f(0)) = f(0), whence f(f(f(0))) = f(f(0)) = f(0). Taking
(x, y) = (0, f(0)) yields f(f(f(0))) = 2f(0). Hence
2f(0) = f(0) so that f(0) = 0. Taking x = 0 yields
f(f(y)) = y for each y. We can complete the solution as in
the Second Solution.
32.
 32.

First solution. Let N = n^{nnn}  n^{nn}.
Since 1989 = 3^{2} ·13 ·17,
N º 0 (mod 1989) Û N º 0 (mod 9, 13 & 17) . 

We require the following facts:


(i) x^{u} º 0 (mod 9) whenever u ³ 2 and
x º 0 (mod 3).


(ii) x^{6} º 1 (mod 9) whenever x \not º 0
(mod 3).


(iii) x^{u} º 0 (mod 13) whenever x º 0 (mod 13).


(iv) x^{12} º 1 (mod 13) whenever x \not º 0
(mod 13), by Fermat's Little Theorem.


(v) x^{u} º 0 (mod 17) whenever x º 0 (mod 17).


(vi) x^{16} º 1 (mod 17) whenever x \not º 0
(mod 17), by FLT.


(vii) x^{4} º 1 (mod 16) whenever x = 2y + 1 is odd.
(For, (2y+1)^{4} = 16y^{3}(y+2) + 8y(3y+1) + 1 º 1 (mod 16).)


Note that
N = n^{nn} 
é ê
ë

n^{(nnn  nn)}  1 
ù ú
û

= n^{nn} 
é ê
ë

n^{nn (nnn  n  1)}  1 
ù ú
û

. 



Modulo 17. If n º 0 (mod 17), then
n^{nn} º 0, and so N º 0 (mod 17).


If n is even, n ³ 4, then n^{n} º 0 (mod 16),
so that
n^{nn(nnn  n  1)} º 1^{(nnn  n  1)} º 1 

so
N º 0 (mod 17).


Suppose that n is odd. Then n^{n} º n (mod 4)
Þ n^{n}  n = 4r for some r Î N 

Þ n^{nn  n} = n^{4r} º 1 (mod 16) 

Þ n^{nn  n}  1 º 0 (mod 16) 

Þ n^{nn(nnn  n  1)} º 1 (mod 17 

Hence
N º 0 (mod 17) for all
n ³ 3.


Modulo 13. If n º 0 (mod 13), then
n^{nn} º 0 and N º 0 (mod 13).


Suppose that n is even. Then n^{n} º 0 (mod 4),
so that n^{nn}  n^{n} º 0 (mod 4).
Suppose that n is odd. Then
n^{nn  n}  1 º 0 (mod 16) and so
n^{nn}  n^{n} º 0 (mod 4).


If n º 0 (mod 3), then n^{n} º 0 so
n^{n}(n^{nn  n}  1) º 0 (mod 3). If n º 1
(mod 3), then n^{nn  n} º 1 so n^{n}(n^{nnn}  1) º 0 (mod 3). If n º 2 (mod 3), then, as
n^{n}  n is always even, n^{nnn} º 1 so
n^{n}(n^{nnn}  1) º 0 (mod 3). Hence, for all n,
n^{nn}  n^{n} º 0 (mod 3).


It follows that n^{nn}  n^{n} º 0 (mod 12)
for all values of n. Hence, when n is not a multiple of
13, n^{(nnn  n)} º 1 so N º 0 (mod 13).


Modulo 9. If n º 0 (mod 3), then
n^{nn} º 0 (mod 9), so N º 0 (mod 9). Let
n \not º 0 (mod 9). Since n^{nn}  n^{n} is divisible
by 12, it is divisible by 6, and so
n^{(nnn  nn)} º 1 and N º 0 (mod 9).
Hence N º 0 (mod 9) for all n.


The required result follows.
33.
 33.

First solution. Letting b_{i} = (a_{i}, S_{i}), we find
that
[a_{i} , S_{i}] = 
a_{i} S_{i} (a_{i}, S_{i})

= 
a_{i} S_{i} b_{i}

. 

The given condition is equivalent to
a_{i} +
S_{i} =
b_{i} + (
a_{i} S_{i}/
b_{i}),
which is equivalent to
0 = b_{i}^{2}  (a_{i} + S_{i})b_{i} + a_{i} S_{i} = (b_{i}  a_{i})(b_{i}  S_{i}) . 

We can achieve the condition by making
a_{i} = (
a_{i},
S_{i}) and
S_{i} = [
a_{i},
S_{i}]. Let
a_{1} =
a_{2} = 1,
a_{i} = 2
^{i2} for
i ³ 3.
Then
S_{i} = 1 + 
i å
j = 2

2^{j2} = 1 + (2^{i1}  1) = 2^{i1} 

Þ (a_{i}, S_{i}) = 2^{i2} , [a_{i}, S_{i}] = 2^{i1} 

for
i ³ 3.
 33.

Second solution. Let a_{i} = 1, a_{2} = 2 and
a_{i} = 3 ·2^{i3} for i ³ 3. Then
S_{i} = 1 + 2 + 3 
i3 å
j = 0

2^{j} = 1 + 2 + 3(2^{i2}  1) = 3 ·2^{i2} 

Þ (a_{i}, S_{i}) = 3 ·2^{i3} , [a_{i}, S_{i}] = 3 ·2^{i2} 

for
i ³ 3.
 33.

Third solution. [K. Purbhoo] Choose a_{1} at will,
and let a_{i} = S_{i1} for i ³ 2. Then
S_{i} = S_{i1} + a_{i} = 2a_{i}, a_{i} + S_{i} = 3a_{i}, (a_{i}, S_{i}) = a_{i}
and [a_{i}, S_{i}] = 2a_{i} for i ³ 2.
 33.

Fourth solution. [K. Yeats] Let a_{1} = 1,
a_{2} = 3 and a_{n} = 2^{n1} for n ³ 3. Then
S_{n} = 2^{n} for n ³ 2 and, for each i with 3 £ i £ n,
(a_{i}, S_{i}) = 2^{i1} and [a_{i}, S_{i}] = 2^{i}.
34.
 34.

First solution. A common rational root must be
1 or 1, in which case the respective values of p are 0 and 2.
These roots are shared with x^{2}  1 (a = 0, b = 1). Suppose
that there is a common nonrational root r. Then
r^{2} = ar + b so that
r^{4} = a^{2} r^{2} + 2abr + b^{2} = (a^{3} + 2ab)r + (a^{2} b + b^{2}) 

whence
pr + 1 = r^{5} = (a^{3} + 2ab)r^{2} + (a^{2} b + b^{2})r = (a^{4} + 3a^{2} b + b^{2})r + b(a^{3} + 2ab) . 

Since
r is not rational,
p = a^{4} + 3a^{2} b + b^{2} and 1 = b(a^{3} + 2ab) . 

Hence 2
ap  1 = 2
a^{5} + 5
a^{3} b, so that
5
a^{3} b = 2
ap  2
a^{5}  1. Thus
1 = 
æ ç
è


2a^{5} + 2ap  1 5a^{3}


ö ÷
ø


æ ç
è

a^{3} + 
4a^{5} + 4pa  2 5a^{2}


ö ÷
ø



from which we obtain that
25a^{5} = (2a^{5} + 2pa  1)(a^{5} + 4pa  2) . 

This simplifies to
a^{10} + 3pa^{6} + 11a^{5}  4p^{2} a^{2} + 4pa  1 = 0 . 

This is a polynomial equation for
a with integer coefficients.
In order that
a be rational, it must be an integer dividing 1.
Hence
a =
±1. If
a = 1, then 1 =
b(1 + 2
b), whence
b =
^{1}/
_{2} or
b = 1. The first value does not give
an integer value of
p, but the second yields
p = 1.
In this case, the two polynomials are
x^{2} 
x + 1 and
x^{5} +
x  1 = (
x^{2} 
x + 1)(
x^{3} +
x^{2}  1) with common roots

w and 
w^{2}, where
w is an imaginary cube root
of unity.
If
a = 1, we get the equation 2
b^{2} +
b + 1 = 0 which is
satisfied by no rational value of
b. Thus the possibilities are
p = 1, 0, 2.
 34.

Second solution. The rational root case can be
handled as in the first solution. By long division, we find that
x^{5}  px  1 = (x^{2}  ax  b)[x^{3} + ax^{2} + (a^{2} + b)x + (a^{3} + 2ab)] 

+ (a^{4} + 3a^{2}b + b^{2}  p)x + (a^{3}b + 2ab^{2}  1) . 

If
r is a nonrational root of the quadratic and the quintic,
then its quadratic conjugate is also. So the quadratic must divide
the quintic and both coefficients of the foregoing division must
vanish. Hence
p =
a^{4} + 3
a^{2}b +
b^{2} and 1 =
b(
a^{3} + 2
ab), and
we can proceed as in the first solution.
35.
 35.

First solution. The result is clear if P is on
the bisector of the angle at A, since both sides of the inequality
are 0.


Wolog, let P be closer to AB than AC, and let Q be the
image of P under reflection in the bisector of the angle A. Then
ÐPAQ = ÐPAC  ÐQAC = ÐPAC  ÐPAB 

and
ÐPCQ = ÐQCB  ÐPCB = ÐPBC  ÐPCB . 

Thus, it is required to show that
ÐPAQ ³ ÐPCQ.


Produce PQ to meet AB in R and AC in S. Consider
the reflection Â with axis RS. The circumcircle
C of DARS is carried to a circle C¢ with
chord RS. Since ÐRCS < 60^{°} = ÐRAS and the
angle subtended at the major arc of C¢ by RS is
60^{°}, the point C must lie outside of C¢.
The circumcircle D of DAPQ is carried by
Â to a circle D¢ with chord PQ. Since D
is contained in C, D¢ must be contained in
C¢, so C must lie outside of D¢.
Hence ÐPQC must be less than the angle subtended at the
major arc of D¢ by PQ, and this angle is equal to
ÐPAQ. The result follows.
36.
 36.

First solution. By the ArithmeticGeometric Means
Inequality, we have that

1+x n+1

= 
n(1/n) + x n+1

³ 
é ê
ë


æ ç
è


1 n


ö ÷
ø

n

x 
ù ú
û

[1/(n+1)]



so that

(1 + x)^{n+1} (n+1)^{n+1}

³ 
x n^{n}



and the result follows.
 36.

Second solution (by calculus). Let
f(x) = n^{n} (1 + x)^{n+1}  (n+1)^{n+1}x for x > 0 . 

Then
f¢(x) = (n+1)[n^{n} (1 + x)^{n}  (n+1)^{n}] = (n+1)n^{n}[(1 + x)^{n}  (1 + 
1 n

)^{n} ] 

so that
f¢(
x) < 0 for 0 <
x < 1/
n and
f¢(
x) > 0 for 1/
n <
x.
Thus
f(
x) attains its minimum value 0 when
x = 1/
n and so
f(
x)
³ 0 when
x > 0. The result follows.
 36.

Third solution. Let u = nx  1 so that
x = (1 + u)/n. Then

(1 + x)^{n+1}  
(n+1)^{n+1} n^{n}

x 

= (1 + 
1 n

+ 
u n

)^{n+1}  (1 + 
1 n

)^{n+1}(1 + u) 
 
= (1 + 
1 n

)^{n+1} + (n+1)(1 + 
1 n

)^{n} 
u n

+ 
æ ç
è

n+1
2

ö ÷
ø

(1 + 
1 n

)^{n1}( 
u n

)^{2} 
 
+ 
æ ç
è

n+1
3

ö ÷
ø

(1 + 
1 n

)^{n2}( 
u n

)^{3} + ¼ (1 + 
1 n

)^{n+1}(1 + u) 
 
= 
æ ç
è

n+1
2

ö ÷
ø

(1 + 
1 n

)^{n1}( 
u n

)^{2}+ 
æ ç
è

n+1
3

ö ÷
ø

(1 + 
1 n

)^{n2}( 
u n

)^{3} + ¼ . 

 

This is clearly nonnegative when
u ³ 0. Suppose that
1 <
u < 0. For 1
£ k £ n/2, we have that

æ ç
è

n+1
2k

ö ÷
ø

(1 + 
1 n

)^{n2k+1}( 
u n

)^{2k}+ 
æ ç
è

n+1
2k+1

ö ÷
ø

(1 + 
1 n

)^{n2k} ( 
u n

)^{2k+1} 

= 
(n+1)!(1 + 1/n)^{n2k} (2k+1)!(n+12k)!


æ ç
è


u n


ö ÷
ø

2k

[(2k+1)(1 + 
1 n

) +(n+1  2k)( 
u n

) ] . 

This will be nonnegative if and only if the
quantity in square brackets is
nonnegative. Since
u > 1, this quantity exceeds
(2k+1)(1 + 
1 n

)  (n + 1  2k)( 
1 n

) = 
æ ç
è


n+1 n


ö ÷
ø

(2k + 1  1)  
2k n

= 2k > 0 . 

Thus, each consecutive pair of terms in the sequence

æ ç
è

n+1
2

ö ÷
ø

(1 + 
1 n

)^{n1}( 
u n

)^{2}+ 
æ ç
è

n+1
3

ö ÷
ø

(1 + 
1 n

)^{n2}( 
u n

)^{3} + ¼ 

has a positive sum and so the desired result follows.