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).

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 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 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 x₁, x₂, ¼, x_2p-1 be 2p-1 integers. Wolog, we can assume that the x_i have been reduced to their least non-negative residue modulo p and that they are in increasing order. For 1 £ i £ p-1, 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₁ + x₂ + ¼+ 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 }, and, for k ³ 1, that A_k is the set of distinct numbers i with 0 £ i £ p-1 which either lie in A_k-1 or are congruent to a + y_k for some a in A_k-1. 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, ¼, p-1 }.

Suppose that going from A_j-1 to A_j yields no new elements. Since 0 Î A_j-1, y_j Î A_j, which means that y_j Î A_j-1. Then 2y_j = y_j + y_j Î A_j = A_j-1, 3y_j = 2y_j + y_j Î A_j = A_j-1, and so on. Thus, all multiples of y_j (modulo p) are in A_j-1. As p is prime, we find that A_j-1 must contain { 0, 1, ¼, p-1 }. 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?

Comment. P must be chosen so that PB:PC = AB²:AC².

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?

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

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

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

x1 x2 ¼xn (1 + x1)(x1 + x2) ¼(xn-1 + xn)(xn + an+1)

subject to the constraint that x₁, x₂, ¼, x_n > 0.

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². 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₀, a₁, ¼, a_n ¼} satisfying, for each positive integer n, the equation

a0 a1 + a0 a2 + ¼+ a0 an + p an+1 = 1 .

Therefore, a₀ = p - 1 and a_n = p^n-2a₂ for n ³ 2. Thus, once a₁ and a₂ are selected, then the rest of the sequence { a_n } is determined. The remaining condition that has to be satisfied is

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

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_n-1) = a₀a_n for n ³ 3, whence

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.

For a £ x £ b, f¢(x) = 3x² - 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₁ and S₂ 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 .

The inscribed sphere bounded by M₀ and M₁ is determined by the condition that it touches M₁ and the lateral faces of the pyramid; thus, it is the inscribed sphere of the pyramid P₁ with base M₁; let its radius be R₁. The inscribed sphere bounded by M₂ and M₀ is the inscribed sphere of the pyramid P₀ with base M₀; let its radius be R₀. Finally, let the inscribed sphere of the pyramid with base M₂ have radius R₂.

Suppose Q₂ is the lateral area of pyramid P₂ and Q₁ the lateral area of pyramid P₁. Thus, S = Q₁ - Q₂.

There is a dilation with factor R₀/R₁ that takes pyramid P₁ to P₀; since it takes the inscribed sphere of P₁ to that of P₀, it takes the base M₁ to M₀ and the base M₀ to M₂. Hence, this dilation takes P₀ to P₂. The dilation composed with itself takes P₁ to P₂. Therefore

Consider the volume of P₂. Since P₂ is the union of pyramids of height R₂ and with bases the lateral faces of P₂ and M₂, its volume is (1/3)R₂(Q₂ + S₂). However, we can find the volume of P₂ another way. P₂ 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₀ with the removal of the pyramid of base M₂ and apex at the centre of the same sphere. Thus, the volume is also equal to (1/3)R₀(Q₂ - S₂).

Hence

Solution 2. [S. En Lu] Consider an arbitrary truncated pyramid with bases A₁ and A₂ of respective areas s₁ and s₂, 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₁, A₂ and C in the respective points P₁, P₂ and Q.

C is a trapezoid with sides of lengths a₁ and a₂ incident with the respective bases A₁ and A₂; let h₁ and h₂ be the respective lengths of the altitudes of triangles with apexes P₁ and P₂ and bases bordering on C. By similarity (of A₁ and A₂),

With S₀ defined as in Solution 1, we have that S₁ / S₀ = S₀ / S₂, so that S₀ = Ö[(S₁S₂)]. Using the results of the first paragraph applied to the truncated pyramids of bases (S₂, S₀) and (S₀, S₁), we obtain that