Solutions to problems in previous issues

Perfect numbers - pages 21 & 27 of Issue 5.1

Euler's theorem (Exercise 7 of page 22.) Here is Euler's proof that every even perfect number has the form 2^m-1(2^m-1), where 2^m-1 is a (Mersenne) prime:

Suppose that (1) n is perfect, and (2) n is even - so of form n = 2^m-1q, where m,q > 1; and suppose that (3) q is NOT a prime. From (2), the divisors of n are the numbers of form 2^rd, where 0 £ r £ m-1 and d divides q, hence the sum of the divisors is: s(n) = (1+2+¼2^m-1)s(q). From (1), we know that s(n) = 2n = 2^mq. Therefore:

(2m-1)(s(q)-q) = q                      (4)

By (3), s(q) > q+1, since q has at least one more factor besides 1 and itself. But then from (4) q has distinct factors 1, s(q)-q,  q. (The latter two can't be equal for that would make 2^m-1 = 1, which is impossible.) Therefore (s(q) ³ 1+(s(q)-q)+q = s(q)+1, which is absurd.

This contradiction assures us that q must be prime , so that s(q) = q+1, and hence q = 2^m-1, from (4). This completes the proof that n = 2^m-1(2^m-1), with 2^m-1 prime.

Do you remember (from the previous issue) the two great unsolved problems? Nobody yet knows if every perfect number has this form, but nobody has yet found an odd perfect number. And nobody knows how many perfect numbers there are, or whether the number is infinite. If you can answer either of these, we will not only proudly print your answer, but can guarantee you a mention in the international press too!

Can a perfect square be a perfect number? (Exercise 9, page 22.)

Owen Sibanda of Zvishavane says NO, and gives a very creditable proof, winning the Prize. He assumes Euler's result (above) that every even perfect number is of Euclid's form 2ⁿ(2ⁿ⁺¹-1) where 2ⁿ⁺¹-1 is prime. He also (as he carefully points out) takes for granted a positive answer to the Open Question 1 (page 24) mentioned above: Is every perfect number even? Until the great moment when this is proved, Sibanda is really proving a weaker result: No even perfect square can be a perfect number. Here is his argument:

Suppose there exists m:m² = 2ⁿ(2ⁿ⁺¹-1), where p = 2ⁿ⁺¹-1 is prime. Then, by Exercise 8 of page 22, proved on page 27 of Issue 5.1, n+1 must be a prime too, so (n = 1 fails to give a square) must be odd, and hence n must be even. Letting n = 2r, r ³ 1, we have 2ⁿ = 2^2r = (2^r)² is a perfect square. Now p, being prime, cannot be a square number, so neither is 2ⁿp. (The prime factor p occurs an odd number of times.)

Alternative (more general) proof:

Remember from the article (page 20 of Issue 5.1) on perfect numbers that each number n can be expressed uniquely as a product of its prime factors. That is, n = p₁^x₁.p₂^x₂.p₃^x₃¼p_m^x_m, where p₁ < p₂ < p₃ < ¼ < p_m are primes, and x₁,x₂,x₃¼x_m are positive integers. The divisors of n are all possible combinations of powers of these primes, taking the form n = p₁^y₁.p₂^y₂.p₃^y₃¼p_m^y_m where 0 £ y_i £ x_i for all i. The sum of all the divisors of n is therefore

s(n) = (1+p1+p12+¼p1x1)(1+p2+p22+¼p2x2)¼(1+pm+pm2+¼pmxm) = æ è p1x1+1-1 p1-1 ö ø . æ è p2x2+1-1 p2-1 ö ø . æ è p3x3+1-1 p3-1 ö ø .¼ æ è pmxm+1-1 pm-1 ö ø ;

and the total number of divisors of n is given by the product:

(x1+1)(x2+1)(x3+1)¼(xm+1).

Let \dsn = m² = ( P_{i = 1}^{i = s} p_i^a_i)² = p₁^2a₁p₂^2a₂¼p_s^2a_s. (Here P stands for `product'.)
Thus the sum of the divisors is \dss(n) = s(p₁^2a₁).s(p₂^2a₂)¼s(p_s^2a_s).
Now each term s(p_i^2a_i) = 1+p_i+p_i²+¼+p_i^2a_i is odd, since each power of an (odd) prime is odd, and there are an odd number of odd numbers being summed. Therefore their product s(n) is odd, and cannot be equal to 2n, so n is not a perfect number.

Postscript:

We have shown incidentally that for any perfect square n, the sum of its divisors is odd. It is also true that the number of divisors of a perfect square is odd. In fact, this characterizes square numbers:

a number is a perfect square Û the number of its divisors is odd.

Proof: The number of divisors is (2a₁+1)(2a₂+1)¼(2a_s+1), which is a product of odd numbers. Or else, just observe that the factors of any number n occur in pairs (f,g): fg = n; for square numbers, and for them only, there is an odd one out-when f = g.

This is the basis for a very nice puzzle. Here it is, and a PRIZE awaits the first correct (and well-justified) solution opened after 31st July.

2  The Eccentric Jailor Problem

Readers' Problem 5.1-2

What is 10+10? And 20+20? Warning - consider all possible bases!

This was solved by Mkachano Munyaradzi of Rufaro Sec. School.

Solution:

10₂+10₂ = 100₂

10₃+10₃ = 20₃ that is 3+3 = 6 in base 10,

and 10+10 = 20, in any base b ³ 3.

20₃+20₃ = 110₃, that is 6+6 = 12 = 9²+3 in base 10,

20₄+20₄ = 100₄, that is 8+8 = 16 = 4² in base 10,

20₅+20₅ = 40₅, that is 10+10 = 20 = 4(5) in base 10,

and 20+20 = 40, in any base b ³ 5.

Readers' Problem 5.1-5

This was solved by Owen Sibanda, Kennedy Kundanayi, and T Mutingwende. Here is Sibanda's solution.

Solution: He starts by introducing some very useful notation: let c, g, r be the numbers of cows, goats and rabbits, respectively, each required to be at least 1. Then we are given two equations to solve:

c+g+r = 100      (1)

10⁴c+10³g+10²r = 10⁵,

that is, 100c+10g+r = 1000.      (2)

Now (1) ×10 gives 10c+10g+10r = 1000,      (3)

and subtracting (1) from (2): 99c+9g = 900,

gives 11c+g = 100.      (4)

Subtracting (3) from (2): 90c-9r = 0,

that is 10c-r = 0.      (5)

Using (4) and (5), r = 10c and g = 100-11c; since both are positive by hypothesis, we have 0 < c < 10 and so finally we have the following solutions:

(c,g,r) in (1,89,10), (2,78,20), (3,67,30), (4,56,40), (5,45,50), (6,34,60), (7,23,70), (8,12,80), (9,1,90).

Readers' Problem 5.1-6

In a triangle ABC, angle B = 90^o, and sides AB = BC = 4. What is the area of the region containing all points P such that all the angles APB, BPC, APC are obtuse?

The principle involved here is best illustrated by this diagram; the angle subtended by a diameter is a right angle ON the circle, acute OUTSIDE the circle, and obtuse INSIDE the circle.

The problem was solved by Thomas Masiwa, Tiri Mutingwende, and (jointly) by Owen Sibanda and Jabusile Shumba, whose solution we give.

Solution: In the diagram, X,Y,Z are the midpoints of AB, BC, AC, respectively. The point P can be anywhere inside the circle on diameter AB (for ÐAPB to be obtuse), and anywhere inside the circle on diameter BC (for ÐBPC to be obtuse). These circles obviously intersect at B and Z, so the common (shaded) region lies within the square BXZY, and is already wholly within the circle on diameter AC, since B lies on this circle (ÐABC is a right angle). Therefore ÐAPC will also be obtuse.

Using symmetry, the area of the shaded region is:

A = 2(area  of  quadrant XBZ- area  of  triangle XBZ) = 2( 1 4 p(22)- 1 2 (22)) = 2(p-2).

Prizewinners and Solutions for the Zimaths Competition

No prize was deserved in the Abnormal Section. Congratulations to you Rufaro students! Are the rest of you going to give them some competition this time?

Normal Section

1.  The sum of two 3-digit numbers is 1252. They consist of the same three 3 digits but in inverse order. The sum of these three digits is 14 and the sum of their three squares is 84. Find these two numbers.

Solution: Many people submitted solutions which involved guesswork, or trial-and-error, or `brute-force'. This is good for finding your way, but not for a final polished proof. We were looking for something more elegant and systematic, a method which will work for other similar problems also. Here is such a method:

Let the number be a.10²+b.10+c. Then

a.102+b.10+c+c.102+b.10+a = 1252, so 101a+20b+101c = 1252,

(1)

and we are also given

a+b+c = 14

(2)

a2+b2+c2 = 84.

(3)

To solve this system of three equations, substitute a = 14-b-c (from (2)) into (1), to get

101(14-b-c+c)+20b = 1252Þ b = 2, a = 12-c.

(4)

Next, substituting these into (3) gives

(12-c)2+22+c2 = 84 Þ c2-12c+32 = (c-4)(c-8) = 0 Þ c = 4, 8.

(5)

Therefore a = 12-c = 8, 4, so the numbers are 428, 824.

In addition to our prizewinners, Tinashe Mangoro and Lesley Nyazire of Hama High, and Ozias Farai Goredema of Kutama produced good solutions to this problem. And Akimu Mageza of Hama used an interesting argument which we reproduce here. Well done Akimu! Future prizes may be yours! Here is his method:

Let the digits be a,b,c, so that

a b c + c b a 1 2 5 2

Since, in the tens column, 2b cannot be an odd number (5), we know there is a 1 carried over from the units column, so 2b is 4 or 14, while a+c = 12. Since, in the hundreds column, a+c = 12 too, there cannot be a 1 carried over from the tens column; therefore 2b = 4. Now substituting b = 2 and c = 12-a in the given equation a²+b²+c² = 84, we get an equation in a alone, which boils down to the quadratic equation a²-12a+32 = (a-8)(a-4) = 0, giving a = 4 or a = 8. When a is one of these, c is the other, so the unknown numbers are 824,  428. Interestingly, this method shows that the equation a+b+c = 14 is redundant!

2.  For every possible real number a, solve the equation (x-1).|x| = a.

Solution:
Let f(x) = (x-1).|x| = {

x2-x,	x ³ 0
-x2+x,	x < 0.

The given equation has a solution if the straight
line y = a meets the graph of y = f(x). Hence:

(a) If a Î (-¥, -[1/4]), there is a unique solution:

-x2+x = a Þ x2-x+a = 0 Þ x = [1/2](1-Ö[(1-4a)]).

(b) If a = -[1/4], there are two solutions: x₁ = [1/2](1-Ö2), x₂ = [1/2].

(c) If a Î (-[1/4], 0), there are three solutions:

x1 = [1/2](1-Ö[(1-4a)]);   x2-x-a = 0 Þ x2, x3 = [1/2](1±Ö[(1+4a)]).

(d) If a = 0, there are two solutions: x₁ = 0, x₂ = 1.

(e) If a > 0, there is a unique solution: x = [1/2](1+Ö[(1+4a)]).

3.  Given a \triangle ABC with the sides a, b, c satisfying a > b > c. Find a value of x (positive or negative) which has to be added to each side to get a right angled triangle (with sides a+x, b+x, c+x), and show that it is unique.

Solution: Using Pythagoras' theorem:

(a+x)2 = (b+x)2+(c+x)2 Þ x2+2x(c+b-a)-a2+b2+c2 = 0 Þ x1, x2 = a-b-c±   _________ Ö2(a-b)(a-c)   .

There are thus at most two possible values of x. We must check each to see if it does satisfy the conditions of the problem.

(a)  x₁ = a-b-c+Ö[(2(a-b)(a-c))]. Since a > b > c we have:
          a+x₁ > b+x₁ > c+x₁; checking whether all are positive:

c+x = c+a-b-c+Ö[(2(a-b)(a-c))] = (a-b)+Ö[(2(a-b)(a-c))] > 0,

since both terms are positive.

(b)  x₂ = a-b-c-Ö[(2(a-b)(a-c))]. Check:

c+x = c+a-b-c-Ö[(2(a-b)(a-c))] = (a-b)-Ö[(2(a-b)(a-c))].

Supposing that c+x > 0, we deduce that (a-b) > Ö[(2(a-b)(a-c))]. Because both sides are positive, this implies

(a-b)2 > 2(a-b)(a-c) Þ a-b > 2(a-c)Þ a+b < 2c.

But this is a contradiction, since a > b > c Þ a+b > 2c. Hence in this case c+x\not > 0. The solution x₁ is unique.

Abnormal Section

1.  The three real numbers a, b and c satisfy  abc = -[(a+b+c)/(Ö3)].
Show that the absolute value of at least one of a, b, or c does not exceed [1/(Ö3)].
(Hint: First, take a > 0, b > 0 and c < 0, and consider (aÖ3-1)(bÖ3-1) .)

Solution: It is clear that a,b,c cannot all have the same sign. Assume first that a > 0, b > 0 and c < 0, and denote c₁ = -c > 0. Suppose the result is false - i.e. that a,b,c₁ > [1/(Ö3)]. Then

(aÖ3-1)(bÖ3-1) > 0Þ 3ab > Ö3(a+b)-1,   so that

abc = -abc1 < - 1 Ö3 ab < - 1 3 (a+b)+ 1 3Ö3 < - 1 3 (a+b)+ 1 3 c1 = - 1 3 (a+b+c).

This is a contradiction of what we were given. The result must therefore be true.

Next, assume that a < 0, b < 0 and c > 0. Denote a₁ = -a > 0, b₁ = -b > 0. Suppose the result is false as before, and then

(aÖ3-1)(bÖ3-1) > 0Þ 3a1b1 > Ö3(a1+b1)-1,   so that

abc = a1b1c > 1 Ö3 a1b1 > 1 3 (a1+b1)- 1 3Ö3 > 1 3 (a1+b1)- 1 3 c = - 1 3 (a+b+c).

Again, we have a contradiction.

2.  Find a 100-digit number which contains no zeros and is a multiple of the sum of its digits.

Solution: Notice that if a natural number ends with digits 125 then it is a multiple of 125. Therefore a solution is the following number, with a string of 94 1¢s:   111¼1995125.

3.  A certain micro-calculator can add, subtract, and can find for any non-zero number x its inverse [1/x]. Is it possible to get 1 starting from an original number

(a)  Ö[19]88?    (b)  Ö[19]+Ö[88]?

You are not permitted to input any number except that original number and all numbers obtained from it by the allowed operations.
(Hint: Start with any two numbers x, y and, performing the allowed operations only, show that you can get xy². See also the Zimaths Abnormal Competition 4.2 no.3)

Solution: The answer is YES for (a),  NO for (b).
It is easy to see that, for any numbers x, y, we have the identity:

1 x - 2 1 1 x +y + 1 1 x -y = xy2.

Hence, from any number x we can (by putting y = x, x²,¼) get x³, x⁵, ¼,x¹⁹, and therefore from Ö[19]88 we can get 88, then [1/88], and finally (adding 88 of these together) we have 1.

However, applying the allowed operations to numbers of the form aÖ[19]+bÖ[88], where a,b are rational numbers, will always get numbers of the same form (and 1 cannot be expressed in this form). For example:

1 a   __ Ö19   +b   __ Ö88   = 1 a   __ Ö19   +b   __ Ö88   . æ ç ç ç ç è a   __ Ö19   -b   __ Ö88   a   __ Ö19   -b   __ Ö88   ö ÷ ÷ ÷ ÷ ø = a   __ Ö19   -b   __ Ö88   19a2-88b2 = æ ç è a 19a2-88b2 ö ÷ ø .   __ Ö19   + æ ç è b 19a2-88b2 ö ÷ ø .   __ Ö88   .