CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location: 
       
Solutions

We begin with an old problem that no one managed to solve.

90.
Let m be a positive integer, and let f(m) be the smallest value of n for which the following statement is true:
given any set of n integers, it is always possible to find a subset of m integers whose sum is divisible by m
Determine f(m).

Solution. [N. Sato] The value of f(m) is 2m - 1. The set of 2m - 2 numbers consisting of m - 1 zeros and m - 1 ones does not satisfy the property; from this we can see that n cannot be less than 2m - 1.

We first establish that, if f(u) = 2u - 1 and f(v) = 2v - 1, then f(uv) = 2uv - 1. Suppose that 2uv - 1 numbers are given. Select any 2u - 1 at random. By hypothesis, there exists a u-subset whose sum is divisible by u; remove these u elements. Continue removing u-subsets in this manner until there are fewer than u numbers remaining. Since 2uv - 1 = (2v - 1)u + (u - 1), we will have 2v - 1 sets of u numbers summing to a multiple of u. For 1 i 2v - 1, let uai be the sum of the ith of these 2v - 1 sets. We can choose exactly v of the ai whose sum is divisible by v. The v u-sets corresponding to these form the desired uv elements whose sum is divisible by uv. Thus, if we can show that f(p) = 2p - 1 for each prime p, we can use the fact that each number is a product of primes to show that f(m) = 2m - 1 for each positive integer m.

Let x1, x2, , x2p-1 be 2p-1 integers. Wolog, we can assume that the xi have been reduced to their least non-negative residue modulo p and that they are in increasing order. For 1 i p-1, let yi = xp+i - xi; we have that yi 0. If yi = 0 for some i, then xi+1 = = xp+i, in which case xi+1 + + xp+i is a multiple of p and we have achieved our goal. Henceforth, assume that yi > 0 for all i

Let s = x1 + x2 + + xp. Replacing xi by xp+i in this sum is equivalent to adding yi. We wish to show that there is a set of the yi whose sum is congruent to -s modulo p; this would indicate which of the first p xi to replace to get a sum which is a multiple of p.

Suppose that A0 = { 0 }, and, for k 1, that Ak is the set of distinct numbers i with 0 i p-1 which either lie in Ak-1 or are congruent to a + yk for some a in Ak-1. Note that the elements of each Ak is equal to 0 or congruent (modulo p) to a sum of distinct yi. We claim that the number of elements in Ak must increase by at least one for every k until Ak is equal to { 0, 1, , p-1 }.

Suppose that going from Aj-1 to Aj yields no new elements. Since 0 Aj-1, yj Aj, which means that yj Aj-1. Then 2yj = yj + yj Aj = Aj-1, 3yj = 2yj + yj Aj = Aj-1, and so on. Thus, all multiples of yj (modulo p) are in Aj-1. As p is prime, we find that Aj-1 must contain { 0, 1, , p-1 }. We deduce that some sum of the yi is congruent to -s modulo p and obtain the desired result.



145.
Let ABC be a right triangle with A = 90. Let P be a point on the hypotenuse BC, and let Q and R be the respective feet of the perpendiculars from P to AC and AB. For what position of P is the length of QR minimum?
Solution. PQAR, being a quadrilateral with right angles at A, Q and R, is a rectangle. Therefore, its diagonals QR and AP are equal. The length of QR is minimized when the length of AP is minimized, and this occurs when P is the foot of the perpendicular from A to BC.

Comment. P must be chosen so that PB:PC = AB2:AC2.



146.
Suppose that ABC is an equilateral triangle. Let P and Q be the respective midpoint of AB and AC, and let U and V be points on the side BC with 4BU = 4VC = BC and 2UV = BC. Suppose that PV is joined and that W is the foot of the perpendicular from U to PV and that Z is the foot of the perpendicular from Q to PV.
Explain how that four polygons APZQ, BUWP, CQZV and UVW can be rearranged to form a rectangle. Is this rectangle a square?
Solution. Consider a 180 rotation about Q so that C falls on A, Z falls on Z1 and V falls on V1. The quadrilateral QZVC goes to QZ1V1A, ZQZ1 is a line and QAV1 = 60. Similarly, a 180 rotation about P takes quadrilateral PBUW to PAU1W1 with WPW1 a line and U1AP = 60. Since U1AP = PAQ = QAV1 = 60, U1AV1 is a line and


U1V1 = U1A + AV1 = UB + CV = 1
2
BC = UV .
Translate U and V to fall on U1 and V1 respectively; let W fall on W2. Since


W1U1W2 = W1U1A + W2U1A = WUB + WUV = 180 ,


W2V1Z1 = W2V1A + AV1Z1 = WVU + CVZ = 180 ,
and


W2 = W1 = Z1 = WZQ = 90 ,
it follows that Z1W2W1Z is a rectangle composed of isometric images of APZQ, BUWP, CQZV and UVW.

Since PU and QV are both parallel to the median from A to BC, we have that PQVU is a rectangle for which PU < PB = PQ. Thus, PQVU is not a square and so its diagonals PV and QU do not intersect at right angles. It follows that W and Z do not lie on QU and so must be distinct.

Since PZQ and VWU are right triangles with QPZ = UVW and PQ = VU, they must be congruent, so that PZ = VW, PW = ZV and UW = QZ. Since


W1W2
= W1U1 + U1W2 = WU + UW = WU + QZ
< UQ = PV = PZ + ZV = PZ + PW = PZ + PW1 = W1Z ,
the adjacent sides of Z1W2W1Z are unequal, and so the rectangle is not square.

Comment. The inequality of the adjacent sides of the rectangle can be obtained also by making measurements. Take 4 as the length of a side of triangle ABC. Then


|PU | = 3 ,    |PQ | = 2 ,   |QU | = |PV | = 7 .
Since the triangles PUW and PVU are similar, UW : PU = VU : PV, whence |UW | = 2[21]/7. Thus, |W1 W2 | = 4[21]/7 7 = |W1Z |.

One can also use the fact that the areas of the triangle and rectangle are equal. The area of the triangle is 43. It just needs to be verified that one of the sides of the rectangle is not equal to the square root of this.



147.
Let a > 0 and let n be a positive integer. Determine the maximum value of


x1 x2 xn
(1 + x1)(x1 + x2) (xn-1 + xn)(xn + an+1)
subject to the constraint that x1, x2, , xn > 0.
Solution. Let u0 = x1, ui = xi+1/xi for 1 i n-1 and un = an+1/xn. Observe that u0 u1 un = an+1. The quantity in the problem is the reciprocal of


(1 + u0)
(1 + u1)(1 + u2) (1 + un)
= 1 +
ui +
uiuj + +
ui1ui2 uik + + u0u1 un .
For k = 1, 2, , n, the sum ui1ui2 uik adds together all the ((n+1) || k) k-fold products of the ui; the product of all the terms in this sum is equal to an+1 raised to the power (n || (k-1)), namely, to a raised to the power k ((n+1) || k). By the arithmetic-geometric means inequality



ui1ui2 uik

n+1
k


ak .
Hence


(1 + u0)(1 + u1) (1 + un) 1 + (n+1)a ++

n+1
k


ak + an+1 = (1 + a)n+1 ,
with equality if and only if u0 = u1 = = un = a. If follows from this that the quantity in the problem has maximum value of (1 + a)-(n+1), with equality if and only if xi = ai for 1 i n.

Comment. Some of you tried the following strategy. If any two of the ui were unequal, they showed that a larger value could be obtained for the given expression by replacing each of these by another value. They then deduced that the maximum occurred when all the ui were equal. There is a subtle difficulty here. What has really been proved is that, if there is a maximum, it can occur only when the ui are equal. However, it begs the question of the existence of a maximum. To appreciate the point, consider the following argument that 1 is the largest postive integer. We note that, given any integer n exceeding 1, we can find another integer that exceeds n, namely n2. Thus, no integer exceeding 1 can be the largest positive integer. Therefore, 1 itself must be the largest.

Some of you tried a similar approach with the xi, and showed that for a maximum, one must have all the xi equal to 1. However, they neglected to build in the relationship between xn and an+1, which of course cannot be equal if all the xi are 1 and a 1. This leaves open the possibility of making the given expression larger by bettering the relationship between the xi and a and possibly allowing inequalities of the variables.



148.
For a given prime number p, find the number of distinct sequences of natural numbers (positive integers) { a0, a1, , an } satisfying, for each positive integer n, the equation


a0
a1
+ a0
a2
+ + a0
an
+ p
an+1
= 1 .
Solution. For n 3 we have that


1 =
a0
a1
+ + a0
a2
++ a0
an-2
+ p
an-1
= a0
a1
+ a0
a2
+ + a0
an-1
+ p
an
whence


p
an-1
= a0
an-1
+ p
an
 ,
so that


an = pan-1
p - a0
 .
Thus, for n 2, we have that


an = pn-2 a2
(p - a0)n-2
 .
Since 1 p - a0 p - 1, p - a0 and p are coprime. It follows that, either p - a0 must divide a2 to an arbitrarily high power (impossible!) or p - a0 = 1.

Therefore, a0 = p - 1 and an = pn-2a2 for n 2. Thus, once a1 and a2 are selected, then the rest of the sequence { an } is determined. The remaining condition that has to be satisfied is


1 = a0
a1
+ p
a2
= p-1
a1
+ p
a2
 .
This is equivalent to


(p - 1)a2 + pa1 = a1 a2 ,
or


[a1 - (p-1)][a2 - p] = p(p-1) .
The factors a1 - (p-1) and a2 - p must be both negative or both positive. The former case is excluded by the fact that (p-1) - a1 and p - a2 are respectively less than p-1 and p. Hence, each choice of the pair (a1, a2) corresponds to a choice of a pair of positive divisors of p(p-1). There are d(p(p-1)) = 2d(p-1) such choices, where d(n) is the number of positive divisors of the positive integer n.

Comment. When p = 5, for example, the possibilities for (a1, a2) are (5, 25), (6, 15), (8, 10), (9, 9), (14, 7), (24, 6). In general, particular choices of sequences that work are


{p-1, p, p2, p3, }


{p-1, 2p-1, 2p-1, p(2p-1), }


{p-1, p2 - 1, p + 1, p(p+1), } .

A variant on the argument showing that the an from some point on constituted a geometric progression started with the relation p(an - an-1) = a0an for n 3, whence


an-1
an
= 1 - a0
p
 .
Thus, for n 3, an+1an-1 = an2, which forces { a2, a3, , } to be a geometric progession. The common ratio must be a positive integer r for which r = p/(p-a0). This forces p - a0 to be equal to 1.

Quite a few solvers lost points because of poor book-keeping; they did not identify the correct place at which the geometric progression began. It is often a good idea to write out the first few equations of a general relation explicitly in order to avoid this type of confusion. You must learn to pay attention to details and check work carefully; otherwise, you may find yourself settling for a score on a competition less than you really deserve on the basis of ability.



149.
Consider a cube concentric with a parallelepiped (rectangular box) with sides a < b < c and faces parallel to that of the cube. Find the side length of the cube for which the difference between the volume of the union and the volume of the intersection of the cube and parallelepiped is minimum.
Solution. Let x be the length of the side of the cube and let f(x) be the difference between the value of the union and the volume of the intersection of the two solids. Then


f(x) =





abc - x3
(0 x < a)
abc + (x - a)x2 - ax2 = abc + x3 - 2ax2
(a x < b)
x3 + ab(c - x) - abx = abc + x3 - 2abx
(b x < c)
x3 - abc
(c x)
The function decreases for 0 x a and increases for x c. For b x c,


f(x) - f(b)
= x3 - 2abx - b3 + 2ab2
= (x - b)[x2 + bx + b2 - 2ab]
= (x - b)[(x2 - ab) + b(x - a) + b2] 0 ,
so that f(x) f(b). Hence, the minimum value of f(x) must be assumed when a x b.

For a x b, f(x) = 3x2 - 4ax = x[3x - 4a], so that f(x) increases for x 4a/3 and decreases for x 4a/3. When b 4a/3, then f(x) is decreasing on the closed interval [a, b] and assumes its minimum for x = b. If b > 4a/3 > a, then f(x) increases on [4a/3, b] and so achieves its minimum when x = 4a/3. Hence, the function f(x) is minimized when x = min (b, 4a/3).



150.
The area of the bases of a truncated pyramid are equal to S1 and S2 and the total area of the lateral surface is S. Prove that, if there is a plane parallel to each of the bases that partitions the truncated pyramid into two truncated pyramids within each of which a sphere can be inscribed, then


S = (   __
S1
 
+   __
S2
 
)([4 ]S1 +[4 ]S2)2 .
Solution 1. Let M1 be the larger base of the truncated pyramid with area S1, and M2 the smaller base with area S2. Let P1 be the entire pyramid with base M1 of which the truncated pyramid is a part. Let M0 be the base parallel to M1 and M2 described in the problem, and let its area be S0. Let P0 be the pyramid with base M0 and P2 the pyramid with base M2.

The inscribed sphere bounded by M0 and M1 is determined by the condition that it touches M1 and the lateral faces of the pyramid; thus, it is the inscribed sphere of the pyramid P1 with base M1; let its radius be R1. The inscribed sphere bounded by M2 and M0 is the inscribed sphere of the pyramid P0 with base M0; let its radius be R0. Finally, let the inscribed sphere of the pyramid with base M2 have radius R2.

Suppose Q2 is the lateral area of pyramid P2 and Q1 the lateral area of pyramid P1. Thus, S = Q1 - Q2.

There is a dilation with factor R0/R1 that takes pyramid P1 to P0; since it takes the inscribed sphere of P1 to that of P0, it takes the base M1 to M0 and the base M0 to M2. Hence, this dilation takes P0 to P2. The dilation composed with itself takes P1 to P2. Therefore


R0
R1
= R2
R0
         and            Q2
Q1
= S2
S1
= R22
R12
 .

Consider the volume of P2. Since P2 is the union of pyramids of height R2 and with bases the lateral faces of P2 and M2, its volume is (1/3)R2(Q2 + S2). However, we can find the volume of P2 another way. P2 can be realized as the union of pyramids whose bases are its lateral faces and whose apexes are the centre of the inscribed sphere with radius R0 with the removal of the pyramid of base M2 and apex at the centre of the same sphere. Thus, the volume is also equal to (1/3)R0(Q2 - S2).

Hence


Q2 - S2
Q2 + S2
= R2
R0
= R2
  ____
R1R2
=
  __
R2

  __
R1
= [4 ]S2
[4 ]S1


Q2([4 ]S1 - [4 ]S2) = S2 ([4 ]S1 + [4 ]S2) ,
so that


S
= Q1 - Q2 = Q2
S2
(S1 - S2)
=

[4 ]S1 + [4 ]S2
[4 ]S1 - [4 ]S2


[   __
S1
 
-   __
S2
 
][   __
S1
 
+   __
S2
 
]
= ( [4 ]S1 + [4 ]S2 )2 (   __
S1
 
+   __
S2
 
) .

Solution 2. [S. En Lu] Consider an arbitrary truncated pyramid with bases A1 and A2 of respective areas s1 and s2, in which a sphere G of centre O is inscribed. Let the lateral area be s. Suppose that C is a lateral face and that G touches A1, A2 and C in the respective points P1, P2 and Q.

C is a trapezoid with sides of lengths a1 and a2 incident with the respective bases A1 and A2; let h1 and h2 be the respective lengths of the altitudes of triangles with apexes P1 and P2 and bases bordering on C. By similarity (of A1 and A2),


h1
h2
= a1
a2
=   
 


s1
s2
 
 .
The plane that contains these altitudes passes through P1P2 (a diameter of G) as well as Q, the point on C nearest to the centre of G. Since the height of C is a1 + a2 [why?], its area is


1
2
(a1 + a2)(h1 + h2)
= 1
2
[ a1h1 + a2h2 + a1h2 + a2h1 ]
= 1
2
[ a1h1 + a2h2 + 2   ________
a1a2h1h2
 
]
= 1
2
[ a1h1 + a2h2 + 2a2h2

 

s1/s2
 
]  .
Adding the corresponding equations over all the lateral faces C yields


s = s1 + s2 +

 

s1 s2
 
= (

 

s1
 
+

 

s2
 
)2 .

With S0 defined as in Solution 1, we have that S1 / S0 = S0 / S2, so that S0 = [(S1S2)]. Using the results of the first paragraph applied to the truncated pyramids of bases (S2, S0) and (S0, S1), we obtain that


S
= (   __
S1
 
+   __
S0
 
)2+ (   __
S0
 
+   __
S1
 
)2
= (   __
S1
 
+ [4 ]S1S2)2 +([4 ]S1S2 +   __
S2
 
)2
= (   __
S1
 
+   __
S2
 
)([4 ]S1 +[4 ]S2)2   .

© Canadian Mathematical Society, 2014 : https://cms.math.ca/