Irish Intervarsity Mathematics Competition 2008

National University of Ireland, Maynooth

11.00–14.00 Saturday 19^{th} April 2008

1. Consider a regular n-gon inscribed inside a circle of radius 1. Each of the vertices of the n-gon lies on the circle. Draw a line between each pair of the n vertices. Prove that the sum of the squares of the lengths of these lines in n^{2}.

Answer: Let ω = e^{2π/n}. Then we can take the vertices of the n-gon to be

ω^{i} (0 ≤ i ≤ n − 1).

The square of the length of the line joining ω^{i}, ω^{j} is

|ω^{i} − ω^{j}|^{2} = (ω^{i} − ω^{j})(ω^{−i} − ω^{−j})
= 2 − (ω^{i−j} + ω^{j−i}).

If we sum over 0 ≤ i ≤ n − 1, 0 ≤ j ≤ n − 1 we will get twice the required sum (as the line joining ω^{i}, ω^{j} will occur twice). Also ω^{i−j} will take each of the values 1, ω, …, ω^{n−1} n times. Hence the sum will be

2n^{2} − 2n(1 + ω + ⋯ + ω^{n−1}) = 2n^{2}.

We conclude that the required sum is n^{2}.

2. There are 63 coins, all identical in appearance, and all identical in weight except that one coin is slightly heavier than the others.

Answer: Number the coins 1–63. Write each number to base 4, n = abc.

For the first weighing, divide the coins according to the first digit: 15 coins starting with 0 (as there is no coin 000), and 16 starting with 1,2 and 3.

Weigh the last 3 sets against one another. That will determine the first digit of the heavy coin.

Do the same with second and third digits. That will determine all the digits of the the heavy coin.

3. Given positive numbers a_{1} ≥ a_{2} ≥ a_{3}, b_{1} ≥ b_{2} ≥ b_{3} and c_{1} ≥ c_{2} ≥ c_{3}, and three permutations α, β, γ of the set {1, 2, 3}, prove that

a_{1}b_{1}c_{1} + a_{2}b_{2}c_{2} + a_{3}b_{3}c_{3} ≥ a_{α(1)}b_{β(1)}c_{γ(1)} + a_{α(2)}b_{β(2)}c_{γ(2)} + a_{α(3)}b_{β(3)}c_{γ(3)}.

Answer: We may suppose (for simplicity) that

a_{1} > a_{2} > a_{3}, b_{1} > b_{2} > b_{3}, c_{1} > c_{2} > c_{3},

since the given result follows from this by continuity.

We may also suppose (re-arranging the terms on the right if necessary) that α is the identity permutation, so that the right hand reads

a_{1}b_{β(1)}c_{γ(1)} + a_{2}b_{β(2)}c_{γ(2)} + a_{3}b_{β(3)}c_{γ(3)}.

Let us suppose β, γ chosen so that the right-hand side is maximized.

Suppose i < j; and suppose

β(i) < β(j) but γ(i) > γ(j).

Then swapping c_{γ(i)} with c_{γ(j)} will increase the sum by

(c_{γ(j)} − c_{γ(i)})(a_{i}b_{β(i)} − a_{j}b_{β(j)}).

Thus

β(i) < β(j) ⟹ γ(i) < γ(j).

Similarly

γ(i) < γ(j) ⟹ β(i) < β(j).

On the other hand, if i < j but

β(i) > β(j) and γ(i) > γ(j),

then the sum will be increased if we swap b_{γ(i)}c_{γ(i)} with b_{γ(j)}c_{γ(j)}.

We conclude that

i < j ⟹ β(i) < β(j) and γ(i) < γ(j).

Thus β and γ are both the identity permutation, and the result follows.

4. Let F (n) denote the usual Fibonacci sequence, which is defined by the properties F (1) = F (2) = 1 and F (n + 2) = F (n + 1) + F (n) for n > 0. Let (a(n)) denote the iterated Fibonacci sequence, which is given by the equation a(n) = F (F (n)) for each n > 0. Prove that a(n) is a multiple of 144 whenever a(n) is a multiple of 14.

Answer: Note that for any modulus m, F (n) mod m will be a recurring sequence.

Taking m = 2 we have

1, 1, 0, 1, 1, 0, 1, ….

Thus

2 | F (n) ⟺ 3 | n.

Taking m = 3 we have

1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, ….

Thus

3 | F (n) ⟺ 4 | n.

We deduce that

2 | a(n) ⟺ 4 | n.

Taking m = 7 we have

1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, 0, 1, 1, ….

Thus

7 | F (n) ⟺ 8 | n.

Taking m = 8 we have

1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, 1, 1, …

Thus

8 | F (n) ⟺ 6 | n.

We deduce that

7 | a(n) ⟺ 6 | n.

Hence

14 | a(n) ⟺ 12 | n.

So we have to show that

12 | n ⟹ 2^{4}3^{2} | a(n).

Taking m = 16 we have

1, 1, 2, 3, 5, 8, 13, 5, 2, 7, 9, 0, 9, 9, ….

We see now that once we get a 0, we will get the same sequence multiplied (in this case) by 9, and then by 9^{2} = 1 mod 16. Hence

16 | F (n) ⟺ 12 | n.

Taking m = 9 we have

1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 0, 8, 8, …

Again, we will get the same sequence multiplied by 8, and then by 8^{2} = 1 mod 9. Hence

9 | F (n) ⟺ 12 | n.

We conclude that

14 | a(n) ⟹ 12 | n ⟹ 144 | a(n).

5. Take a positive integer N that ends in the digit 2. Move the 2 to the beginning of the number, and subtract 1 to get a new number, M. For example, if N = 52 then we move the 2 to the beginning of N to get 25, and then subtract 1 to obtain M = 24. What is the smallest value of N such that M = 2N?

Answer: Suppose N has r digits. We have

N = 10a + 2,

where a is the number formed by removing the last digit. Then

M = 2 · 10^{r} + a.

Hence

2 · 10^{r} + a − 1 = 2(10a + 2),

ie

19a = 2 · 10^{r} − 5.

It follows that

2 · 10^{r} ≡ 5 mod 19.

Multiplying by 10, this is equivalent to

10^{r} ≡ 12 mod 19.

Now

10, 10^{2}, 10^{3}, ⋯ ≡ 10, 5, 12, … mod 19.

We conclude that the smallest possible value of r is 3. (The general value is 3 mod 18.)

Taking r = 3, we have

19a = 2 · 10^{3} − 5,

ie

a = 1995/19 = 105.

We conclude that the smallest solution is

N = 1052, N = 2105.

6. For n = 1, 2, … let

a_{n} = n(n + 1), b_{n} = n + 1.

What is the value of the convergent sequence

\frac{a_{1}}{b_{1}} , \frac{a_{1}}{b_{1} + \frac{a_{2}}{b_{2}}} , \frac{a_{1}}{b_{1} + _{\frac{a_{2}}{b_{2}+ \frac{a_{3}}{b_{3}}}}} , …?

Answer: Let the nth convergent (expressed as a fraction without reducing to simple terms) be p_{n}/q_{n}. Thus

p_{1} = a_{1}, q_{1} = b_{1},
p_{2} = a_{1}b_{2}, q_{2} = b_{1}b_{2} + a_{2}.

It follows by induction, on substituting b_{n} + a_{n+1}/b_{n+1} for b_{n}, that

p_{n} = b_{n}p_{n−1} + a_{n}p_{n−2},
q_{n} = b_{n}q_{n−1} + a_{n}q_{n−2}.

With these formulae, we can even go back to

p_{0} = 0, q_{0} = 1,
p_{−1} = 1, q_{−1} = 0.

In our case we see that the sequences p_{n}, q_{n} both satisfy the recurrence relation

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

Dividing by (n + 1)! this can be written

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

Thus if we set

z_{n} = \frac{x_{n}}{(n + 1)!},

then z_{n} satisfies the linear recurrence relation

z_{n} = z_{n−1} + z_{n−2}

(like the Fibonnaci numbers).

The solution to this is

z_{n} = Aλ^{n} + Bμ^{n},

where λ, μ are the roots of

t^{2} − t − 1 = 0,

ie

λ, μ = (1 ± \sqrt{5})/2.

For z_{n} = p_{n}/(n + 1)!, taking n = 0, −1 and noting that λμ = −1,

A + B = 0, −Aμ − Bλ = 1.

Thus

A(λ − μ) = 1,

ie

A = 1/\sqrt{5}, B = −1/\sqrt{5}.

Similarly, for z_{n} = q_{n}/(n + 1)!, taking n = 0, −1 gives

A + B = 1, −Aμ − Bλ = 0.

Thus

A(1 − μ^{2}) = 1,

ie

−Aμ = 1,

ie

A = λ, B = μ.

So finally, since λ^{n} → ∞, μ^{n} → 0, and the factors 1/(n + 1)! cancel out,

\frac{p_{n}}{q_{n}} → \frac{1/\sqrt{5}}{λ}
= −μ/\sqrt{5}
= (5 − \sqrt{5})/10.

7. Let a triangle ABC have sides of length |AB| = 5, |BC| = 6, |CA| = 7, and let the lengths of the perpendiculars from a point P inside the triangle to the sides AB, BC and CA be x, y and z, respectively. Find the minimum value of the sum x^{2} + y^{2} + z^{2}.

Answer: If Δ is the area of the triangle then

Δ^{2} = s(s − a)(s − b)(s − c)
= 9 · 4 · 3 · 2
= 2^{3}3^{3}.

Hence

5x + 6y + 7z = 2Δ = 12\sqrt{6}.

Thus we have to minimize

f(x, y, z) = x^{2} + y^{2} + z^{2}

subject to the constraint

g(x, y, z) = 5x + 6y + 7z − 2Δ = 0.

Applying the method of Lagrange multipliers, we have to solve

2x = 5λ, 2y = 6λ, 2z = 7λ, g(x, y, z) = 0.

These give

5^{2}λ/2 + 6^{2}λ/2 + 7^{2}λ/2 = 24\sqrt{6}.

ie

110λ = 48\sqrt{6}.

ie

λ = \frac{24}{55}\sqrt{6}.

Thus the minimal point is

P = (x, y, z) = \frac{λ}{2}(5, 6, 7),

and the minimal value of x^{2} + y^{2} + z^{2} is

\frac{λ^{2}}{4} (5^{2} + 6^{2} + 7^{2}) = \frac{24^{2} · 6 · 110}{55^{2} · 6 · 4}

= \frac{288}{55}.

8. Let (a_{n}) be a sequence of non-negative integers such that

a_{n+2} = \binom{a_{n+1}}{a_{n}},

where

\binom{m}{k} = \begin{cases}\frac{m!}{k!(m−k)!} & if m ≥ k \\ 0 otherwise \end{cases}

Answer: If a_{n} = 0 for some n then the sequence continues

\begin{cases}a_{n+1}, 1, 1, … if a_{n+1} ≤ 1 \\ a_{n+1}, 1, 0, 0, 1, 1, … if a_{n+1} ≥ 2 \end{cases}

So we may assume that a_{n} ≠ 0. If a_{n} = 1 for some n then the sequence continues

\begin{cases}a_{n+1}, a_{n+1}, 1, 1, … if a_{n+1} ≤ 1 \\ a_{n+1}, a_{n+1}, 1, 0, … if a_{n+1} ≥ 2 \end{cases}

So we may assume that a_{n} ≠ 1. In particular 2 ≤ a_{1} and a_{2} > a_{1}. If a_{2} = a_{1} + 1 then the sequence continues

a_{1}, a_{2}, a_{2}, 1, 0, …

So we may assume that 2 ≤ a_{1} ≤ a_{2} − 2. Suppose this is so. Recall that the binomial coefficients \binom{n}{r} increase as r runs from 0 to [n/2] and then decrease until r = n. Hence

a_{3} = \binom{a_{2}}{a_{1}} ≥ \binom{a_{2}}{2} = \frac{1}{2}a_{2}(a_{2} − 1) ≥ \frac{3}{2}a_{2}

since a_{2} ≥ 4. We show by induction that

a_{n+1} ≥ \frac{3}{2}a_{n}

for all n. If this is true for r ≤ n then certainly 2 ≤ a_{r} ≤ a_{r+1} − 2 for ≤ n. Hence

a_{n+2} = \binom{a_{n+1}}{a_{n}} ≥ \binom{a_{n+1}}{2} ≥ \frac{3}{2}a_{n+1}.

Hence the sequence tends to infinity.

9. Show that there does not exist a differentiable function f : ℝ → ℝ which satisfies the following equation for all real values x:

f′(x) ≥ 1 + |f(x)|^{2}.

Answer: Evidently f(x) is monotone increasing from −∞ to +∞ (since f′(x) ≥ 1 for all x). Hence

f(c) = 0

for some c, and

x > c ⟹ f(x) > 0.

Let g(x) be the function defined for x ≥ c by g(c) = 0 and

g′(x) = \frac{1}{2}(1 + g(x)^{2}).

Thus

\frac{g′(x)}{1 + g(x)^{2}} = 2.

Integrating,

tan^{−1}(g(x)) = 2x + C,

ie

g(x) = tan(2x + C).

Since g(c) = 0 we can take 2c + C = 0, ie

g(x) = tan(2(x − c)).

Hence g(x) → ∞ as x → c + π.

But it is easy to see that

g(x) ≤ f(x)

for x ≥ c.

This is certainly true for x slightly > c, since g′(c) = 1/2 < f′(c). Suppose the two graphs cross at x_{0} > c. On applying the Mean Value Theorem to f(x) − g(x) on [c, x_{0}] it would follow that f′(ξ) = g′(ξ) for some ξ ∈ (c, x_{0}), which we have seen is not possible.

We conclude that f(x) → ∞ for some x < c+π, contrary to hypothesis.

10. In a room there are 2008 bulbs and 2008 buttons, and both are numbered from 1 to 2008. For each integer 1 ≤ i ≤ 2008, pressing Button i changes the on or off status of Bulb i and one other bulb (the same bulb each time). Assuming that all bulbs are initially off, prove that by pressing the appropriate combination of buttons we can turn on at least 1340 of them simultaneously on. Prove also that if the effects of the buttons are chosen appropriately, 1340 is the largest number of bulbs that can be simultaneously on.

Answer: Let S = {1, 2, …, 2008}, and let

f : S → S

be the map defined by the property that pressing Switch i turns on Bulbs i and f(i).

We do the last part of the question first. Partition S into 669 triplets, leaving one element over. For each triplet {a, b, c} let

f(a) = b, f(b) = c, f(c) = a.

Then it is clear that whichever of the switches a, b, c is or are on, at most 2 of the bulbs will be on.

This ignores the singlet {d}. Set f(d) = e. Then it is clear that all the bulbs in the triplet containing e can be on at the same time.

Thus the maximum number of bulbs on is

668 · 2 + 3 + 1 = 1340.

Turning to the first part of the question, let

S_{r} = f^{r}(S)

(where eg f^{2}(S) = f(f(S))).

Then

S = S_{0} ⊃ S_{1} ⊃ S_{2} ⊃ · · · .

The sequence must become stationary: say

S_{n} = S_{n+1} = · · · .

Let T_{r} = S_{r} \ S_{r+1}.

Then

f(T_{r}) = T_{r+1}.

Now turn on the switches in T_{0}, T_{2}, T_{4}, … and leave off those in T_{1}, T_{3}, T_{5}, . . ..

Suppose i ∈ T_{2r+1}. Consider the set

X(i) = {j ∈ T_{2r} : f(j) = i}.

Then X(i) ≠ ∅. Suppose there are m numbers in X(i). Then bulb i will be off or on according as m is even or odd.

Now consider the union

Y (i) = X(i) ∪ {i},

associating the switches in X(i) with switch i. In this set there are m + 1 bulbs out of m + 1 on if m is odd, and m out of m + 1 on if m is even.

In all cases the proportion is ≥ 2/3. Hence the overall number of bulbs on is

≥ \frac{2}{3} × 2008 = 1339\frac{2}{3}.

Hence at least 1340 bulbs are on.