Irish Intervarsity Mathematics Competition 2007

Trinity College Dublin

11.00–14.00 Saturday 14^{th} April 2007

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

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

1. Does the number 2007^{n} end with the digits 2007 for any n > 1?

Answer: The answer is Yes. The multiplicative group (ℤ/10000)^{×} has order

ϕ(10000) = ϕ(2^{4}5^{4})
= ϕ(2^{4})ϕ(5^{4})
= 2^{3} · 4 · 5^{3}
= 4000.

Hence, by Lagrange’s Theorem,

2007^{4000} ≡ 1 mod 10000,

and so

2007^{n} ≡ 2007 mod 1000

if

n = 2000m + 1.

2. Does the number 2007^{n} begin with the digits 2007 for any n > 1?

Answer: The answer is Yes. The result follows if we can find n such that

2007^{n} = 10000000000 …,

ie

2007^{n} = 10^{m}(1 + ϵ),

where 0 < ϵ < 0.00000000001; for then

2007^{n+1} = 2007 …,

Taking logarithms to base 10, and setting α = log_{10}2007,

nα = m + log_{10}(1 + ϵ),

which will hold if

0 ≤ [nα] ≤ ϵ,

We can find such an n for any real number α. (This is Kronecker’s Theorem.) For if we consider the remainders [nα], two must differ by less than ϵ (by the Pigeon Hole Principle), say

0 ≤ [rα] − [sα] ≤ ϵ,

and so

0 ≤ [nα] ≤ ϵ,

for n = r − s.

3. Three ants A,B,C start at the vertices of an equilateral triangle. Ant A pursues B, B pursues C, and C pursues A (each moving always in the direction of its target). If the sides of the triangle are 1 metre in length, and the ants move at 1mm/sec, how long does it take them to meet at the centroid of the triangle? Answer: The 3 ants will always lie at the vertices of an equilateral triangle A(t)B(t)C(t), with the same centroid O. The angle

∠OA(t)B(t) = π/6.

Hence the component of the velocity of ant A towards O is

v = 1 · cos(π/6) = \sqrt{3}/2.

Initially

AO = \frac{2}{3} · \frac{\sqrt{3}}{2} · 1000.

Hence the time taken for the ants to reach O is

T = \frac{2000}{3} seconds.

4. Is the circle the only convex figure with the property that every inscribed equilateral triangle is of the same size?

Answer: Hopefully a contestant will give a better proof than the following, which I only sketch.

Suppose ABC is one position of the triangle, with centroid O. By considering neighbouring triangles, we deduce that the angles between the tangents at A, B, C and the lines OA, OB, OC (respectively) must be equal.

But then the centroid G must be fixed, to first order; and so it must be fixed.

5. A triangle ABC is given.

(a) What point P minimizes AP + BP + CP?

(b) What point P minimizes AP^{2} + BP^{2} + CP^{2}?

Answer:

(a) The point P minimizing AP + BP + CP is the unique point P

such that

AP̂B = BP̂C = CP̂A = \frac{2π}{3} (= 120^{∘}).

(To construct this point, draw a circular arc on AB such that AP̂B = 2π/3 for all points P on the arc; and a similar circular arc on BC such that BP̂C = 2π/3 for all point on the arc. Then the required point P is the 2nd point—apart from the point B— where these 2 arcs meet.) Suppose that P minimizes AP + BP + CP. Keep CP fixed, allowing P to vary on a circle centred on C. Draw the tangent t to this circle at P. A small variation dP of P along the tangent t must leave AP +BP unchanged, to the first order in dP. It follows that P must be the point on t minimizing AP + BP. But by the Law of Reflection, this will occur when AP and BP make the same angle θ with t. (To see this, let B′ be the reflection of B in t. Then

AP + BP = AP + P B′

will be minimized when AP B′ is a straight line.) But now

AP̂C = θ + \frac{π}{2} = BP̂C.

Thus at the minimizing point,

AP̂C = BP̂C.

By the same argument with B in place of C,

AP̂B = CP̂B.

Hence all 3 angles AP̂B, BP̂C, CP̂A are equal; and since they add up to 2π (360^{∘}), each must be equal to 2π/3 (120^{∘}).

(b) The point minimizing AP^{2}+BP^{2}+CP^{2} is the centroid G of ABC. For suppose Q is the minimal point. Let A′ be mid-point of BC. Then

AQ^{2} + BQ^{2} = 2A′Q^{2} + 2A′B^{2}.

So we have to minimize

2A′Q^{2} + QA^{2}.

Evidently this will be minimal when AQA′ lie in a straight line. Thus Q must lie on the median AA′. Similarly it must lie on the other 2 medians. Hence it lies at the centroid G of ABC.

6. Does there exist a map f : ℤ → ℤ (where ℤ is the set of integers) such

that

f(f(x)) = x^{2}

for all x ∈ ℤ?

Answer: The answer is Yes.

Note that if we set

s(x) = x^{2}

then

f^{2} = s ⟹ sf = fs,

ie

f(x^{2}) = f(x)^{2}.

In particular,

f(0)^{2} = f(0), f(1)^{2} = f(1).

It follows that either

f(0) = 0, f(1) = 1 or f(0) = 1, f(1) = 0.

More generally, if

f(a) = b

then

f(b) = a^{2}, f(a^{2}) = b^{2}, f(b^{2}) = a^{3}, ….

Let us divide the integers n > 1 into chains

C(r) = {r, r^{2}, r^{4}, r^{8}, … }.

Thus ℕ \ {0, 1} is partitioned into

C(2), C(3), C(5), C(6), …,

with a chain C(r) starting with each non-square r. Divide the chains into pairs (C(2), C(3)), (C(5), C(6)), … Suppose C(r), C(s) is one pair. Then we can set

f(r^{i}) = s^{i}, f(s^{i}) = r^{i+1}.

We can extend the definition to ℤ by setting

f(−n) = f(n).

7. Suppose x, y are positive integers. Show that if

\frac{x^{2} + y^{2}}{xy + 1}

is an integer then it is a perfect square. Answer: Let

\frac{x^{2} + y^{2}}{xy + 1} = m.

Then

x^{2} − mxy + y^{2} − m = 0.

We can regard this as a quadratic equation for x, with y fixed. Since one root x is an integer, so is the other root x′, say; for

x + x′ = my.

Also

xx′ = y^{2} − m,

from which it follows that

x > y ⟹ x′ < y.

But we can also regard the equation as a quadratic equation for y; and in the same way this gives a second solution (x, y′) for which

y > x ⟹ y′ < x.

Thus we get a sequence of solutions, say

(x, y) = (x_{0}, y_{0}), (x_{1}, y_{0}), (x_{1}, y_{1}), …

with decreasing xy. This must end with x = 0 or y = 0, in which case it is clear that m is a square.

8. Show that every rational number x ∈ (0, 1) can be represented uniquely

in the form

x = \frac{a_{1}}{1!} + \frac{a_{2}}{2!} + ... + \frac{a_{k}}{k!} ,

where a_{1}, …, a_{k} are integers with 0 ≤ a_{i} < i for 1 ≤ i ≤ k.

Answer: Notice that a_{1} = 0, since 0 ≤ 1_{1} < 1.

Let

a_{2} = [2x],

and let

x_{2} = 2x − a_{2}.

Then

0 ≤ a_{2} < 2,

and

0 ≤ x_{2} < 1.

Let

a_{3} = [3x_{2}],

and let

x_{3} = 3x_{2} − a_{3}.

Then

0 ≤ a_{3} < 3,

and

0 ≤ x_{3} < 1.

Continuing in this way, the process will end if and when

x_{k+1} = 0.

It is easy to see that this will happen when

k!x ∈ ℕ,

which must be true for some k.

9. What is the greatest number of parts into which the plane can be divided by n straight lines?

Answer: One line divides the plane into 2 parts; 2 lines divides it into 4 (assuming they are not parallel).

Suppose n lines divide the plane into N(n) parts. If now we add a new line then it will cut the existing lines in at most n points, and there will in fact be exactly n new points if the line is not parallel to any of the existing lines and does not go through any of the existing intersection points.

This will create n + 1 new regions. Hence

N(n + 1) = N(n) + n + 1.

It follows that

N(n) = 2 + 2 + 3 + ⋯ + n

= 1 + \frac{1}{2}n(n + 1)

= \frac{n^{2} + n + 2}{2}.

10. Three points A, B, C are chosen at random on the circumference of a circle. What is the probability that the centre of the circle lies inside ABC?

Answer: Suppose the angle subtended by AB at the centre is θ. Then C must lie on an arc subtending the same angle at the centre. (In fact C must lie in the reflection of the arc AB in the centre. The probability of this is θ/2π. Thus the probability that the centre lies in ABC is

p = \frac{1}{π} ∫_{0}^{π} \frac{θ}{2π} dθ

= \frac{1}{2π^{2}} [\frac{θ^{2}}{2} ]_{0}^{π}

= \frac{1}{4}.

11. For which real numbers x does the sequence

x, sin x, sin(sin x), sin(sin(sin x)), …

converge?

Answer: If the sequence converges to c then

sin c = c,

to which the only solution is c = 0. So if the sequence converges, it converges to 0.

Suppose sin x ≥ 0. Then

0 ≤ sin x ≤ 1.

But sin x ≤ x for 0 ≤ xπ/2. It follows that the sequence is decreasing if x ≥ 0, and so is convergent.

Similarly if sin x < 0 then

\frac{sin x}{x} < 1;

so the sequence is increasing, and again is convergent.

12. A circular hole of diameter 1 is drilled through the centre of a sphere of radius 1. What is the surface area of the drilled sphere?

Answer: Let

θ = AÔP,

where O is the centre of the sphere, A is the point on the sphere at the centre of the hole, and P is a point on the sphere on the edge of the hole. Then

sin θ = \frac{1}{2},

and so

θ = \frac{π}{6} .

The length of the cylinder removed is

2 cos θ = \sqrt{3};

so its surface area is

2πrh = \sqrt{3}π.

Recall a famous theorem from the Ancient Greeks, that the area of a section of a sphere cut out by two parallel planes is equal to the area cut out on the circumscribed cylinder perpendicular to the planes. It follows from this that the surface area of each cap removed from the sphere is

2π(1 − cos θ) = (2 − \sqrt{3})π.

The area of the sphere is 4π. Hence the surface area of the drilled sphere is

4π − 2(2 − \sqrt{3})π + \sqrt{3}π = 3\sqrt{3}π.