DUMS Intervarsity Team Selection Test

Easter 2009

Time allowed: 90 minutes

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

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

1. What are the last 3 digits of 2009^{2009}?

Answer: It is sufficient to determine

9^{2009} mod 1000,

since a ≡ b mod n ⟹ a^{n} ≡ b^{n} mod n. By the binomial theorem,

9^{2009} = (10 − 1)^{2009}

≡ (−1)^{2009} + 2009 · 10 · (−1)^{2008} + \binom{2009}{2}10^{2}(−1)^{2007} mod 1000

≡ −1 + 90 − \frac{9 · 8}{2}100 mod 1000

≡ −1 + 90 − 600 mod 1000

≡ 489 mod 1000, ie the last 3 digits are 489.

2. What is the first digit of 1001^{1001}? Answer: We know that

(1 + \frac{1}{n})^{n} → e

More questions overleaf! as n → ∞.

The first digit of 1001^{1001} is the same as the first digit of (1 + \frac{1}{1000})^{1001}.

But

(1 + \frac{1}{1000})^{1000} ≈ e = 2.6 ….

The additional factor (1 + 1/1000) will not affect the first digit. Thus the first digit is 2.

[And the first 2 digits are 26.

If asked to justify the argument above we would go back to the proof that (1 + 1/n)^{n} → e, by taking logarithms, with

log(1 + 1/n) = 1/n − 1/2n^{2} + 1/3n^{3} − ⋯,

so that

log(1 + 1/n)^{n} = 1 + O(1/n).

It would be a straightforward matter to verify that the error involved in omitting the terms after the first is not sufficient to alter the first, or even the first 2, digits.]

3. Show that, in any collection of 52 distinct positive integers, there are two distinct numbers whose sum or difference is divisible by 100.

Answer: If 0 and/or 50 are among the 52 integers, ignore them. Let the remaining integers be x_{1}, …, x_{50}. Consider the 101 integers

{50, ±x_{1}, …, ±x_{50}}.

There are 100 residue-classes mod 100. Hence (by the pigeon-hole principle) two of these must lie in the same residue-class, ie

x_{i} ≡ x_{j} mod 100 or x_{i} ≡ −x_{j} mod 100.

In the first case x_{i} − x_{j} is divisible by 100; in the seond case x_{i} + x_{j} is divisible by 100.

4. Six positive integers are written on the faces of a cube. At each vertex, the numbers on the 3 adjacent faces are multiplied. The sum of these 8 products is 105. What is the sum of the 6 numbers on the faces?

Answer: Choose two opposite faces. Let the numbers on these be a, b. Let the numbers on the remaining 4 faces (going round the cube) be cdef. Then the sum of the products involving the first face is

a(cd + de + ef + fc) = a(c + e)(d + f).

Similarly, the sum of the products involving the second face is

b(cd + de + ef + fc) = a(c + e)(d + f).

Hence the sum of all the products is

(a + b)(c + e)(d + f).

But

105 = 3 · 5 · 7.

Hence

a + b, c + e, d + f = 3, 5, 7

in some order. We conclude that a + b + c + d + e + f = 3 + 5 + 7 = 15.

5. Find all integer solutions of

8xy + 5x + 3y = 0.

Answer: [There are various approaches to this very simple problem.] Multiplying the equation by 8,

64xy + 40x + 24y = 0,

ie

(8x + 3)(8y + 5) = 15.

Thus (8x+3, 8y+5) = (1, 15), (−1, −15), (15, 1), (−15, −1), (3, 5), (−3, −5), (5, 3), (−5, −3). Each of these determines x, y. The only cases giving integer values to x, y are

(8x + 3, 8y + 5) = (3, 5) ⟹ (x, y) = (0, 0)
(8x + 3, 8y + 5) = (−5, −3) ⟹ (x, y) = (−1, −1).

6. Suppose Ireland and Wales are equally strong at rugby. Which is more likely, that Ireland wins 3 games out of 4, or that Wales wins 5 games out of 8? (Ignore the possibility of draws.)

Answer: The probability of Ireland winning 3 games out of 4 is

\binom{4}{3}(\frac{1}{2})^{4} = \frac{1}{4}.

The probability of Wales winning 5 games out of 8 is

\binom{8}{5}(\frac{1}{2})^{8} = \frac{7}{32}.

Thus it is more likely that Ireland wins 3 games out of 4.

7. Given a point P and a circle Γ, suppose a line l through P cuts Γ in X, Y. Show that P X.P Y is independent of l.

Answer: Suppose P XY, P X′Y′ are two such lines. Consider the triangles P XY′, P Y X′.

Recall that the angle AXB subtended by a chord AB in a circle is constant. Hence the angles ∠P XY′ = ∠X′XY and ∠P Y X′ = ∠Y′Y X are equal.

The two triangles also have the angle ∠XP X′ in common. Hence the two triangles have the same angles, and so are similar.

It follows that

\frac{P X}{P Y′} = \frac{P Y}{P X′}

ie

P X · P X′ = P Y · P Y′.

8. Suppose p(x) is a polynomial with integer coefficients such that

p(0) = p(1) = 2009.

Show that p(x) has no integer zeros.

Answer: Consider the polynomial

f(x) = p(x) − 2009.

We have

f(0) = f(1) = 0.

Hence

f(x) = x(x − 1)q(x)

for some polynomial q(x), ie

p(x) = x(x − 1)q(x) + 2009.

If

p(n) = 0

then

n(n − 1) | 2009.

But

2009 = 7 · 287.

Thus

n ∈ {±1, ±7, ±287, ±2009}.

But in none of these cases does (n − 1) | 2009.

9. Suppose the sequence x_{n} satisfies

lim_{n→∞}(x_{n+1} − x_{n}) = 0.

Show that

lim_{n→∞} \frac{x_{n}}{n} = 0.

Answer: Given ϵ > 0 we can find N such that

|x_{n+1} − x_{n}| < ϵ/2 if n ≥ N.

If x ≥ N then

x_{n} = (x_{n} − x_{n−1}) + (x_{n−1} − x_{n−2}) + ⋯ + (x_{N+1} − x_{N}) + x_{N}. Hence

|x_{n}| ≤ |x_{n} − x_{n−1}| + |x_{n−1} − x_{n−2}| + ⋯ + |x_{N+1} − x_{N}| + |x_{N}|
≤ (n − N)ϵ/2 + |x_{N}|

Thus

|a_{n}/n| ≤ ϵ/2 + |x_{N}/n|.

Now choose M such that

|x_{N}/n| < ϵ/2

if n ≥ M. Then

|x_{n}/n| < ϵ

if n ≥ max(M, N). Hence

x_{n}/n → 0.

10. Does there exist a differentiable function f : ℝ → ℝ, not identically

zero, such that

f′(x) = f(x + 1)

for all x? Answer: Let us try

f(x) = e^{cx}.

This will satisfy the given equation if

ce^{cx} = e^{c(x+1)} = e^{c}e^{cx},

ie if

c = e^{c}.

Now it is easy to see that c ≠ e^{c} for any real number c; for if c < 0 then e^{c} > 0, while if c > 0 then e^{c} > c. However, we may be able to find a complex number c such that

e^{c} = c;

and then

f(x) = ℜ(e^{cx}) = cos(cx)

will satisfy the given relation. Thus there is a solution provided the function

f(z) = e^{z} − z

has a zero.