Solutions

127.

Let

A = 2ⁿ + 3ⁿ + 216(2^n-6 + 3^n-6)

and

B = 4ⁿ + 5ⁿ + 8000(4^n-6 + 5^n-6)

where n > 6 is a natural number. Prove that the fraction A/B is reducible.

Solution 1. Observe that

xⁿ + yⁿ + x³y³(x^n-6 + y^n-6) = (x^n-3 + y^n-3)(x³ + y³) = (x^n-3 + y^n-3)(x + y)(x² - xy + y²) .

When (x, y) = (2, 3), x² - xy + y² = 7, while, when (x, y) = (4, 5), x² - xy + y² = 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⁶ º 1 (mod 7), whenever a is not a multiple of 7. Observe that 216 º 8000 º -1 (mod 7). Then, modulo 7,

A º 2ⁿ + 3ⁿ - 2^n-6 - 3^n-6 = 2^n-6(2⁶ - 1)+ 3^n-6(3⁶ - 1) º 0

and

A º 4ⁿ + 5ⁿ - 4^n-6 - 5^n-6 = 4^n-6(2⁶ - 1)+ 5^n-6(3⁶ - 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⁴ = 10d + 1 for some c, so that its rightmost digit is 1 (b, c and d are some integers). Then

0 = f(3b⁴) = f(3) + f(b⁴) = 0 + f(b⁴) = 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 semi-circles, 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²/4 or b²/4. Thus, the maximum area of the circumscribed rectangle is

æ
ç
è

a²

b²

ö
÷
ø

+ ab =

(a + b)² .

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 n-1 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 ]

__
Ö10

+ 19

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

Ö[5 ]3 Ö2 - 2 Ö5

·Ö[10 ]

__
Ö10

+ 19

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

__
Ö10

+ 19

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

__
Ö10

)·

(19 + 6

__
Ö10

)

= -Ö[10 ]361 - 360 = -1 .