Solutions

127.

Let
A = 2^{n} + 3^{n} + 216(2^{n6} + 3^{n6}) 

and
B = 4^{n} + 5^{n} + 8000(4^{n6} + 5^{n6}) 

where n > 6 is a natural number. Prove that the
fraction A/B is reducible.
Solution 1. Observe that
x^{n} + y^{n} + x^{3}y^{3}(x^{n6} + y^{n6}) = (x^{n3} + y^{n3})(x^{3} + y^{3}) = (x^{n3} + y^{n3})(x + y)(x^{2}  xy + y^{2}) . 

When (x, y) = (2, 3), x
^{2}  xy + y
^{2} = 7, while, when
(x, y) = (4, 5), x
^{2}  xy + y
^{2} = 21 = 7 ×3. It follows
that, for each n > 6, both A and B are divisible by 7 and the
result follows.
Solution 2. We consider the values of A and B modulo 7,
and use the fact that a^{6} º 1 (mod 7), whenever a is not
a multiple of 7. Observe that 216 º 8000 º 1 (mod 7).
Then, modulo 7,
A º 2^{n} + 3^{n}  2^{n6}  3^{n6} = 2^{n6}(2^{6}  1)+ 3^{n6}(3^{6}  1) º 0 

and
A º 4^{n} + 5^{n}  4^{n6}  5^{n6} = 4^{n6}(2^{6}  1)+ 5^{n6}(3^{6}  1) º 0 , 

so that both A and B are divisible by 7 and A/B is reducible.
Comment. The same conclusion holds when 216 is replaced by 6
and 8000 replaced by 20.

128.

Let n be a positive integer. On a circle,
n points are marked. The number 1 is assigned to one
of them and 0 is assigned to the others. The following
operation is allowed: Choose a point to which 1 is assigned
and then assign (1  a) and (1  b) to the two adjacent
points, where a and b are, respectively, the numbers
assigned to these points before. Is it possible to assign
1 to all points by applying this operation several times
if (a) n = 2001 and (b) n = 2002?
Solution. (a) It is clear that we can obtain a string of
3 ones, with all the other positions marked with a zero.
Suppose that we have a string of 2k
 1 ones with all the
other postions marked with a zero. Note that three consecutive
entries 1, 1, 0 can be changed to 0, 1, 1 and that three consecutive
entries 0, 1, 0 can be changed to
1, 1, 1. By starting at one end of the
string of ones and using the first operation to ``shift'' a
zero over two position until we come to the entries 0, 1, 0
at the other end of the string, we see that we can obtain a string
of 2k + 1 ones. We can repeat this for k = 1,
¼, 1000
until we achieve all ones.
(b) Observe that the parity the number of ones does not change.
If we start with a single one, then there must be an odd number of ones,
so we cannot solve the problem when n = 2002.

129.

For every integer n, a nonnegative integer
f(n) is assigned such that


(a) f(mn) = f(m) + f(n) for each pair m, n
of natural numbers;


(b) f(n) = 0 when the rightmost digit in the
decimal representation of the number n is 3; and


(c) f(10) = 0.


Prove that f(n) = 0 for any natural number n.
Solution 1. Substituting m = 1, we find that f(1) = 0.
Substituting m = n =
1, we find that f(
1) = 0, and
substituting m =
1 yields that f(n) = f(
n) for every integer
n. So we suppose henceforth that n > 0.
Let n = 10k + 1, then 0 = f(30k + 3) = f(3) + f(10k + 1) = 0 + f(n). Let n = 10k + 7. Then
f(n) = f(3) + f(10k + 7) = f((3k+2)10 + 1) = 0. 

Finally, let n = 10k + 9. Then
f(n) = f(3) + f(10k + 9) = f((3k+2)10 + 7) = 0. 

If follows that f(n) = 0, whenever n and 10 are coprime.
Since 0 = f(10) = f(2) + f(5), and f(2) ³ 0, f(5) ³ 0,
if follows that f(2) = f(5) = 0. The result now follows by
applying (a) to the prime factorization of a given number n.
Solution 2. As in Solution 1, we can show that f(2) = f(5) = 0. Consider the prime factorization of n, say,
n = 2^{r} 5^{s} b, where the greatest common divisor of b and
10 is equal to 1. Since b = 10a ±1, or b = 10c ±3,
we have that b^{4} = 10d + 1 for some c, so that its
rightmost digit is 1 (b, c and d are some integers).
Then
0 = f(3b^{4}) = f(3) + f(b^{4}) = 0 + f(b^{4}) = 4f(b) , 

whence f(n) = rf(2) + sf(5) + f(b) = 0.

130.

Let ABCD be a rectangle for which the
respective lengths of AB and BC are a and b.
Another rectangle is circumscribed around ABCD so that
each of its sides passes through one of the vertices of
ABCD. Consider all such rectangles and, among them,
find the one with a maximum area. Express this area in
terms of a and b.
Solution. The circumscribed rectangle is the union of the
inner rectangle and four right triangles whose hypotenuses are the
four sides of the inner rectangle. The apexes of these four right
triangles lie on semicircles whose diameters are the four sides of
the inner rectangle, so that the altitudes of the right triangles
from the hypotenuses cannot exceed the radii of the semicircles,
namely a/2 or b/2.
We can circumscribe a rectangle each of whose right triangles is
isosceles, and whose heights are a/2 or b/2 and areas are
a^{2}/4 or b^{2}/4. Thus, the maximum area of the circumscribed
rectangle is
2 
æ ç
è


a^{2} 4

+ 
b^{2} 4


ö ÷
ø

+ ab = 
1 2

(a + b)^{2} . 


131.

At a recent winter meeting of the Canadian
Mathematical Society, some of the attending mathematicians
were friends. It appeared that every two mathematicians, that
had the same number of friends among the participants, did
not have a common friend. Prove that there was a mathematician
who had only one friend.
Comment. Note that the result is false if there is no
mathematician who has a friend. Thus, we need to assume that there
is at least one pair of friends.
Solution 1. Wolog, we may assume that each person present has
at least one friend. We prove the result by induction. It is
clearly true when there are only two people. Let S be the
set of people in the crowd, each of whom has the minimum number of friends.
Suppose if possible, that this minimum exceeds 1. The set S
is nonempty. Let T consist of all of the others. Then, looking
at all the pairs of friends within T, by an induction hypothesis,
there is a person p in T with only one friend in T. Since
any two people in S cannot have a friend in common, p can
have at most have one friend in S. Since, by hypothesis, p cannot
have a single friend, p must have two friends. But then p should
have been included in S, and we arrive at a contradiction.
Solution 2. Let q be the person with the maximum number n of
friends (or one of several, if there is more than one having the
same maximum number of friends). Each of the n friends of q
has at least one friend. If any of them has exactly one friend,
the the result holds. Assume, if possible,
that none of them has exactly one
friend. Since n is the maximum possible number of friends,
there are n1 possibilities for the number of friends that these
n people have. By the Pigeonhole Principle, there must be two
of them with the same number of friends. But the given conditions
require that two persons with the same number of friends do not
have a common friend. But this contradicts q being the common
friend of them. Therefore, there must be someone with one friend.

132.

Simplify the expression
Ö[5 ]3 Ö2  2 Ö5·Ö[10 ] 
2

. 

Solution. Observe that (3
Ö2
 2
Ö5)
^{2} = 2(19
 6
Ö[10]), and that 3
Ö2
 2
Ö5 < 0. Hence
2
Ö5
 3
Ö2 =
Ö{2(19
 6
Ö[10]}, and so

 
= Ö[5 ]2 Ö5  3 Ö2·Ö[10 ] 
2


 
= Ö[10 ](2(19  6 
 __ Ö10

)· 
1 2

(19 + 6 
 __ Ö10

) 
 
= Ö[10 ]361  360 = 1 . 

