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
usubset whose sum is divisible by u; remove these u elements.
Continue removing usubsets 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 ua_{i} be the sum of the ith of these
2v  1 sets. We can choose exactly v of the a_{i} whose sum is
divisible by v. The v usets 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 x_{1}, x_{2}, ¼, x_{2p1} be 2p1 integers.
Wolog, we can assume that the x_{i} have been reduced to their least
nonnegative residue modulo p and that they are in increasing
order. For 1 £ i £ p1, let y_{i} = x_{p+i}  x_{i};
we have that y_{i} ³ 0. If y_{i} = 0 for some i, then
x_{i+1} = ¼ = x_{p+i}, in which case
x_{i+1} + ¼+ x_{p+i} is a multiple of p and we have achieved
our goal. Henceforth, assume that y_{i} > 0 for all i
Let s = x_{1} + x_{2} + ¼+ x_{p}. Replacing x_{i} by x_{p+i} in this
sum is equivalent to adding y_{i}. We wish to show that there is
a set of the y_{i} whose sum is congruent to s modulo p; this
would indicate which of the first p x_{i} to replace to get a
sum which is a multiple of p.
Suppose that A_{0} = { 0 }, and, for k ³ 1, that
A_{k} is the set of distinct numbers i with 0 £ i £ p1
which either lie in A_{k1} or are congruent to a + y_{k} for
some a in A_{k1}. Note that the elements of each A_{k} is
equal to 0 or congruent (modulo p) to a sum of distinct y_{i}.
We claim that the number of elements in
A_{k} must increase by at least one for every k until A_{k}
is equal to { 0, 1, ¼, p1 }.
Suppose that going from A_{j1} to A_{j} yields
no new elements. Since 0 Î A_{j1}, y_{j} Î A_{j}, which means that
y_{j} Î A_{j1}. Then 2y_{j} = y_{j} + y_{j} Î A_{j} = A_{j1},
3y_{j} = 2y_{j} + y_{j} Î A_{j} = A_{j1}, and so on. Thus, all multiples of
y_{j} (modulo p) are in A_{j1}. As p is prime, we find that
A_{j1} must contain { 0, 1, ¼, p1 }. We deduce that some
sum of the y_{i} 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 = AB^{2}:AC^{2}.

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 Z
_{1} and V falls on V
_{1}. The
quadrilateral QZVC goes to QZ
_{1}V
_{1}A, ZQZ
_{1} is a line and
ÐQAV
_{1} = 60
^{°}. Similarly, a 180
^{°} rotation
about P takes quadrilateral PBUW to PAU
_{1}W
_{1} with WPW
_{1} a
line and
ÐU
_{1}AP = 60
^{°}. Since
ÐU
_{1}AP =
ÐPAQ =
ÐQAV
_{1} = 60
^{°}, U
_{1}AV
_{1} is a line and
U_{1}V_{1} = U_{1}A + AV_{1} = UB + CV = 
1 2

BC = UV . 

Translate U and V to fall on U
_{1} and V
_{1} respectively;
let W fall on W
_{2}. Since
ÐW_{1}U_{1}W_{2} = ÐW_{1}U_{1}A + ÐW_{2}U_{1}A = ÐWUB + ÐWUV = 180^{°} , 

ÐW_{2}V_{1}Z_{1} = ÐW_{2}V_{1}A + ÐAV_{1}Z_{1} = ÐWVU + ÐCVZ = 180^{°} , 

and
ÐW_{2} = ÐW_{1} = ÐZ_{1} = ÐWZQ = 90^{°} , 

it follows that Z
_{1}W
_{2}W
_{1}Z 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

= W_{1}U_{1} + U_{1}W_{2} = WU + UW = WU + QZ 
 
< UQ = PV = PZ + ZV = PZ + PW = PZ + PW_{1} = W_{1}Z , 


the adjacent sides of Z
_{1}W
_{2}W
_{1}Z 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,
W
_{1} W
_{2}  = 4
Ö[21]/7
¹ Ö7 =
W
_{1}Z
.
One can also use the fact that the areas of the triangle and rectangle
are equal. The area of the triangle is 4Ö3. 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

x_{1} x_{2} ¼x_{n} (1 + x_{1})(x_{1} + x_{2}) ¼(x_{n1} + x_{n})(x_{n} + a^{n+1})



subject to the constraint that x_{1}, x_{2}, ¼, x_{n} > 0.
Solution. Let u
_{0} = x
_{1}, u
_{i} = x
_{i+1}/x
_{i} for
1
£ i
£ n
1 and u
_{n} = a
^{n+1}/x
_{n}. Observe that
u
_{0} u
_{1} ¼u
_{n} = a
^{n+1}. The quantity in the problem
is the reciprocal of

(1 + u_{1})(1 + u_{2}) ¼(1 + u_{n}) 
 
= 1 + 
å
 u_{i} + 
å
 u_{i}u_{j} + ¼+ 
å
 u_{i1}u_{i2} ¼u_{ik} + ¼+ u_{0}u_{1} ¼u_{n} . 


For k = 1, 2,
¼, n, the sum
åu
_{i1}u
_{i2} ¼u
_{ik}
adds together all the ((n+1)  k) k
fold products of the
u
_{i}; the product of all the terms in this sum is equal to
a
^{n+1} raised to the power (n  (k
1)), namely, to
a raised to the power k ((n+1)  k). By the arithmeticgeometric
means inequality

å
 u_{i1}u_{i2} ¼u_{ik} ³ 
æ ç
è

n+1
k

ö ÷
ø

a^{k} . 

Hence
(1 + u_{0})(1 + u_{1}) ¼(1 + u_{n}) ³ 1 + (n+1)a +¼+ 
æ ç
è

n+1
k

ö ÷
ø

a^{k} + ¼a^{n+1} = (1 + a)^{n+1} , 

with equality if and only if u
_{0} = u
_{1} =
¼ = u
_{n} = 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
x
_{i} = a
_{i} for 1
£ i
£ n.
Comment. Some of you tried the following strategy. If any two
of the u_{i} 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 u_{i} 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 u_{i} 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 n^{2}. 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 x_{i}, and showed that
for a maximum, one must have all the x_{i} equal to 1. However, they
neglected to build in the relationship between x_{n} and a_{n+1},
which of course cannot be equal if all the x_{i} are 1 and a ¹ 1.
This leaves open the possibility of making the given expression larger
by bettering the relationship between the x_{i} 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)
{ a_{0}, a_{1}, ¼, a_{n} ¼} satisfying, for each
positive integer n, the equation

a_{0} a_{1}

+ 
a_{0} a_{2}

+ ¼+ 
a_{0} a_{n}

+ 
p a_{n+1}

= 1 . 

Solution. For n
³ 3 we have that


a_{0} a_{1}

+ ¼+ 
a_{0} a_{2}

+¼+ 
a_{0} a_{n2}

+ 
p a_{n1}


 
= 
a_{0} a_{1}

+ 
a_{0} a_{2}

+ ¼+ 
a_{0} a_{n1}

+ 
p a_{n}




whence

p a_{n1}

= 
a_{0} a_{n1}

+ 
p a_{n}

, 

so that
a_{n} = 
pa_{n1} p  a_{0}

. 

Thus, for n
³ 2, we have that
a_{n} = 
p^{n2} a_{2} (p  a_{0})^{n2}

. 

Since 1
£ p
 a
_{0} £ p
 1, p
 a
_{0} and p are coprime.
It follows that, either p
 a
_{0} must divide a
_{2} to an arbitrarily
high power (impossible!) or p
 a
_{0} = 1.
Therefore, a_{0} = p  1 and a_{n} = p^{n2}a_{2} for n ³ 2.
Thus, once a_{1} and a_{2} are selected, then the rest of the
sequence { a_{n} } is determined. The remaining condition that
has to be satisfied is
1 = 
a_{0} a_{1}

+ 
p a_{2}

= 
p1 a_{1}

+ 
p a_{2}

. 

This is equivalent to
(p  1)a_{2} + pa_{1} = a_{1} a_{2} , 

or
[a_{1}  (p1)][a_{2}  p] = p(p1) . 

The factors a
_{1}  (p
1) and a
_{2}  p must be both negative or
both positive. The former case is excluded by the fact that
(p
1)
 a
_{1} and p
 a
_{2} are respectively less than p
1 and
p. Hence, each choice of the pair (a
_{1}, a
_{2}) 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
(a_{1}, a_{2}) are (5, 25), (6, 15), (8, 10), (9, 9),
(14, 7), (24, 6). In general, particular choices of
sequences that work are
{p1, p, p^{2}, p^{3}, ¼} 

{p1, 2p1, 2p1, p(2p1), ¼} 

{p1, p^{2}  1, p + 1, p(p+1), ¼} . 

A variant on the argument showing that the a_{n} from some point
on constituted a geometric progression started with the relation
p(a_{n}  a_{n1}) = a_{0}a_{n} for n ³ 3, whence

a_{n1} a_{n}

= 1  
a_{0} p

. 

Thus, for n
³ 3, a
_{n+1}a
_{n1} = a
_{n}^{2}, which forces
{ a
_{2}, a
_{3},
¼, } to be a geometric progession. The
common ratio must be a positive integer r for which
r = p/(p
a
_{0}). This forces p
 a
_{0} to be equal to 1.
Quite a few solvers lost points because of poor bookkeeping;
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 + (x  a)x^{2}  ax^{2} = abc + x^{3}  2ax^{2} 


x^{3} + ab(c  x)  abx = abc + x^{3}  2abx 

 

 

The function decreases for 0
£ x
£ a and increases for
x
³ c. For b
£ x
£ c,

= x^{3}  2abx  b^{3} + 2ab^{2} 
 
= (x  b)[x^{2} + bx + b^{2}  2ab] 
 
= (x  b)[(x^{2}  ab) + b(x  a) + b^{2}] ³ 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) = 3x^{2}  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 S_{1} and S_{2} 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 = ( 
 __ ÖS_{1}

+ 
 __ ÖS_{2}

)(Ö[4 ]S_{1} +Ö[4 ]S_{2})^{2} . 

Solution 1. Let M
_{1} be the larger base of the truncated
pyramid with area S
_{1}, and M
_{2} the smaller base with area S
_{2}.
Let P
_{1} be the entire pyramid with base M
_{1} of which the truncated
pyramid is a part. Let M
_{0} be the base parallel to M
_{1} and
M
_{2} described in the problem, and let its area be S
_{0}. Let
P
_{0} be the pyramid with base M
_{0} and P
_{2} the pyramid with
base M
_{2}.
The inscribed sphere bounded by M_{0} and M_{1} is determined by
the condition that it touches M_{1} and the lateral faces of the
pyramid; thus, it is the inscribed sphere of the pyramid P_{1} with
base M_{1}; let its radius be R_{1}. The inscribed sphere bounded by
M_{2} and M_{0} is the inscribed sphere of the pyramid P_{0} with base
M_{0}; let its radius be R_{0}. Finally, let the inscribed sphere of
the pyramid with base M_{2} have radius R_{2}.
Suppose Q_{2} is the lateral area of pyramid P_{2} and Q_{1} the
lateral area of pyramid P_{1}. Thus, S = Q_{1}  Q_{2}.
There is a dilation with factor R_{0}/R_{1} that takes pyramid P_{1}
to P_{0}; since it takes the inscribed sphere of P_{1} to that
of P_{0}, it takes the base M_{1} to M_{0} and the base M_{0} to
M_{2}. Hence, this dilation takes P_{0} to P_{2}. The dilation
composed with itself takes P_{1} to P_{2}. Therefore

R_{0} R_{1}

= 
R_{2} R_{0}

and 
Q_{2} Q_{1}

= 
S_{2} S_{1}

= 
R_{2}^{2} R_{1}^{2}

. 

Consider the volume of P_{2}. Since P_{2} is the union of pyramids of
height R_{2} and with bases the lateral faces of P_{2} and M_{2}, its
volume is (1/3)R_{2}(Q_{2} + S_{2}). However, we can find the volume of
P_{2} another way. P_{2} 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 R_{0} with the removal of the
pyramid of base M_{2} and apex at the centre of the same sphere.
Thus, the volume is also equal to (1/3)R_{0}(Q_{2}  S_{2}).
Hence

Q_{2}  S_{2} Q_{2} + S_{2}

= 
R_{2} R_{0}

= 
R_{2}

= 

= 
Ö[4 ]S_{2} Ö[4 ]S_{1}



Þ Q_{2}(Ö[4 ]S_{1}  Ö[4 ]S_{2}) = S_{2} (Ö[4 ]S_{1} + Ö[4 ]S_{2}) , 

so that

= Q_{1}  Q_{2} = 
Q_{2} S_{2}

(S_{1}  S_{2}) 
 
= 
é ê
ë


Ö[4 ]S_{1} + Ö[4 ]S_{2} Ö[4 ]S_{1}  Ö[4 ]S_{2}


ù ú
û

[ 
 __ ÖS_{1}

 
 __ ÖS_{2}

][ 
 __ ÖS_{1}

+ 
 __ ÖS_{2}

] 
 
= ( Ö[4 ]S_{1} + Ö[4 ]S_{2} )^{2} ( 
 __ ÖS_{1}

+ 
 __ ÖS_{2}

) . 


Solution 2. [S. En Lu] Consider an arbitrary truncated pyramid
with bases A_{1} and A_{2} of respective areas s_{1} and
s_{2}, 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 A_{1}, A_{2} and C in the respective points
P_{1}, P_{2} and Q.
C is a trapezoid with sides of lengths a_{1} and a_{2} incident
with the respective bases A_{1} and A_{2}; let h_{1} and h_{2} be
the respective lengths of the altitudes
of triangles with apexes P_{1} and P_{2}
and bases bordering on C. By similarity (of A_{1} and A_{2}),

h_{1} h_{2}

= 
a_{1} a_{2}

= 
æ ú
Ö


. 

The plane that contains these altitudes passes through P
_{1}P
_{2}
(a diameter of
G) as well as Q, the point on C nearest to
the centre of
G. Since the height of C is a
_{1} + a
_{2}
[why?], its area is

1 2

(a_{1} + a_{2})(h_{1} + h_{2}) 

= 
1 2

[ a_{1}h_{1} + a_{2}h_{2} + a_{1}h_{2} + a_{2}h_{1} ] 
 
= 
1 2

[ a_{1}h_{1} + a_{2}h_{2} + 2 
 ________ Öa_{1}a_{2}h_{1}h_{2}

] 
 
= 
1 2

[ a_{1}h_{1} + a_{2}h_{2} + 2a_{2}h_{2}  Ö

s_{1}/s_{2}

] . 


Adding the corresponding equations over all the lateral faces
C yields
s = s_{1} + s_{2} +  Ö

s_{1} s_{2}

= (  Ö

s_{1}

+  Ö

s_{2}

)^{2} . 

With S_{0} defined as in Solution 1, we have that S_{1} / S_{0} = S_{0} / S_{2}, so that S_{0} = Ö[(S_{1}S_{2})]. Using the results of
the first paragraph applied to the truncated pyramids of bases
(S_{2}, S_{0}) and (S_{0}, S_{1}), we obtain that

= ( 
 __ ÖS_{1}

+ 
 __ ÖS_{0}

)^{2}+ ( 
 __ ÖS_{0}

+ 
 __ ÖS_{1}

)^{2} 
 
= ( 
 __ ÖS_{1}

+ Ö[4 ]S_{1}S_{2})^{2} +(Ö[4 ]S_{1}S_{2} + 
 __ ÖS_{2}

)^{2} 
 
= ( 
 __ ÖS_{1}

+ 
 __ ÖS_{2}

)(Ö[4 ]S_{1} +Ö[4 ]S_{2})^{2} . 

