Irish Intervarsity Mathematics Competition 1999

University College Cork

Answer all questions. Tables and calculators may be used.

1. Find the value of

lim_{n→∞} (∑_{r=0}^{n} \frac{1}{\binom{n}{r}}) ,

where \binom{n}{r} is the binomial coefficient, the number of combinations of n things taken r at a time. Answer: Let us write c_{r} for \binom{n}{r}. Then c_{n−r} = c_{r}; and the binomial coefficient c_{r} increases as r increases from r = 0 to the middle of [0, n], and then decreases to r = n. In particular,

c_{r} ≥ c_{2} = \frac{n(n − 1)}{2} if r ≠ 0, 1, n − 1, n.

Thus

S(n) = ∑ \frac{1}{c_{r}} ≤ 1 + \frac{1}{n} + δ + \frac{1}{n} + 1,

where

δ ≤ n\frac{2}{n(n − 1)} = \frac{2}{n − 1}.

Thus each of the middle three parts tends to 0, leaving the two 1’s at the ends, and so

S(n) → 2 as n → ∞.

Remark: I thought at first that one would have to use the estimate for \binom{n}{r} which one gets from the Law of Large Numbers, ie for large n the binomial coefficients approximate to the curve e^{−x^{2}}, suitably scaled and translated.

2. The coordinates of four points in the plane are given by A(0, 0), B(1, 2), C(3, 3) and D(3, 0). What is the smallest possible value of |P A|+|P A|+|P C|+ |P D|, where P is any point in the plane.

Answer: Remark: There were three “resources” that occurred to me for dealing with this question:

(a) The “reflection principle” that if A, B are two points on the same side of the line ℓ then AP + BP is minimised, for P on ℓ, when AP and BP make the same angle with ℓ. (This is easily proved by joining A to the reflection of B in ℓ.)

(b) The locus of points such that P A+P B = c, where c is a constant, is an ellipse with foci at A, B.

(c) If r is a vector of length r = |r| then

dr = \frac{r.dr}{r}
= u.dr,

where u is a unit vector in the direction of r.

Now for the answer. We have AB = BC = \sqrt{5}, CD = DA = 3. Thus the quadrilateral splits into two isosceles triangles, and is symmetric about the diagonal BD. Also the diagonals are each at angle π/4 to the axes, and so are perpendicular.

If we assume the minimum occurs at a point P on the axis of symmetry, then the result follows at once; for BP + P D is constant for points on the segment BD, and AP + P C is clearly minimised when AP C is a straight line. Hence the minimum occurs where the diagonals meet, ie at the mid-point of AC, namely P = (3/2, 3/2).

To see that the minimum must occur on this line BD. suppose there was a minimum at a point M off the line. Then the reflection M′ of M in BD is also a minimum. But consider P on the segment MM′. By the “reflection principle” above, AP + CP is minimised when P is at the mid-point of MM′ (on the axis BD); and both BP and DP get smaller when P moves from M to this mid-point. Hence the minimum must occur on the axis of symmetry.

3. Two real numbers a and b are chosen with 0 ≤ a ≤ 1 and 0 ≤ b ≤ 1. What is the probability that a^{2} + b^{2} ≤ 1.

Answer: The point (a, b) is evenly distributed over the unit square. Hence the probability is just the area of the subset {(a, b) : a^{2} + b^{2} ≤ 1} of this square, ie the quarter-circle with radius 1. Thus the probability is π/4.

4. If x, y, z, w, t and u are all prime numbers with x ≤ y ≤ z ≤ w ≤ t ≤ u, find all solutions of the equation

x^{2} + y^{2} + z^{2} + w^{2} + t^{2} = u^{2}.

Answer: This is based on the fact that if x is odd then

x^{2} ≡ 1 mod 8.

Evidently u is odd, since 2 is the only even prime. Thus

u^{2} ≡ 1 mod 8.

Suppose a of the numbers on the left are 2, and the remaining 5 − a are odd. Then

x^{2} + y^{2} + z^{2} + w^{2} + t^{2} ≡ 4a + (5 − a) mod 8.

The only way in which this can be ≡ 1 mod 8 is if a = 4 and 5 − a = 1. In other words the equation is

2^{2} + 2^{2} + 2^{2} + 2^{2} + t^{2} = u^{2},  (1)

ie

16 + t^{2} = u^{2},  (2)

ie

16 = (u − t)(u + t).  (3)

Since t and u are odd, u − t and u + t are both even. On factoring 16, there is only one possibility:

(u − t, u + t) = (2, 8),  (4)

ie

t = 3, u = 5.  (5)

so the only solution is

2^{2} + 2^{2} + 2^{2} + 2^{2} + 3^{2} = 5^{2}.

5. Evaluate ∑_{r=1}^{n}(r + 1)^{2}(r!).

Answer: Remark: There are only two simple ways in which one might get a “closed” formula for a sum like this:

(a) by expressing the sum as a coefficient in the product of two polynomials; and

(b) by expressing the rth term in the form

a_{r} = f(r) − f(r − 1)

for some function f(r).

In this case we have

(r + 1)^{2}r! = (r + 1)(r + 1)!
= (r + 2)(r + 1)! − (r + 1)!
= (r + 2)! − (r + 1)!

Thus

∑_{r=1}^{n}(r + 1)^{2}r! = (3! − 2!) + (4! − 3!) + ⋯ + ((n + 2)! − (n + 1)!)
= (n + 2)! − 2.

6. Find all positive integers less than 100 which have precisely seven distinct divisors (including 1 and n). Answer: Suppose

n = p_{1}^{e_{1}}p_{2}^{e_{2}} ⋯ p_{r}^{e_{r}},

where p_{1}, …, p_{r} are distinct primes, and each e_{i} is a positive integer. Then the factors of n are the numbers

d = p_{1}^{j_{1}}p_{2}^{j_{2}} ⋯ p_{r}^{j_{r}},

where

0 ≤ j_{i} ≤ e_{i}

for i = 1, …, r. Thus n has just

(e_{1} + 1)(e_{2} + 1) ⋯ (e_{r} + 1)

factors. If this is 7, then we must have r = 1 and e_{1} = 6, ie n = p_{1}^{6}. The only such power less than 100 is 2^{6} = 64. Thus there is only one number in this range with just 7 divisors.

7. Let ABC be a triangle with a right angle at A. Show that the internal bisector of the angle BAC divides the square on the hypotenuse BCDE into two parts of equal area.

Answer: A line divides a rectangle into 2 equal parts if and only if it goes through the centre O. For if the line goes through the centre, then reflection in the centre (which is an isometry, and so preserves area) sends one part into the other; while if the line does not go through the centre then the parallel line through the centre divides the square into equal parts, so the original line cannot do this.

It follows that we have to show that the bisector of A goes through the centre O of the square BCDE.

The circle with BC as diameter passes through A and O, since the angles BAC and BOC are both π/2. Hence

CAO = CBO = π/4.

Thus CO bisects the right angle A, and the result follows.

8. Evaluate

f(m, n) = ∫_{0}^{1} x^{m}(1 − x)^{n} dx

as a function of m and n only.

Answer: Integrating by parts,

f(m, n) = [\frac{x^{m+1}}{m + 1}(1 − x)^{n}]_{0}^{1} + ∫_{0}^{1} \frac{x^{m+1}}{m + 1}n(1 − x)^{n−1}

The first term vanishes, since x^{m+1} = 0 at x = 0 and (1 − x)^{n} = 0 at x = 1 (assuming n ≥ 1). Thus

f(m, n) = \frac{n}{m + 1}f(m + 1, n − 1).

Repeating this,

f(m, n) = \frac{n}{m + 1}f(m + 1, n − 1)

= \frac{n}{m + 1} \frac{n − 1}{m + 2}f(m + 2, n − 2)

⋯

= \frac{n(n − 1) ⋯ 1}{(m + 1)(m + 2) ⋯ (m + n)}f(m + n, 0)

= \frac{n(n − 1) ⋯ 1}{(m + 1)(m + 2) ⋯ (m + n)} ∫_{0}^{1} x^{m+n} dx

= \frac{n(n − 1) ⋯ 1}{(m + 1)(m + 2) ⋯ (m + n)} \frac{1}{m + n + 1}

= \frac{n(n − 1) ⋯ 1}{(m + 1)(m + 2) ⋯ (m + n + 1)}.

Thus

f(m, n) = \frac{m!n!}{(m + n + 1)!}.

9. A window of total perimeter 200cm consists of a rectangle surmounted by a semicircle. Find the maximal area the window can have.

Answer: Let the semicircle have radius r, and the rectangle have sides 2r, 2s. Then the perimeter is

P = πr + 2r + 4s = (π + 2)r + 4s,

while the area is

A = πr^{2} + 4rs.

It follows that

dP = (π + 2) dr + 4 ds,

while

dA = (2πr + 4s) dr + 4r ds.

At a stationary point, dA = 0 whenever dP = 0. It follows that the two linear forms in dr, ds must be proportional, ie

\frac{2πr + 4s}{π + 2} = \frac{4r}{4}.

Thus

(2πr + 4s) = (π + 2)r,

and so

s = \frac{π − 2}{4}r.

Since P = (π + 2)r + 4s = 200, we conclude that

r = \frac{100}{π}, s = \frac{25(π − 2)}{π},

giving minimal area

A = \frac{10000}{π} + \frac{10000(π − 2)}{π^{2}}

= 20000\frac{π − 1}{π^{2}}.

10. The lengths of the sides of a quadrilateral are 1, 2, 3 and 4. What is the maximal area the quadrilateral can have?

Answer: Suppose a quadrilateral has sides AB = a, BC = b, CD = c, DA = d. Then its area Δ is given by

2Δ = ab sin A + cd sin C.

Let the diagonal AC = x. Then

x^{2} = a^{2} + b^{2} − 2ab cos A, x^{2} = c^{2} + d^{2} − 2cd cos C.

It follows that

2x dx = −2ab sin A dA = −2cd sin C dC.

On the other hand,

2 dA = ab cos A dA + cd cos C dC

If the area is stationary, then dΔ = 0 whenever ab sin A dA = cd sin C dC. In other words, the two linear forms in dA, dC are proportional, ie

\frac{ab sin A}{ab cos A} = \frac{−cd sin C}{cd cos C} ,

ie

tan A = − tan C,

ie

A + C = π.

Thus we have proved the theorem that a quadrilateral with given sides has maximal area when it is concyclic.

In the present case, our two equations for x^{2} give

a^{2} + b^{2} − 2ab cos A = c^{2} + d^{2} − 2cd cos C,

which with cos C = − cos A gives

(2 · 1 · 2 + 2 · 3 · 4) cos A = 1^{2} + 2^{2} − 3^{2} − 4^{2},

ie

cos A = −\frac{20}{28} = −\frac{5}{7},

and so

sin A = sin C = \frac{\sqrt{24}}{7} = \frac{2}{7}\sqrt{6}.

We conclude that the maximal area is

Δ = \frac{ab + cd}{2} sin A = \frac{14}{2} · \frac{2}{7}\sqrt{6} = 2\sqrt{6}.