Irish Intervarsity Mathematics Competition

Trinity College Dublin 1997

9.30–12.30 Saturday 22^{nd} February 1997

Answer as many questions as you can; all carry the same mark. Give

reasons in all cases. Tables and calculators are not allowed.

1. Compute

∑_{n=1}^{∞} \frac{n^{2}}{2^{n}} .

Answer: First solution: Let

f(x) = ∑_{0}^{∞} \frac{x^{n}}{2^{n}}

= 1 + \frac{x}{2} + \frac{x^{2}}{2^{2}} + ⋯
= \frac{1}{1 − x/2}
= \frac{2}{2 − x}.

Differentiating,

∑_{1}^{∞} \frac{nx^{n−1}}{2^{n}} = \frac{2}{(2 − x)^{2}} .

Multiplying by x,

∑_{1}^{∞} \frac{nx^{n}}{2^{n}} = \frac{2x}{(2 − x)^{2}} .

Differentiating again,

∑_{1}^{∞} \frac{n^{2}x^{n−1}}{2^{n}} = \frac{2}{(2 − x)^{2}} + \frac{4x}{(2 − x)^{3}} .

Substituting x = 1,

∑_{1}^{∞} \frac{n^{2}}{2^{n}} = 2 + 4 = 6.

Second solution: Let

S = ∑_{1}^{∞} \frac{n^{2}}{2^{n}}

Then

2S = ∑_{1}^{∞} \frac{n^{2}}{2^{n−1}}

= ∑_{0}^{∞} \frac{(n + 1)^{2}}{2^{n}}

= S + 2T + ∑_{0}^{∞} \frac{1}{2^{n}} ,

where

T = ∑_{1}^{∞} \frac{n}{2^{n}} .

Thus

S = 2T + 2.

Similarly,

2T = ∑_{1}^{∞} \frac{n}{2^{n−1}}

= ∑_{0}^{∞} \frac{n + 1}{2^{n}}
= T + 2.

It follows that

T = 2, S = 6.

2. A stick is broken in random in 2 places (the 2 break-points being chosen independently). What is the probability that the 3 pieces form a triangle?

Answer: We may suppose the stick has length 1. Let the 2 breaks occur at distance x and y along the stick. We can represent this case by the point (x, y) in the square 0 ≤ x, y ≤ 1. The probability will be given by the area in this square corresponding to breaks which give pieces that can form a triangle.

The condition for this is

x < 1/2, y < 1/2, 1 − x − y < 1/2.

These inequalities define a triangle in the square, of area 1/4. Hence the probability is 1/4.

3. For which real numbers x > 0 is there a real number y > x such that

x^{y} = y^{x} ?

Answer: Taking logs (to base e),

y log x = x log y.

Thus

\frac{log x}{x} = \frac{log y}{y} .

Consider the function

f(x) = \frac{log x}{x}.

Differentiating,

f′(x) = \frac{1 − log x}{x^{2}}.

As x → 0+, f(x) → −∞; and as x → ∞, f(x) → 0. Thus f(x) increases from 0 to e, where it takes the value e^{−1}, and then decreases to 0. Also f(x) < 0 for 0 < x < 1, and f(x) > 0 for x > 1

It follows that there is a y > x with f(y) = f(x) if and only if

1 < x < e.

4. Show that there are an infinity of natural numbers n such that when the last digit of n is moved to the beginning (as eg 1234 ↦ 4123) n is multiplied by 3.

Answer: Let

a_{n} a_{n−1} … a_{1} a_{0}

3

a_{0} a_{n} … a_{2} a_{1}

First solution: it is clear that a_{0} ≥ 3, since it appears as the first digit on the bottom.

Let us try a_{0} = 3. Then a_{1} = 9, and our sum starts

\begin{aligned}… & 9 & 3 \\ & & 3 \\ … & & 9 \end{aligned}

But then a_{2} = 7:

\begin{aligned}… & 7 & 9 & 3 \\ & & & 3 \\ … & & 7 & 9 \end{aligned}

Continuing in this way, we determine a_{3}, a_{4}, …, successively. After a long time we find we have completed a cycle, and are back where we started:

1034482758620689655172413793

3

3103448275862068965517241379

This number with 28 digits is a solution to our problem; and we see that the cycle could be repeated any number of times to give an infinity of solutions with 2 × 28, 3 × 28, … digits.

Second proof: Let

n = 10b + a,

where

a = a_{0}, b = 10^{n−1}a_{n} + 10^{n−2}a_{n−1} + ⋯ + a_{1}.

Then

3(10b + a) = 10^{n}a + b.

Thus

29a = (10^{n} − 3)b.

Hence

29 | 10^{n} − 3.

On the other hand, if this is true then it is easy to see that we get a solution with

a = \frac{10^{n} − 3}{29}, b = 1.

(We will also have solutions with b = 2 and b = 3.) Thus we have to show that there are an infinity of solutions n of

10^{n} ≡ 3 mod 29.

This follows by a little group theory, applied to the multiplicative group (ℤ/29)^{×} formed by the 28 non-zero remainders modulo 29. By Lagrange’s Theorem, the order of 10 in this group divides 28, and is thus 2, 4, 7, 14 or 28. But

10^{2} = 100 ≡ −12 mod 29, 10^{4} ≡ 12^{2} = 144 ≡ 3 mod 29.

Thus

10^{28q+4} ≡ 3 mod 29,

giving an infinity of solutions to our problem.

5. What is the whole number part of

1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + ⋯ + \frac{1}{\sqrt{1997}} ?

Answer: I was surprised no-one made a serious effort at this, as the basic idea — to approximate the sum ∑ f(n), where f(x) is an increasing or decreasing function, by the integral ∫ f(x) dx — is quite often used. It is the basis for example of the standard derivation of Stirling’s approximation to n!, which on taking logs reduces to approximating ∑ log n.

In our case we can approximate

S = ∑_{n=1}^{N} \frac{1}{\sqrt{n}}

by

∫ \frac{1}{\sqrt{x}} dx = [2\sqrt{X}].

Since 1/\sqrt{x} is decreasing,

∫_{1}^{N+1} \frac{1}{\sqrt{x}} dx ≤ ∑_{n=1}^{N} \frac{1}{\sqrt{n}} ≤ 1 + ∫_{1}^{N} \frac{1}{\sqrt{x}} dx.

But is that good enough? Almost certainly not, since the 2 values differ by almost 1. However, it cannot be out by more than 1. Thus

2(\sqrt{(1998)} − 1) < I < 1 + 2(\sqrt{(1997)} − 1).

Now

45^{2} = 81 × 25 = 2025, 44^{2} = 45^{2} − 90 + 1 = 1936.

Thus

\sqrt{(1997)} ≈ 44.7

and so

[S] = 87 or 88.

There are two ways of improving the estimate. We could start further into the sum, which would bring the bounds together; for example

∫_{4}^{N+1} \frac{1}{\sqrt{x}} dx ≤ I − 1 − \frac{1}{\sqrt{2}} − \frac{1}{\sqrt{3}} ≤ \frac{1}{2} + ∫_{4}^{N} \frac{1}{\sqrt{x}} dx.

An alternative way — which we shall follow — is to take the integral

∫_{n−1/2}^{n+1/2} f(x) dx

as an estimate for f(n).

In our case this means taking

2\sqrt{(n = 1/2)} − 2\sqrt{(n − 1/2)}

as an approximation to 1/\sqrt{n}. Since the function f(x) = 1/\sqrt{x} is concave, it follows that

\frac{1}{\sqrt{n}} < ∫_{n−1/2}^{n+1/2} \frac{1}{\sqrt{x}} dx
= 2 (\sqrt{(n + 1/2)} − \sqrt{(n − 1/2)}) .

It follows that

S > 1 + 2(\sqrt{1997.5} − \sqrt{1.5})
≈ 1 + 2(44.7 − 1.2)
≈ 88.

We conclude that

[S] = 88.

6. Prove that

n(n + 1)(n + 2) > (n + \frac{8}{9})^{3}

for any integer n ≥ 3.

Answer: This is the easiest question on the paper, even if it is stated in a slightly misleading way, since the result has nothing to do with integers. In effect it concerns the polynomial

f(x) = x(x + 1)(x + 2) − (x + \frac{8}{9})^{3}
= (3 − \frac{2^{3}}{3} ) x^{2} + (2 − \frac{2^{6}}{3^{3}} ) x − \frac{2^{9}}{3^{6}} .

This is a quadratic, and f(x) → ∞ as x → −∞ and as x → ∞. It follows that f(x) has a minimum where f′(x) = 0, ie where

\frac{2}{3}x = \frac{10}{27},

that is,

x = \frac{5}{9}.

It follows that f(x) is increasing for x ≥ 3; so it is sufficient to show that

f(3) > 0,

ie

3 · 4 · 5 ≥ (\frac{35}{9})^{3} ,

ie

3^{7} · 4 ≥ 7^{3} · 5^{2},

ie

8748 ≥ 8575.

7. Show that the determinant of the 3 × 3 matrix

A = (\begin{matrix}sin(x_{1} + y_{1}) & sin(x_{1} + y_{2}) & sin(x_{1} + y_{3}) \\ sin(x_{2} + y_{1}) & sin(x_{2} + y_{2}) & sin(x_{2} + y_{3}) \\ sin(x_{3} + y_{1}) & sin(x_{3} + y_{2}) & sin(x_{3} + y_{3}) \end{matrix})

is zero for all real numbers x_{1}, x_{2}, x_{3}, y_{1}, y_{2}, y_{3}.

Answer: This problem can be solved by computing the determinant Δ directly. But the following argument is quicker.

Consider Δ as a function of x_{1}. Evidently

Δ = A sin x_{1} + B cos x_{1},

where A, B are functions of x_{2}, x_{3}, y_{1}, y_{2}, y_{3}.

The determinant vanishes if x_{1} = x_{2}, since the first 2 rows are then equal. Similarly it vanishes if x_{1} = x_{3}. It follows that

A sin x_{2} + B cos x_{2} = 0 = A sin x_{3} + B cos x_{3}.

This implies that either A = B = 0, in which case Δ = 0, or else

sin x_{2} cos x_{3} = sin x_{3} cos x_{2},

ie

tan x_{2} = tan x_{3},

ie

x_{2} − x_{3} = nπ

for some n ∈ ℕ. We can write this

x_{2} ≡ x_{3} mod π.

Similarly, if Δ ≠ 0 then

x_{3} ≡ x_{1} mod π, x_{1} ≡ x_{2} mod π.

It follows that 2 (at least) of x_{1}, x_{2}, x_{3} differ by a multiple of 2π, say

x_{1} ≡ x_{2} mod 2π.

But then the first 2 rows of Δ are equal, and Δ vanishes.

8. Let

A(m, n) = \frac{m!(2m + 2n)!}{(2m)!n!(m + n)!}

for non-negative integers m and n. Show that

A(m, n) = 4A(m, n − 1) + A(m − 1, n)

for m ≥ 1, n ≥ 1. Hence or otherwise show that A(m, n) is always an integer.

Answer: If m, n ≥ 1,

4A(m, n − 1) + A(m − 1, n) = 4\frac{m!(2m + 2n − 2)!}{(2m)!(n − 1)!(m + n − 1)!} + \frac{(m − 1)!(2m + 2n − 2)!}{(2m − 2)!n!(m + n − 1)!}
= \frac{(m − 1)!(2m + 2n − 2)!}{(2m)!n!(m + n − 1)!} (4mn + 2m(2m − 1))
= \frac{m!(2m + 2n − 2)!}{(2m)!n!(m + n − 1)!} (2(2n + 2m − 1))
= \frac{m!(2m + 2n − 1)!}{(2m)!n!(m + n − 1)!}2
= \frac{m!(2m + 2n)!}{(2m)!n!(m + n)!}
= A(m, n).

On the other hand,

A(m, 0) = \frac{m!(2m)!}{(2m)!m!} = 1,

while

A(0, n) = \frac{(2n)!}{n!n!} = C_{n}^{2n},

an integer.

But now it follows by induction on d = m + n that A(m, n) is an integer. This is true when d = 0, since A(0, 0) = 1 as we have seen. Now suppose it true for all m, n with m+n = d. Then if m+n = d+1, the terms on the right in the recursion formula A(m, n) = 4A(m, n −

1) + A(m − 1, n) have already been proved integral, and so A(m, n) is also integral.

9. Let P (x) = a_{0} + a_{1}x + ⋯ + a_{n}x^{n} be a real polynomial of degree n ≥ 2 such that

0 < a_{0} < − ∑_{k=1}^{[n/2]} \frac{1}{2k + 1}a_{2k}

(where [n/2] denotes the integer part of n/2). Prove that the equation P (x) = 0 has at least one solution in the range −1 < x < 1.

Answer: The conditions can be written

a_{0} > 0, a_{0} + \frac{1}{3} 3 + \frac{1}{5} 5 + ⋯ < 0.

But

∫_{−1}^{1} P (x) dx = 2 (a_{0} + \frac{1}{3} 3 + \frac{1}{5} 5 + ⋯) .

Thus

f(0) > 0, ∫_{−1}^{1} f(x) dx < 0.

From the second condition, f(x) < 0 for some x ∈ (−1, 1). Thus f(x) changes sign in (−1, 1), and so has a zero there.

10. Suppose a_{1}, a_{2}, a_{3}, … is an infinite sequence of real numbers satisfying 0 < a_{n} ≤ 1 for all n. Let S_{n} = a_{1} + a_{2} + ⋯ + a_{n} and T_{n} = S_{1} + S_{2} + ⋯ + S_{n}. Show that

∑_{n=1}^{∞} \frac{a_{n}}{T_{n}} < ∞.

Answer: The idea is to “bunch together” the a_{n}’s, and treat each bunch as one element.

More precisely, if ∑ a_{n} converges then the result is immediate, since T_{n} ≥ a_{1} and so

∑ \frac{a_{n}}{T_{n}} ≤ \frac{1}{a_{1}} ∑ a_{n}.

We may assume therefore that

∑ a_{n} = ∞.

Now let us divide the a_{n}’s successively into bunches, each with sum ≥ 1 but < 2, say

1 ≤ a_{1} + a_{2} + ⋯ + a_{m_{1}} < 2, 1 ≤ a_{m_{1}+1} + ⋯ + a_{m_{2}} < 2,

and so on. Then

S_{m_{1}} ≥ 1, S_{m_{2}} ≥ 2, S_{m_{3}} ≥ 3, …

and

T_{m_{1}} ≥ 1, T_{m_{2}} ≥ 3, S_{m_{3}} ≥ 6, ….

In general

S_{m_{r}} ≥ r, T_{m_{r}} ≥ \frac{r(r + 1)}{2}.

But now

\frac{a_{m_{r}+1}}{T_{m_{r}+1}} + ⋯ + \frac{a_{m_{r+1}}}{T_{m_{r+1}}} ≤ \frac{a_{m_{r}+1} + ⋯ + a_{m_{r+1}}}{T_{m_{r}}}
≤ \frac{2}{T_{m_{r}}} .

Thus

∑ \frac{a_{n}}{T_{n}} ≤ 2 (\frac{1}{T_{m_{1}}} + \frac{1}{T_{m_{2}}} + ⋯)
≤ ∑ \frac{1}{r(r + 1)} < ∞