Maths Intervarsity Competition 2000

Dublin City University

10.00–13.00 March 4^{th}

Answer all questions.

1. Prove that

∑_{k=1}^{n} \binom{n}{k}^{2} = \binom{2n}{n},

for any positive integer n. Answer: Let

c_{k} = \binom{n}{k}.

Then

c_{k} = c_{n−k};

and so the sum is

∑_{k=1}^{n} c_{k}c_{n−k} = coefficient of x^{n} in (1+c_{1}x+c_{2}x^{2}+⋯+c_{n}x^{n})(1+c_{1}x+c_{2}x^{2}+⋯+c_{n}x^{n})

But

(1 + c_{1}x + c_{2}x^{2} + ⋯ + c_{n}x^{n}) = (1 + x)^{n}.

Thus

∑_{k=1}^{n} c_{k}c_{n−k} = coefficient of x^{n} in (1 + x)^{2n} = \binom{2n}{n}.

2. Determine all positive integers n for which 2^{n} + 1 is divisible by 3. Answer: Since

2 ≡ −1 mod 3 it follows that

2^{n} ≡ (−1)^{n} mod 3

Hence

2^{n} + 1 ≡ (−1)^{n} + 1 ≡ \begin{cases}2 mod 3 & if n is even \\ 0 mod 3 & if n is odd \end{cases}

Thus

3 | 2^{n} + 1

if and only if n is odd.

3. Show that the sequence

\sqrt{7}, \sqrt{7 − \sqrt{7}}, \sqrt{7 − \sqrt{7 + \sqrt{7}}}, \sqrt{7 − \sqrt{7 + \sqrt{7 − \sqrt{7}}}}, … converges and evaluate the limit. Answer: Let

a_{0} = \sqrt{7}, a_{1} = \sqrt{7 − \sqrt{7}}, ….

Then

a_{n+2} = \sqrt{7 − \sqrt{7 + a_{n}}} (n ≥ 0)

Suppose a_{n} → ℓ. Then

ℓ = \sqrt{7 − \sqrt{7 + ℓ}},

ie

ℓ^{2} = 7 − \sqrt{7 + ℓ},

ie

(7 − ℓ^{2})^{2} = ℓ,

ie

ℓ^{4} − 14ℓ^{2} − ℓ + 42 = 0.

One root of this is ℓ = 2, since 16 − 56 − 2 + 42 = 0. Dividing,

ℓ^{4} − 14ℓ^{2} − ℓ + 42 = (ℓ − 2)(ℓ^{3} + 2ℓ^{2} − 10ℓ − 21).

Now we see that ℓ = −3 is also a root, since −27 + 18 + 30 − 21 = 0. Thus

ℓ^{4} − 14ℓ^{2} − ℓ + 42 = (ℓ − 2)(ℓ + 3)(ℓ^{2} − ℓ − 7).

The full set of roots is

2, −3, \frac{1}{2}(1 ± \sqrt{29}).

Now a_{n} < \sqrt{7} for all n, and so ℓ ≤ \sqrt{7}. Thus the only possible limit is ℓ = 2.

We observe that

a_{n} ≤ \sqrt{7} ⟹ \sqrt{7 + a_{n}} ≤ \sqrt{7 + \sqrt{7}}
⟹ a_{n+2} ≥ \sqrt{7 − \sqrt{7 + \sqrt{7}}} = a_{2}.

Also

a_{n} ≥ a_{2} ⟹ \sqrt{7 + a_{n}} ≥ \sqrt{7 + a_{2}}
⟹ a_{n+2} ≤ \sqrt{7 − \sqrt{7 + a_{2}}} = a_{4}.

Thus

a_{2} ≤ a_{n} ≤ a_{4}

for n ≥ 2.

To prove that the sequence converges, note that

7 − a_{n+2}^{2} = \sqrt{7 + a_{n}};

and so

(a_{n+2}^{2} − 7)^{2} = 7 + a_{n}.

Similarly,

(a_{n+3}^{2} − 7)^{2} = 7 + a_{n+1}.

Subtracting,

a_{n+1} − a_{n} = a_{n+3}^{4} − a_{n+2}^{4} − 14(a_{n+3}^{2} − a_{n+2}^{2})
= (a_{n+3}^{2} − a_{n+2}^{2})(a_{n+3}^{2} + a_{n+2}^{2} − 14)
= (a_{n+3} − a_{n+2})(a_{n+3} + a_{n+2})(a_{n+3}^{2} + a_{n+2}^{2} − 14)

Thus

\frac{a_{n+1} − a_{n}}{a_{n+3} − a_{n+2}} = −(a_{n+2} + a_{n+3})(14 − a_{n+2}^{2} − a_{n+3}^{2}).

Now

a_{n+2} + a_{n+3} ≥ 2a_{2} ≥ 2,

while

14 − a_{n+2}^{2} − a_{n+3}^{2} ≥ 14 − 2a_{4}^{2}
= 14 − 2(7 − \sqrt{7 + \sqrt{a_{2}})}
= 2(\sqrt{7 + \sqrt{a_{2}}}
> 4.

Thus

|\frac{a_{n+1} − a_{n}}{a_{n+3} − a_{n+2}} | > 8 > 2^{2}.

It follows by induction that

|a_{n+3} − a_{n+2}| ≤ \begin{cases}2^{−n}|a_{1} − a_{0}| & if n is odd \\ 2^{−n}|a_{2} − a_{1}| & if n is even. \end{cases}

In all cases,

|a_{n+3} − a_{n+2}| ≤ C2^{−n},

for some C > 0. Hence

a_{n} = a_{0} + (a_{1} − a_{0}) + ⋯ + (a_{n} − a_{n−1})

is convergent.

4. The sequence {x_{0}, x_{1}, x_{2}, … } is defined by the conditions

x_{0} = a, x_{1} = b, x_{n+1} = \frac{x_{n−1} + (2n − 1)x_{n}}{2n} .

Express lim_{n→∞} x_{n} concisely in terms of a and b (given numbers).

Answer: We can write the given relation in the form

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

Thus by induction

x_{n+1} − x_{n} = (−1)^{n} \frac{1}{2n · 2(n − 1) ⋯ 2 · 1}(x_{1} − x_{0})

= (−1)^{n} \frac{1}{n!}2^{−n}(x_{1} − x_{0})

Hence

x_{n} = x_{0} + (x_{1} − x_{0}) + (x_{2} − x_{1}) + ⋯ + (x_{n} − x_{n−1})

= x_{0} + (x_{1} − x_{0})(1 − \frac{1}{2!}2^{−1} + ⋯ ± \frac{1}{n!}2^{−n});

and so

x_{n} → x_{0} + (x_{1} − x_{0})e^{1/2} = a + (b − a)e^{1/2}.

5. A random number generator can only select one of the nine integers 1, 2, …, 9 and it makes these selections with equal probability. Determine the probability that after n selections the product of the n numbers will be divisible by 10.

Answer: The product will be divisible by 10 if and only if 2 and 5 occur among the chosen numbers.

Let X denote the set of all 9^{n} choices, let S denote the set of choices not including 2, and T the set of choices not including 5. Then the set of choices containing at least one 2 and at least one 5 is

X \ (S ∪ T).

Now

∥X∥ = 9^{n},

while

∥S∥ = ∥T ∥ = 8^{n},

since in either case we have n choices from 8 digits; and similarly

∥S ∩ T ∥ = 7^{n}, since there are now 7 choices for each of the n digits. Moreover,

∥S ∩ T ∥ + ∥S ∪ T ∥ = ∥S∥ + ∥T ∥.

Thus

∥S ∪ T ∥ = 2 · 8^{n} − 7^{n}.

Hence

∥X \ (S ∪ T)∥ = 9^{n} − ∥S ∪ T ∥ = 9^{n} − 2 · 8^{n} + 7^{n};

and the probability that the choice lies in this set is

\frac{9^{n} − 2 · 8^{n} + 7^{n}}{9^{n}} = 1 − 2(8/9)^{n} + (7/9)^{n}.

6. Evaluate

∫_{−∞}^{∞} e^{−ax^{2}−bx^{−2}}dx, a, b > 0.

Answer: Let

I(a, b) = ∫_{−∞}^{∞} e^{−(ax^{2}+bx^{−2})}dx.  (∗)

Substituting x = ρy,

I(a, b) = ∫_{−∞}^{∞} e^{−(aρ^{2}x^{2}+bρ^{−2}x^{−2})}ρdx
= ρI(ρ^{2}a, ρ^{−2}b).

Setting ρ = \sqrt[4]{b/a},

I(a, b) = \sqrt[4]{b/a} I(\sqrt{ab}, \sqrt{ab}).

Let

J(c) = I(c, c).

Then

I(a, b) = \sqrt[4]{b/a} J(\sqrt{ab}).

Differentiating (∗) with respect to b ‘under the integral sign’,

\frac{∂I(a, b)}{∂b} = − ∫_{−∞}^{∞} x^{−2}e^{−(ax^{2}+bx^{−2})}dx.

(This is valid, since the integral converges uniformly absolutely.) Substituting x = y^{−1},

I(a, b) = 2 ∫_{0}^{∞} e^{−(ax^{2}+bx^{−2})}dx

= 2 ∫_{∞}^{0} e^{−(ay^{−2}+by^{2})} − \frac{dy}{y^{2}}

= 2 ∫_{−∞}^{∞} x^{−2}e^{−(bx^{2}+ax^{−2})}dx.

Thus

\frac{∂I(a, b)}{∂b} = −I(b, a).

But

I(a, b) = a^{−1/4}b^{1/4}J(\sqrt{ab}).

Hence

\frac{∂I(a, b)}{∂b} = \frac{1}{4}a^{− \frac{1}{4}} b^{− \frac{3}{4}} J(\sqrt{ab}) + \frac{1}{2}a^{− \frac{1}{4}} b^{− \frac{1}{4}} J′(\sqrt{ab}).

Thus

\frac{1}{4}a^{− \frac{1}{4}} b^{− \frac{3}{4}} J(\sqrt{ab}) + \frac{1}{2}a^{− \frac{1}{4}} b^{− \frac{1}{4}} J′(\sqrt{ab}) = −a^{\frac{1}{4}} b^{− \frac{1}{4}} J(\sqrt{ab}),

ie

J(\sqrt{ab})(4\sqrt{ab} + 1) = −2\sqrt{ab}J′(\sqrt{ab}).

Thus

J′(x) = −\frac{4x + 1}{2x}J(x),

ie

\frac{J′(x)}{J(x)} = −2x − \frac{1}{2x}.

Hence

log J(x) = −2x − \frac{1}{2} log x + c,

ie

J(x) = \frac{C}{\sqrt{x}}e^{−2x}.

Thus

I(a, b) = a^{− \frac{1}{4}} b^{\frac{1}{4}} J(\sqrt{ab})
= Ca^{− \frac{1}{2}} e^{−2\sqrt{ab}}.

In particular,

I(1, 0) = C.

But we know that

I(1, 0) = ∫_{−∞}^{∞} e^{−x^{2}}dx = \sqrt{π}.

Hence C = \sqrt{π}, and so

I(a, b) = \sqrt{\frac{π}{a}}e^{−2\sqrt{ab}}.

7. How many zeros are there at the end of the number 2000! = 1 · 2 · 3 ⋯ 1999 · 2000?

Answer: Suppose 2 occurs to power m in 2000!, and 5 to power n. Then the number of zeros is min(m, n).

Now 2 divides [2000/2] of the numbers (where [x] denotes the greatest integer ≤ x), 2^{2} divides [2000/2^{2}] of the numbers, etc. It follows that

m = [2000/2] + [2000/2^{2}] + [2000/2^{3}] + ⋯;

and similarly

n = [2000/5] + [2000/5^{2}] + [2000/5^{3}] + ⋯,

It is clear that n ≤ m, since every term in the second sum is ≤ the corresponding term in the first sum.

Thus the number of zeros at the end of 2000! is

n = 400 + 80 + 16 + 3 = 499.

8. It may seem odd but the sets [0, 1] and [0, 1) contain the same “numbers” of points. Find a one to one map of [0, 1] onto [0, 1).

Answer: The map

f : [0, 1] → [0, 1)

defined by

f(x) = \begin{cases}\frac{1}{n+1} & if x = \frac{1}{n} \\ x & if x is not of the form \frac{1}{n} \end{cases}

has the required property. Thus f maps 1 to 1/2, 1/2 to 1/3, etc, and maps numbers not of this form to themselves.

9. The area T and an angle γ of a trianlge are given. Determine the lengths of the sides a and b so that the side cm opposite to the angle γ, is as short as possible.

Answer: We have

T = \frac{1}{2}ab sin γ,

while

c^{2} = a^{2} + b^{2} − 2ab cos γ

= (a − b)^{2} + 2ab(1 − cos γ)

= (a − b)^{2} + \frac{4T (1 − cos γ)}{sin γ}

Thus c is minimized when a = b, in which case

a = b = \sqrt{\frac{2T}{sin γ}} .

10. What is the smallest amount that may be invested at interest rate i, compounded annually, in order that one may withdraw £1 at the end of the first year, £4 at the end of the second year, …, £n^{2} at the end of the n^{th} year, …, in perpetuity?

Answer: Let the sum at the end of n years be a(n) pounds. Then

a(n + 1) = (1 + λ)a(n) − n^{2},

where λ = i/100. Thus

a(n + 1) − (1 + λ)a(n) = −n^{2}.

The solution of the homogeneous problem

a(n + 1) − (1 + λ)a(n) = 0

is

a(n) = ρ(1 + λ)^{n},

where ρ is a constant. For a particular solution let us try

a(n) = An^{2} + Bn + C.

Since

A(n + 1)^{2} + B(n + 1) + C = (1 + λ)(An^{2} + Bn + C) − n^{2}

for all n,

λA = 1,
λB = 2A,
λC = A + B.

Hence

A = \frac{1}{λ}, B = \frac{2}{λ^{2}} , C = \frac{λ + 2}{λ^{3}}.

Thus the general solution is

a(n) = ρ(1 + λ)^{n} + \frac{λ^{2}n^{2} + 2λn + λ + 2}{λ^{3}}.

We see that a(n) ≥ 0 for all n if and only if ρ ≥ 0. But

a(0) = ρ + \frac{λ + 2}{λ^{3}}.

Thus the smallest value that a(0) can have is

\frac{λ + 2}{λ^{3}} = \frac{200 + i}{i^{3}} × 10000

pounds.