Irish Intervarsity Mathematics Competition 2003

University College Dublin

Time allowed: Three hours

1. Let

f(x) = x^{3} + Ax^{2} + Bx + C,

where A, B, C are integers. Suppose the roots of f(x) = 0 (in the field of complex numbers) are α, β, γ. Prove that if

|α| = |β| = |γ| = 1

then

f(x) | (x^{12} − 1)^{3}.

Answer: One or three of the roots must be real. But if α ∈ ℝ and |α| = 1 then α = ±1.

If the three roots are ±1 then the result follows, since ±1 are roots of x^{12} − 1.

So we may assume that one root, say α, is ±1, and the other two are complex conjugates e^{±θ}. Since α + β + γ = −A is an integer, so is β + γ = 2 cos θ. Thus either β + γ = 0, in which case β, γ = ±i; or else β + γ = ±1, in which case β, γ = ω, ω^{2} or − ω, −ω^{2}, where ω = e^{2πi/3}.

Since ±i, ±ω, ±ω^{2} are all roots of x^{12} − 1, the result follows.

2. Let n be a positive integer. Prove that when written in decimal form (in base 10),

(\sqrt{17} + 4)^{2n+1}

has at least n zeroes following the decimal point.

Answer: Let

x = \sqrt{17} + 4, y = \sqrt{17} − 4.

Then

xy = 1;

while

x^{2n+1} − y^{2n+1} ∈ ℤ,

since the terms involving odd powers of \sqrt{17} cancel out. It follows that the part of x^{2n+1} after the decimal point is y^{2n+1}. This gives the result, since x > 8 and so

y^{2n+1} < 64^{−n} < 10^{−n}.

3. Find all integers n for which

n^{4} − 16n^{3} + 86n^{2} − 176n + 169

is the square of an integer. Answer: Let the given expression be f(n), and let

g(n, c) = n^{2} − 8n + c,

for integers c. Then

g(n, c)^{2} = n^{4} − 16n^{3} + (64 + 2c)n^{2} − 16cn + c^{2}.

Thus

f(n) = g(n, 11)^{2} + 48,
= g(n, 12)^{2} − 2n^{2} + 16n + 25,
= g(n, 13)^{2} − 4n^{2} + 32n.

It follows that if f(n) = m^{2} then m > g(n, 11). But m ≤ g(n, 13) = g(n, 11) + 2 unless

4n^{2} ≤ 32n,

ie

0 ≤ n ≤ 8.

If n = 0 or n = 8 then f(n) = g(n, 13)^{2}. So we need only consider 1 ≤ n ≤ 7. We have

g(n, 11) = (n − 4)^{2} − 5.

Thus

f(1) = g(1, 11)^{2} + 48 = 4^{2} + 48 = 64 = 8^{2},
f(2) = g(2, 11)^{2} + 48 = (−1)^{2} + 48 = 49 = 7^{2},
f(3) = g(3, 11)^{2} + 48 = (−4)^{2} + 48 = 64 = 8^{2},
f(4) = g(4, 11)^{2} + 48 = (−5)^{2} + 48 = 73,
f(5) = g(5, 11)^{2} + 48 = (−4)^{2} + 48 = 64 = 8^{2},
f(6) = g(6, 11)^{2} + 48 = (−1)^{2} + 48 = 49 = 7^{2},
f(7) = g(7, 11)^{2} + 48 = 4^{2} + 48 = 64 = 8^{2}.

Finally, if f(n) is a square for n outside the range [0, 8] then f(n) = g(n, 12)^{2}, in which case

2n^{2} − 16n + 25 = 0,

which is impossible since the first two terms are even while the last is odd.

We conclude that f(n) is a square if and only if n ∈ {0, 1, 2, 3, 5, 6, 7, 8}.

4. Consider the sequence

1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, …

in which each positive integer k is repeated k times. Prove that its n^{th} term is

[\frac{1 + \sqrt{8n − 7}}{2}] ,

where [x] denotes the greatest integer not exceeding x.

Answer: Let the nth number in the sequence be a_{n}.

The first n for which a_{n} = k is

n = 1 + 2 + ⋯ + (k − 1) + 1 = \frac{k(k − 1)}{2} + 1 = \frac{k^{2} − k + 2}{2}.

The function

f(x) = \frac{x^{2} − x + 2}{2}

is monotone increasing for x ≥ 1. Thus

n = f(x)

for a unique x = x(n) ≥ 1; and a_{n} = k if

k ≤ x(n) < k + 1,

ie

a_{n} = [x(n)].

But x(n) is the solution of

x^{2} − x + 2 = 2n.

Thus

a_{n} = [\frac{1 + \sqrt{1 − 4(2 − 2n)}}{2}]

= [\frac{1 + \sqrt{8n − 7}}{2}] .

5. Let ABC be an acute angled triangle and a, b, c the lengths of the sides BC, CA, AB, respectively. Let P be a point inside ABC, and let x, y, z be the lengths P A, P B, P C, respectively. Prove that

(x + y + z)^{2} ≥ \frac{a^{2} + b^{2} + c^{2}}{2} .

Answer: We have

x + y > c, y + z > b, z + x > a.

Thus

(y + z)^{2} + (z + x)^{2} + (x + y)^{2} = 2(x^{2} + y^{2} + z^{2} + yz + zx + xy)
> a^{2} + b^{2} + c^{2}.

Hence

2(x + y + z)^{2} = 2(x^{2} + y^{2} + z^{2} + 2(yz + zx + xy))
> a^{2} + b^{2} + c^{2},

ie

(x + y + z)^{2} > (a^{2} + b^{2} + c^{2})/2.

6. Let ABCD be a convex quadrilateral with the lengths AB = AC, AD = CD and angles BÂC = 20^{∘}, AD̂C = 100^{∘}. Prove that the lengths AB = BC + CD.

Answer: Since the triangle ABC is isosceles,

AB̂C = AĈB = 80^{∘}.

Similarly, since the triangle DAC is isosceles,

DÂC = DĈA = 40^{∘}.

From the triangle ABC,

\frac{BC}{sin 20} = \frac{AB}{sin 80}.

Thus

BC = \frac{sin 20}{sin 80}AB.

Similarly, from the triangle ACD,

\frac{AC}{sin 100} = \frac{CD}{sin 40}.

Thus

CD = \frac{sin 40}{sin 100}AC = \frac{sin40}{sin80}AB.

Accordingly, we have to show that

\frac{sin 20}{sin 80} + \frac{sin 40}{sin 80} = 1,

ie

sin 20 + sin 40 = sin 80.

But

sin 20 + sin 40 = sin(30 − 10) + sin(30 + 10)

= 2 sin 30 cos 10 = cos 10 = sin 80,

as required.

7. Let S be a set of 30 positive integers less than 100. Prove that there exists a nonempty subset T of S such that the product of the elements of T is the square of an integer.

Answer: If we take the numbers {1, 2, …, 100} modulo squares we obtain an abelian group A, in which eg ¯3 · ¯6 = ¯2, The elements of A are all of order 2, and A is generated by the elements p̄ defined by primes p. There are 25 primes p ≤ 100, so

A = C_{2}^{25}.

We can regard A as a 25-dimensional vector space over the 2-element field 𝔽_{2}. If s_{1}, …, s_{r} ∈ S then

s̄_{1} + ⋯ + s̄_{r} = 0 ⟺ s_{1} ⋯ s_{r} is a square.

The 30 elements

{s̄: s ∈ S}

must be linearly dependent in the vector space A, ie there is some relation

s̄_{1} + ⋯ + s̄_{r} = 0

But then the product

s_{1} ⋯ s_{r}

is a square.

8. Let

f(x) = x^{5} + ax^{4} + bx^{3} + cx^{2} + dx + e,

where a, b, c, d, e are integers, and suppose that f(x) = 0 has no integer roots. Suppose also that f(x) = 0 has roots α, β (in the field of complex numbers) with α + β an integer. Show that αβ is an integer.

Answer: Suppose

α + β = n.

Consider the factorisation of f(x) into irreducible polynomials over the rationals ℚ. We know that any such factorisation is in fact a factorisation into monic polynomials over ℤ. Since f(x) has no integral root it cannot have a factor of degree 1. Thus either f(x) is irreducible, or else it factorises into 2 irreducible polynomials, of degrees 2 and 3.

Suppose first that f(x) is irreducible. Then β = n − α is a root of f(n − x), as well as of f(x). It follows that

f(n − x) = −f(x).

Thus from the coefficients of x^{4},

5n + a = −a,

ie

5n = 2a.

In particular, n is even.

The roots of f(x) must divide into pairs {θ, n−θ} with at least one root satisfying θ = n − θ. But that is impossible, since f(x) has no integral root. It follows that f(x) cannot be irreducible.

Thus f(x) factorises, say

f(x) = g(x)h(x),

where α is a root of g(x).

As before, β = n − α is a root of g(n − x), as well as of f(x). Thus g(n−x) is (to within a factor ±1) either g(x) or h(x). Since deg g(x) ≠ deg h(x),

g(n − x) = ±g(x).

Suppose first that g(x) is cubic, say

g(x) = x^{3} + Ax^{2} + Bx + C.

If the third root is γ then

α + β + γ = −A ⟹ γ = −(A + n),

giving an integral root of f(x), contrary to assumption.

Hence g(x) is quadratic, say

g(x) = x^{2} + Bx + C.

Then αβ = C is integral, as required.

9. Let x be a real number with 0 < x < 1. Let {a_{n}} be a sequence of positive real numbers. Prove that the inequality

1 + xa_{n} ≥ x^{2}a_{n−1}

holds for infinitely many positive integers n.

Answer: Suppose to the contrary that

a_{n} < xa_{n−1} − \frac{1}{x}

for all sufficiently large n, say n ≥ N. This implies in particular that a_{n} is decreasing for n ≥ N. Hence a_{n} converges to a limit ℓ ≥ 0, satisfying

ℓ ≤ xℓ − \frac{1}{x}.

But this implies that

(1 − x)ℓ ≤ −\frac{1}{x} < 0 ⟹ ℓ < 0,

which is impossible since a_{n} ≥ 0.

10. Find the least positive integer n for which

m^{n} − 1 is divisible by 10^{2003}

for all integers m with greatest common divisor gcd(m, 10) = 1. Answer: We have to find n such that

m^{n} ≡ 1 mod 2^{2003}

and

m^{n} ≡ 1 mod 5^{2003}.

The group (ℤ/2^{n})^{×}, ie the group of odd numbers modulo 2^{n}, contains

ϕ(2^{n}) = 2^{n−1}

elements. Thus the order of any odd number in this group is 2^{r} for some r. It is not hard to show that if n ≥ 2,

(ℤ/2^{n})^{×} ≅ ℤ/(2) × ℤ/(2^{n−2}).

Thus every odd number has order dividing 2^{n−2}, and some odd numbers have this order.

The group (ℤ/5^{n})^{×}, ie the group of numbers coprime to 5 modulo 5^{n}, contains

ϕ(5^{n}) = 4 · 5^{n−1}

elements. is 2^{r} for some r. Again, it is not hard to see that this group is cyclic. Thus every number coprime to 5 has order dividing 4 · 5^{n−1}, and some such numbers have this order.

It follows that the least number n such that all m coprime to 10 satisfy

m^{n} ≡ 1 mod 10^{2003}

is

n = lcm(2^{2000}, 4 · 5^{2001})
= 2^{2000}5^{2001}
= 5 · 10^{2000}.