30th British Mathematical Olympiad 1994 Problems

30th British Mathematical Olympiad 1994 Problems

1.  Find the smallest integer n > 1 such that (1² + 2² + 3² + ... + n²)/n is a square.

2.  How many incongruent triangles have integer sides and perimeter 1994?

3.  A, P, Q, R, S are distinct points on a circle such that ∠PAQ = ∠QAR = ∠RAS. Show that AR(AP + AR) = AQ(AQ + AS).

4.  How many perfect squares are there mod 2ⁿ?

Solutions

Problem 1

Find the smallest integer n > 1 such that (1² + 2² + 3² + ... + n²)/n is a square.

Solution

We want (n+1)(2n+1)/6 = m². But n+1 and 2n+1 are coprime. Also 2n+1 is odd, so we must have either (1) 2n+1 = a², n+1 = 6b² or (2) 2n+1 = 3a², n+1 = 2b². But 2n+1 = 2(n+1) - 1, so in case (1) we have a² + 1 = 12b². But squares are 0 or 1 mod 3, so a² + 1 is 1 or 2 mod 3, whereas 12b² is 0 mod 3. So case (1) is not possible.

In case (2) we have 4b² - 1 = 3a², so either 2b + 1 = c², 2b - 1 = 3d² or 2b + 1 = 3d², 2b - 1 = c², so c² = 3d² ± 2. We now try successively, d = 1, 2, ... . d = 1 gives c = 1, b = 1, n = 1. But we are given n > 1. d = 2 fails, d = 3 gives a = 15, b = 13, n = 337.

Checking: (337 + 1)(2.337 + 1)/6 = 169.225 = (13.15)². 

Problem 2

How many incongruent triangles have integer sides and perimeter 1994?

Solution

Answer: 82834.

We assume a triangle is not allowed to be degenerate with zero area. Let t_n be the number of incongruent triangles with perimeter n and integer sides. Calculating the first few terms, we find t₁ = t₂ = 0, t₃ = 1 (111), t₄ = 0, t₅ = 1 (122), t₆ = 1 (222), t₇ = 2 (133, 223), t₈ = 1 (233), t₉ = 3 (144, 234, 333).

Suppose the triangle has sides a, b, c with a ≤ b ≤ c. The only restrictions are that a > 0 and a + b > c. Now consider a-1, b-1, c-1. This will be a triangle with perimeter 3 shorter unless a = 1 or a + b = c + 1. But if a = 1, then we must have b = c and hence a + b = c + 1. So a-1, b-1, c-1 is either a triangle or a degenerate triangle. Conversely, if a-1, b-1, c-1 is a triangle or a degenerate triangle, then a, b, c is a triangle. So if we put d_n as the number of degenerate triangles with perimeter n (including those with shortest side zero), then t_n+3 = t_n + d_n.

Obviously d_odd = 0. d_2n = the number of pairs a ≤ b with a + b = n, which is just [n/2] + 1 (for example 4 = 0 + 4 = 1 + 3 = 2 + 2). So we have t₁₉₉₄ = t₁₉₉₁ = t₁₉₈₈ + 498 = t₁₉₈₅ + 498 = t₁₉₈₂ + 496 + 498 = t₁₉₇₉ + 496 + 498 = t₁₉₇₆ + 495 + 496 + 498 = ... = 1 + 3 + 4 + 6 + 7 + ... + 496 + 498. There are 498 x 2/3 terms, which can be grouped into pairs with sum 499 (1 and 498, 3 and 496 etc), so the sum is 166 x 499.

Alternative solution

Assume a ≤ b ≤ c. We must have c < 1994/2, so the largest possible value of c is 996. Also c ≥ 1994/3, so c ≥ 665. If c = 665, then the only solution is a = 664, b = 665. If c = 666, then the solutions are a = 662, b = 666, or a = 663, b = 665, or a = b = 664. Evidently if c is odd, then the number of pairs (a, b) is one greater than for c - 1 (if the smallest and largest possible a for c-1 are h and k, then the largest and smallest for c are h-2 and k-1), but if c is even then the number of pairs is two greater than for c-1 (the largest and smallest are h-2 and k). Hence the total number of possibilities is 1 + 3 + 4 + 6 + 7 + ... + 498 (for c = 996 the possibilities are a = 2 up to a = 499). 

Problem 3

A, P, Q, R, S are distinct points on a circle such that ∠PAQ = ∠QAR = ∠RAS. Show that AR(AP + AR) = AQ(AQ + AS).

Solution

Take X on the ray AQ so that QX = AS, and take Y on the ray AR so that RY = AP. Then we have to show that AQ·AX = AR·AY, so it is sufficient to show that QRYX is cyclic.

We have QR = SR (because they subtend equal angles at A), QX = SA (by construction) and ∠RQX = 180^o - ∠AQR = ∠RSA. So triangles QRX and SRA are congruent. So ∠YRX = ∠RXA + ∠RAX. But ∠RXA = ∠RXQ (same angle) = ∠RAS (congruent triangles). So ∠YRX = ∠RAX + ∠RAS = ∠RAX + ∠QAP (given as equal) = ∠PAR. But RX = AR (QRX and SRA congruent) and RY = AP (by construction). So RYX and APR are congruent. So ∠RYX = ∠APR = ∠AQR = 180^o - ∠RQX. So QRYX is cyclic. 

Problem 4

How many perfect squares are there mod 2ⁿ?

Solution

Answer: n odd (2^n-1 + 5)/3, n even (2^n-1 + 4)/3.

We find the first few:

2: 0, 1

4: 0, 1

8: 0, 1, 4

16: 0, 1, 4, 9

32: 0, 1, 4, 9, 16, 17, 25

64: 0, 1, 4, 9, 16, 17, 25, 33, 36, 41, 49, 57

a² = b² mod 2ⁿ iff (2a)² = (2b)² mod 2ⁿ⁺², so the number of even squares mod 2ⁿ⁺² equals the number of squares mod 2ⁿ. This suggests looking separately at the odd and even squares. Let u_n be the number of odd squares mod 2ⁿ and v_n be the number of even squares mod 2ⁿ.

(2a + 1)² = (2b + 1)² mod 2ⁿ is equivalent to 4a² + 4a = 4b² + 4b mod 2ⁿ, which is equivalent to a² + a = b² + b mod 2^n-2 or (a - b)(a + b + 1) = 0 mod 2^n-2. But a - b and a + b + 1 have sum 2a + 1 which is odd, so they have opposite parity, so either a - b = 0 mod 2^n-2 or (a + b + 1) = 0 mod 2^n-2. Thus just 3 other odd numbers have the same square as (2a + 1), namely (2a + 2^n-1 + 1), -(2a + 1) and -(2a + 2^n-1 + 1). So there are 2^n-3 different odd squares mod 2ⁿ. In other words, v_n = 2^n-3.

Now u_n = u_n-2 + v_n-2 = u_n-4 + v_n-4 + v_n-2 etc. So the total number of squares u_2m + v_2m = v_2m + v_2m-2 + v_2m-4 + ... + v₄ + u₄ = 2^2m-3 + 2^2m-5 + ... + 2 + 2 = 2(4^m-2 + 4^m-3 + ... + 1) + 2 = 2(4^m-1 - 1)/3 + 2 = (2^n-1 + 4)/3.

Similarly, the total number of squares for n odd is (2^n-1 + 5)/4.