CMS/SMC
Société mathématique du Canada
www.smc.math.ca
Société mathématique du Canada
  location: 
       

Solutions for October Problems


Comment on problems 339 and 342. In both these problems, a condition was left out and made each of them trivial. Accordingly, problem 339 is marked out of 4 and problem 342 out of 3, for the basic solution. However, additional marks were provided for students who recognized that the problems might have been misstated and provided work that led to the intended solutions. While I try to make sure that the problems are correct, and certainly on contests, the problems are generally gone over very carefully, mistakes do occur. If on a contest, you feel that a mistake has been made in formulating a problem, then you should state clearly a non-trivial version of the problem and solve that. In the solutions below, the corrected version of the problem is given.


339.
Let a, b, c be integers with abc 0, and u, v, w be integers, not all zero, for which
au2 + bv2 + cw2 = 0 .
Let r be any rational number. Prove that the equation
ax2 + by2 + cz2 = r
is solvable for rational values of x, y, z.
Solution 1. Suppose, wolog, that u 0. Try a solution of the form
(x, y, z) = (u(1 + t), vt, wt) .
Then au2 + 2au2t + au2t2 + b2v2t2 + cw2t2 = r implies that 2au2t = r - au2, from which we find the value t = (r - au2)/((2au2). Since a, b, c, u, v, w, r, t are all rational, so is the trial solution.

Solution 2. [R. Peng] Suppose that r = p/q. Then the equation with r on the right is satisfied by

(x, y, z) =
 p

2
+  1

2qa
,
 p

2
-  1

2qa


 v

u

,
 p

2
-  1

2qa


 w

u


 .

Comment. If not all a, b, c are zero, then it is trivial to prove that the equation with r on the right has a solution; the only rôle that the equation with 0 on the right plays is to ensure that a, b, c do not all have the same sign. However, some made quite heavy weather of this. The hypothesis that integers are involved should alert you to the fact that some special character of the solution is needed. It is unreasonable to ask that the solution be in integers, but one could seek out rational solutions.


340.
The lock on a safe consists of three wheels, each of which may be set in eight different positions. Because of a defect in the safe mechanism, the door will open if any two of the three wheels is in the correct position. What is the smallest number of combinations which must be tried by someone not knowing the correct combination to guarantee opening the safe?
Solution. The smallest number of combinations that will guarantee success is 32. Denote the eight positions of each whell by the digits 0, 1, 2, 3, 4, 5, 6, 7, so that each combination can be represented by an ordered triple (a, b, c) of three digits. We show that a suitably selected set of 32 combinations will do the job. Let A = { (a, b, c) : 0 a, b, c 3  and a + b + c 0 (mod ) 4 } and B = { (u, v, w) : 4 u, v, w 7  and  u + v + w 0 (mod ) 4 }. Any entry in the triples of A and B is uniquely determined by the other two, and any ordered pair is a possibility for these two. Thus, each of A and B contains exactly 16 members. If (p, q, r) is any combination, then either two of p, q, r belong to the set { 0, 1, 2, 3 } and agree with corresponding entries in a combination in A, or two belong to { 4, 5, 6, 7 } and agree with corresponding entries in a combination in B.

We now show that at least 32 combinations are needed. Suppose, if possible, that a set S of combinations has three members whose first entry is 0: (0, a, b), (0, c, d), (0, e, f). There will be twenty-five combinations of the form (0, y, z) with y a, c, e, z b, d, f, that will not match in two entries any of these three. To cover such combinations, we will need at least 25 distinct combinations of the form (x, y, z) with 1 x 7. None of the 28 combinations identified so far match the 7 ×6 = 42 combinations of the form (u, v, w), where v { a, c, e }, w {b, d, f }, (v, w) (a, b), (c, d), (e, f). Any combination of the form (u, v, t) or (u, t, w) can cover at most three of these and of the form (t, v, w) at most 7. Thus, S will need at least 37 = 3 + 25 + (42/7) members to cover all the combinations. A similar argument obtains if there are only three members in S with any other given entry. If there are only one or two members in S with a given entry, say first entry 0, then at least 36 combinations would be needed to cover all the entries with first entry 0 and the other entries differing from the entries of these two elements of S.

Thus, a set of combinations will work only if there are at least four combinations with a specific digit in each entry, in particular at least four whose first entry is k for each of k = 0, , 7. Thus, at least 32 entries are needed.

Comment. Some solvers formulated the problem in terms of the minimum number of rooks (castles) required to occupy or threaten every cell of a solid 8 ×8 ×8 chessboard.



341.
Let s, r, R respectively specify the semiperimeter, inradius and circumradius of a triangle ABC.
(a) Determine a necessary and sufficient condition on s, r, R that the sides a, b, c of the triangle are in arithmetic progression.
(b) Determine a necessary and sufficient condition on s, r, R that the sides a, b, c of the triangle are in geometric progression.
Comment. In the solutions, we will use the following facts, the establishment of which is left up to the reader:
a + b + c = 2s

ab + bc + ca = s2 + 4Rr + r2

abc = 4Rrs
An efficient way to get the second of these is to note that the square of the area is given by r2s2 = s(s-a)(s-b)(s-c) from which
r2s = s3 - (a + b + c)s2 + (ab + bc + ca)s - abc = s3 - 2s3 + (ab + bc + ca)s - 4Rrs .

Solution 1. (a) a, b, c are in arithmetic progression if and only if

0
= (2a - b - c)(2b - c - a)(2c - a - b)
= (2s - 3a)(2s - 3b)(2s - 3c)
= 8s3 - 12s2(a + b + c) + 18s(ab + bc + ca) - 27abc
= 2s3 - 36Rrs + 18r2s .
Since s 0, the necessary and sufficient condition that the three sides be in arithmetic progression is that s2 + 9r2 = 18Rr.

(b) First, note that

a3 + b3 + c3
= (a + b + c)3 - 3(a + b + c)(ab + bc + ca) + 3abc
= 2s3 - 12Rrs - 6r2s ,
and
a3 b3 + b3 c3 + c3 a3
= (ab + bc + ca)3 - 3abc(a + b + c)(ab + bc + ca) + 3(abc)2
= (s2 + 4Rr + r2)3 - 24Rrs4 - 48R2r2s2 - 24Rr3s2 .
a, b, c are in geometric progression if and only if
0
= (a2 - bc)(b2 - ca)(c2 - ab)
= abc(a3 + b3 + c3) - (a3b3 + b3c3 + c3a3)
= 32Rrs4 - (s2 + 4Rr + r2)3 ,
The necessary and sufficient condition is that
(s2 + 4Rr + r2)3 = 32Rrs4 .

Solution 2. The three sides of the triangle are the three real roots of the cubic equation

x3 - 2sx2 + (s2 + r2 + 4Rr)x - 4Rrs = 0 .
The three sides are in arithmetic progression if and only if one of them is equal to 2s/r and are in geometric progression if and only if one of them is equal to their geometric mean 3 {4Rrs}.

(a) The condition is that 2s/3 satisfies the cubic equation:

0 = 8s3 - 6s(4s2) + 9(s2 + r2 + 4Rr)(2s) - 108Rrs = 2s(s2 + 9r2 - 18Rr) .

(b) The condition is that 3 {4Rrs} satisfies the cubic equation: 2s(4Rrs)1/3 = s2 + 4Rr + r2 or 32Rrs3 = (s2 + 4Rr + r2)3.

Solution 3. [B.H. Deng] Assume that b lies between a and c, inclusive. (a) The three sides are in arithmetic progression if and only if b = 2/3s or a + c = 2b. Since 4Rrs = abc, this is equivalent to 6Rr = ac, which in turn is equivalent to

r2 + s2 + 4Rr = (a + c)b + ac = 2b2 + ac = (8/9)s2 + 6Rr
or s2 + 9r2 = 18Rr.

(b) The three sides are in geometric progression if and only if b3 = abc = 4Rrs and ac = b2. This holds if and only if

r2 + s2 + 4Rr = (a + c)b + ac = (2s - b)b + ac = 2s
3
 

4Rrs
 
- b2 + ac = 2s
3
 

4Rrs
 
or (r2 + s2 + 4Rr)3 = 32Rrs4.



342.
Prove that there are infinitely many solutions in positive integers, whose greatest common divisor is equal to 1, of the system
a + b + c
= x + y
a3 + b3 + c3
= x3 + y3 .
Solution 1. Suppose that a, b, c are in arithmetic progression, so that c = 2b - a and x + y = 3b. Then
x2 - xy + y2 =  a3 + b3 + c3

a + b + c
= 3b2 - 4ab + 2a2
so that
3xy = (x + y)2 - (x2 - xy + y2) = 6b2 + 4ab - 2a2
and
xy = 2b2 +  2a(2b - a)

3
 .
Therefore
(y - x)2 = (x + y)2 - 4xy = b2 -  8a(2b - a)

3
=  (3b - 8a)2 - 40a2

9
 .

Let p = 3b - 8a, q = 2a. We can get solutions by solving p2 - 10q2 = 9. Three solutions are (p, q) = (3, 0),(7, 2), (13, 4). The fundamental solution of u2 - 10v2 = 1 is (u, v) = (19, 6). So from any solution (p, q) = (r, s) of p2 - 10q2 = 9, we get another (p, q) = (19r + 60s, 6r + 19s). For these to yield solutions (a, b, c; x, y) of the original system, we require q to be even and p + 4q to be divisible by 3. Since 19r + 60s r (mod 3) and 6r + 19s s (mod 2), if (p, q) = (r, s) has these properties, then so also does (p, q) = (19r + 60s,6r + 19s). Starting with (r, s), we can define integers p and q, and then solve the equations x + y = 3b, y - x = 1. Since p and so b are odd, these equations have integer solutions. Here are some examples:

(p, q; a, b, c; x, y) =
(3, 0; 0, 1, 2; 1, 2), (57, 18; 9, 43, 77; 64, 65),
(7, 2; 1, 5, 9; 7, 8), (253, 80; 40, 191, 342; 286, 287) .

Solution 2. [D. Dziabenko] Let a = 3d. c = 2b - 3d, so that x + y = 3b and a, b, c are in arithmetic progression. Then

a3 + b3 + c3
= 27d3 + b3 + 8b3 - 36b2d + 54bd2 - 27d3
= 9b3 - 36b2d + 54bd2 = 9b(b2 - 4b2d + 6d2) ,
whence x2 - xy + y2 = 3b2 - 12bd + 18d2. Therefore
3xy = (x + y)2 - (a2 - xy + y2) = 6b2 + 12bd - 18d2
so that xy = 2b2 + 4bd - 6d2 and
(x - y)2 = (x + y)2 - 4xy = b2 - 16bd + 24d2 = (b - 8d)2 - 40d2 .
Let b - 8d = p2 + 10q2 and d = pq. Then
x - y =

 

p4 - 20p2q2 + 100q4
 
= p2 - 10q2 .
Solving this, we find that
(a, b, c; x, y) = (3pq, p2 + 8pq + 10q2, 2p2 + 13pq + 20q2;2p2 + 12pq + 10q2, p2 + 12pq + 20q2) .
Some numerical examples are
(a, b, c; p, q) = (3, 19, 35;24, 33), (6, 30, 54; 42, 48), (6, 57, 108; 66, 105) .
Any common divisor of a and b must divide 3pq and p2 + 10q2, and so must divide both p and q. [Justify this; you need to be a little careful.] We can get the solutions we want by arranging that the p and q are coprime.

Solution 3. [F. Barekat] Let m = a + b + c = x + y and n = a3 + b3 + c3 = x3 + y3. Then

3xy = m2 -  n

m
=  m3 - n

m
and
(x - y)2
=  x3 + y3

x + y
- xy =  4n - m3

3n
=  4(a3 + b3 + c3) - (a + b + c)3

3(a + b + c)
= (c - a - b)2 -  4ab(a + b)

a + b + c
 .
Select a, b, c so that
 4ab(a + b)

a + b + c
= 2(c - a - b) - 1 .
so that x - y = c - a - b - 1. Then we can solve for rational values of x and y. If we can do this x + y = a + b + c and x - y = c - a - b - 1. Note that, these two numbers have different parity, so we will obtain fractional values of x and y, whose denominators are 2. However, the equations to be solved are homogeneous, so we can get integral solutions by doubling: (2a, 2b, 2c; 2x, 2y).

Let c = u(a + b). Then

4ab = 2(u-1)(u+1)(a + b) - (u + 1) .
Let u = 4v + 3, Then we get
ab = 4(v + 1)(2v + 1)(a + b) - 4(v + 1) ,
from which
[a - 4(v + 1)(2v + 1)][b - 4(v + 1)(2v + 1)] = (v + 1)[16(v + 1)(2v + 1)2 - 1] .
We use various factorizations of the right side and this equation to determine integer values of a and b, from which the remaining variables c, x and y can be determined.

For example, v = 0 yields the equation (a - 4)(b - 4) = 15 from which we get the possibilities

(a, b, c) = (5, 19, 72), (7, 9, 48) .
Doubling to clear fractions, yields the solutions
(a, b, c; x, y) = (10, 38, 144; 49, 143), (14, 18, 96; 33, 95) .
Additional solutions come from v = 1:
(a, b, c; x, y) = (76, 130, 1442; 207, 1441),(50, 1196, 8722; 1247, 8721) .

Solution 4. [D. Rhee] An infinite set of solutions is given by the formula

(a, b, c; x, y)
= (2, n2 + 3n, n2 + 5n + 4; n2 + 4n + 2, n2 + 4n + 4)
= (2, n(n + 3), (n+1)(n+4); (n+2)2 - 2, (n+2)2) .
Examples are (a, b, c; x, y) = (2, 4, 10; 7, 9),(2, 10, 18; 14, 16), (2, 18, 28; 23, 25).

Comment. M. Fatehi gave the solution

(a, b, c; x, y) = (5, 6, 22; 12, 21) .



343.
A sequence { an } of integers is defined by
a0 = 0 ,   a1 = 1 ,   an = 2an-1 + an-2
for n > 1. Prove that, for each nonnegative integer k, 2k divides an if and only if 2k divides n.
Solution 1. Let m and n be two nonnegative integers. Then am+n = aman+1 + am-1an = am+1an + aman-1. This can be checked for small values of m and n and established by induction. The induction step is
am+n+1
= 2am+n + am+n-1 = 2(aman+1 + am-1an) +(aman + am-1an-1
= am (2an+1 + an) + am-1(2an + an-1) = am an+2 + am-1an+1 .
In particular, for each integer n,
a2n = an (an-1 + an+1) .

It is straightforward to show by induction from the recursion that an is odd whenever n is odd and even whenever n is even. Suppose now that n is even. Then an+1 = 2an + an-1 an-1 a1 = 1 (mod 4), so that an-1 + an+1 = 2bn for some odd number bn. Hence a2n = 2anbn. For k = 0, we have that 2k |an if and only if 2k |n. Suppose that this has been established for k = r.

Suppose that n = 2r+1m for some integer m. Then n/2 is divisible by 2r, and therefore so is an/2. Hence an = 2an/2bn/2 is divisible by 2r+1. On the other hand, suppose that n is not divisible by 2r+1. If n is not divisible by 2r, then an is not so divisible by the induction hypothesis, and so not divisible by 2r+1. On the other hand, if n = 2rc, with c odd, then an is divisible by 2r. But n/2 = 2r-1c, so an/2 is not divisible by 2r. Hence an = 2an/2bn/2 is not divisible by 2r+1. The result follows.

Solution 2. For convenience, imagine that the sequence is continued backwards using the recursion an-2 = an - 2an-1 for all integer values of the index n. We have for every integer n, an+1 = 2an + an-1 2an+1 = 4an + 2an-1 an+2 - an = 4an + an - an-2 an+2 = 6an - an-2. Suppose, for some positive integer r, we have established that, for every integer n,

an + 2r = br an - an-2r
where br 2 (mod 4). This is true for r = 1 with b1 = 6. Then
br an + 2r = br2 an - br an - 2r

an + 2r+1 + an = br2 an - (an + an-2r+1)

an + 2r = br+1an - an - 2r+1 ,
where br+1 = b22 - 2 2 (mod 4).

Observe that, since an+1 an-1 (mod 2) and a0 = 0, a1 = 1, an is even if and only if n is even. When n is even, then an+2 an-2 (mod 4), so that an is divisible by 4 if and only if n is.

Let m 2 be a positive integer. Suppose that it has been established for 1 s m, that 2s divides an if and only if 2s divides n. Then 2s+1 will divide an only if n = 2s p for some integer p. Now

a2s = bs-1a2s-1 - a0 = bs-1a2s-1 ;
since 2 || bs-1 and 2s-1 || a2s-1, it follows that 2s || a2s. (The notation 2k || q means that 2k is the highest power of 2 that divides q.) Thus 2s+1 does not divide 2s.

Suppose that it has been established for 1 i p that when n = 2s i, 2s+1 |n if and only if p is even. We have that

a2s(p+1) = bs 2sp - a2s(p-1) .
If p is even, then bs a2sp 0 (mod 2s+1), so that a2s(p+1) a2s(p-1) 2s (mod 2s+1), and a2s(p+1) is not a multiple of 2s+1. If p is odd, then each term on the right side of the foregoing equation is a multiple of 2s+1, and therefore so is a2s(p+1). The desired result follows by induction.

Solution 3. The characteristic equation for the recursion is t2 - 2t - 1 = 0, with roots t = 1 2. Solving the recursion, we find that

an
=  1

2 2
[(1 + 2)n - (1 - 2)n]
=  1

2



k=0 

n
2k + 1

2k 2
=

k=0 

n
2k+1

2k = n +

k=1 

n
2k + 1

2k
= n +

k=1 
 n

2k+1

n-1
2k

2k .
(We use the convention that (i || j) = 0 when i < j. Suppose that n = 2rs where r is a nonnegative integer and s is odd. Since the odd number 2k + 1 divides n ((n-1) || 2k) = 2r s ((n-1) || 2k), 2k + 1 must divide s ((n-1) || 2k), so that 2s must divide n ((n-1) || 2k) = (n || (2k+1)). Therefore, 2s+1 must divide each term (n || (2k+1)) for k 1. Therefore an n (mod 2s) and the desired result follows.

Comment. Y. Zhao obtained by induction that





an+1
an
an
an-1




=



2
1
1
0




n



 
from which the matrix equation




a2n+1
a2n
a2n
a2n-1




=



an+1
an
an
a2n-1




2



 
yields the equation a2n = an (an-1 + an+1.



344.
A function f defined on the positive integers is given by
f(1) = 1 ,   f(3) = 3 ,   f(2n) = f(n) ,

f(4n + 1)
= 2f(2n + 1) - f(n)
f(4n + 3)
= 3f(2n + 1) - 2f(n) ,
for each positive integer n. Determine, with proof, the number of positive integers no exceeding 2004 for which f(n) = n.
Solution. Let g(n) be defined for positive integer n by writing n to base 2 and reversing the digits. Specifically, if n = k=0r ak 2r with each ak equal to 0 or 1 and ar = 1, then g(n) = k=0n ar-k2k. We prove that g(n) has the properties ascribed to f(n). It is checked that g(1) = g(2) = g(3) = 1. Let n = ar2r + ar-12r-1 + + a12 + a0. Then 2n = ar2r+1 + + a02 + 0 and g(2n) = 0·2r+1 + a0 2r + + ar-12 + ar = g(n).

Since 4n + 1 = ar2r+2 + ar-12r+1 + + a123 + a02+ 0·2 + 1,

g(n)
+ g(4n+1) = (a02r + a12r-1 + + ar-12 + ar) +(2r+2 + a02r + a12r-1 + + ar-12 + ar)
= 2r+2 + a02r+1 + a1rr + + ar-122 + ar2 = 2(2r+1 + a02r + a12r-1 + + ar-12 + ar
= 2g(a2 2r+1 + a0 2r + a1 2r-1 + + ar-1 2+ ar) = 2g(2n+1) .
(This uses the fact that a2i + a2i = a2i+1.)

Since 4n + 3 = ar2r+2 + ar-12r+1 + + a123 + a02+ 1·2 + 1,

2g(n)
+ g(4n+3)
= (a02r+1 + a1 2r + a2 2r-1 + + ar-122 + ar 2)
      + (2r+2 + 2r+1 + a02r + a12r-1 + + ar-12 + ar)
= (2r+2 + a02r+1 + a12r + + ar2) + (2r+1 + a02r + a12r-1 + + ar)
= 2g(2n+1) + g(2n+1) = 3g(2n + 1) .

We show by induction that f(n) = g(n) for every positive integer n. This is true for 1 n 4. Suppose it holds for 1 n 4m. Then

f(4m + 1) = 2f(2m + 1) - f(m) = 2g(2m + 1) - g(m) = g(4m + 1) ;

f(4m + 2) = f(2m + 1) = g(2m + 1) = g(4m + 2) ;

f(4m + 3) = 3f(2m + 1) - 2f(m) = 3g(2m + 1) - 2g(m) = g(4m + 3) ;

f(4m + 4) = f(2m + 2) = g(2m + 2) = f(4m + 4) .
Thus we have a description of f(n).

For f(n) = n, it is necessary and sufficient that n is a palindrome when written to base 2. We need to find the number of palindromes between 1 and 2004 = (11111010100)2 inclusive. The number of (2r-1)- and 2r-digit palindromes is each 2r-1 as the first and last digits must be 1 and there are r-1 other matching pairs of digits or central digits that can be set to either 0 or 1. The number of palindromes up to 211 - 1 = 2047 is 2(1 + 2 + 4 + 8 + 16) + 32 = 94. The only palindromes between 2004 and 2048 are (11111011111)2 and (11111111111)2, and these should not be counted. Therefore, there are exactly 92 palindromes, and therefor 92 solutions of f(n) = n between 1 and 2004, inclusive.



345.
Let C be a cube with edges of length 2. Construct a solid figure with fourteen faces by cutting off all eight corners of C, keeping the new faces perpendicular to the diagonals of the cuhe and keeping the newly formed faces identical. If the faces so formed all have the same area, determine the common area of the faces.
Solution 1. In the situation where the cuts pass through the midpoints of the edges, yielding a cube-octahedron with six square and eight equilateral-triangular sides, we find that the square faces have area 2 and the triangular faces have area (3/4)(2) = 6/4 < 2. Moving the cuts closer to the vertices yields triangular faces of area less than 2 and octahedral faces of area greater than 2. Thus, for equal areas of the corner and face figures, the cuts must be made a a distance exceeding 1 from each vertex.

The corner faces of the final solid are hexagons formed by large equilateral triangles with smaller equilateral triangles clipped off each vertex; the other faces are squares (diamonds) in the middle of the faces of the cube. Let the square faces have side length x. The vertices of this face are distant 1 - (x/2) from the edge of the cube, so that smaller equilateral triangles of side 2(1 - (x/2)) = 2 - x are clipped off from a larger equilateral triangle of side 2(2 - x) + x = 22 - x. The areas of the hexagonal faces of the solid figure are each

 3

4
[(22 - x)2 - 3(2 - x)2] =  3

2
+  x6

2
-  x23

2
 .
For equality, we need
x2 =  3

2
[1 + x2 - x2] ,
or
(2 + 3)x2 - x6 - 3 = 0 .
Hence
x =
6 +


83 + 18

2(2 + 3)
and the common area is
x2 =
6 + 23 +


27 + 123

7 + 43
= (6 + 23 +

 

27 + 123
 
)(7 - 43) .

Solution 2. Let the cut be made distant u from a vartex. As in Solution 1, we argue that 1 < u < 2. Then the edge of the square face of the final solid is distant u/2 from the vertex of the cube and 2(1 - (u/2)) from the centre of the face. Thus, the square face has side length 2(2 - u) and area 8 - 8u + 2u2.

The hexagonal face of the solid consists of an equilateral triangle of side 2u with three equilateral triangles of side 2(u - 1) clipped off. Its area is (3/2)[-2u2 + 6u - 3. For equality of area of all the faces, we require that

2(8 - 8u + 2u2) = 3(-2u2 + 6u - 3)
or
2(2 + 3)u2 - 2(8 + 33)u + (16 + 33) = 0 .
Solving this equation and taking the root less than 2 yields that
u =
(8 + 33) -


9 + 43

2(2 + 3)
 ,
whence
2 - u =
3 +


9 + 43

2(2 + 3)
 .
Thus, the common area is
2(2 - u)2 =
6 + 23 +


27 + 123

7 + 43
= (6 + 23 +

 

27 + 123
 
)(7 -43) .

© Société mathématique du Canada, 2014 : http://www.smc.math.ca/