19th Canadian Mathematical Olympiad Problems 1987

19th Canadian Mathematical Olympiad Problems 1987

1.  Find all positive integer solutions to n! = a² + b² for n < 14.

2.  Find all the ways in which the number 1987 can be written in another base as a three digit number with the digits having the same sum 25.

3.  ABCD is a parallelogram. X is a point on the side BC such that ACD, ACX and ABX are all isosceles. Find the angles of the parallelogram.

4.  n stationary people each fire a water pistol at the nearest person. They are arranged so that the nearest person is always unique. If n is odd, show that at least one person is not hit. Does one person always escape if n is even?

5.  Show that [√(4n + 1)] = [√(4n + 2)] = [√(4n + 3)] = [√n + √(n + 1)] for all positive integers n. 

Solutions

Problem 1

Find all positive integer solutions to n! = a² + b² for n < 14.

Solution

Answer: 2! = 1² + 1², 6! = 24² + 12².

A necessary condition for N to be the sum of two squares is that N does not have a prime p = 3 mod 4 such that the highest power of p dividing N is odd. Thus for n = 3, 4, 5 the highest power of 3 dividing n! is 3¹. For n = 7, 8, 9, 10, 11, 12, 13 the highest power of 7 dividing n! is 7¹. So in all those cases n! cannot be written as a sum of two squares. Obviously 1! cannot (because the smallest sum of two squares is 2) and we have exhibited 2! and 6! as a sum of two squares.

To prove the criterion, note that if p divides N and N = a² + b² then a² = -b² mod p, so if a and b are not multiples of p, then we can take c such that ac = 1 and get x² = -1 mod p, where x = bc. But if p = 3 mod 4, then (p-1)/2 is odd, so x^p-1 = (-1)^odd = -1 mod p, whereas we know that x^p-1 = 1 mod p for all x not zero mod p. 

Problem 2

Find all the ways in which the number 1987 can be written in another base as a three digit number with the digits having the same sum 25.

Solution

45² = 2025. So any three digit number in base 45 or higher is too big. 12³ = 1728, so any three digit number in base 12 or less is too small. Suppose the base is b and the number has first two digits m and n. Then we have mb² + nb + (25 - m - n) = 1987. So m(b² - 1) + n(b - 1) = 1962 = 18·109. Hence b - 1 divides 18.109. But 109 is prime, so we must have b = 19. We have 1987 = 5·19² + 9·19 + 11 and 5 + 9 + 11 = 25, so b = 19 works. 

Problem 3

ABCD is a parallelogram. X is a point on the side BC such that ACD, ACX and ABX are all isosceles. Find the angles of the parallelogram.

Solution

There are 5 possible configurations. (1) ∠D = 36^o, CA = CD = CX, XB = XA, (2) ∠D = 36^o, DA = DC, AC = AX = BX, (3) ∠D = 36^o, CA = CD, XA = XC, BA = BX, (4) ∠D = 45^o, CD = CA, XC = XA = XB, (5) ∠D = 77 1/7^o, AC = AD, XC = XA, BA = BX.

One just has to go through the various possibilities. In triangle ABX the equal angles could be at A and B, B and X, or X and A. Case 1, ∠XAB = ∠XBA = x. Hence angle D = x, ∠CXA = 2x, ∠XCD = 180^o - x. Now in triangle AXC, the equal angles could be at X and A or various other possibilities. Suppose they are at X and A. Then we get all the angles in terms of x. Now require that ACD is isosceles to get x. Similarly for the other cases. 

Problem 4

n stationary people each fire a water pistol at the nearest person. They are arranged so that the nearest person is always unique. If n is odd, show that at least one person is not hit. Does one person always escape if n is even?

Solution

n odd. Use induction. For n = 3, let the people be A, B, C. Let AB be the shortest side of the triangle. Then A and B shoot each other and so no one shoots C. Suppose it is true for n. Given n+2 people let A, B be the closest pair (or one of them). Then A and B shoot each other. If anyone else shoots A or B, then the victim is hit twice. There are only n+2 shots, so if one person gets hit more than once, then there are at most n shots left between n+1 people, so someone must escape. If no one else shoots at A and B, then by induction one of the remaining n people escapes.

For n even, take isolated pairs of people, then each pair wet each other and no one escapes. On the other hand someone obviously can escape. For example, take everyone close together except for one person - no one shoots at him. 

Problem 5

Show that [√(4n + 1)] = [√(4n + 2)] = [√(4n + 3)] = [√n + √(n + 1)] for all positive integers n.

Solution

Put f(n) = [√n + √(n + 1)]. Obviously f(n) is monotonic increasing. We have f(m² - 1) = 2m - 1 and f(m²) = 2m. Suppose n = m(m+1)-1. Then (√n + √(n + 1))² = 2m(m+1)-1 + 2√( (m(m+1)-1) m(m+1) ) < 2m(m+1) - 1 + 2m(m+1) < (2m+1)². So f(n) = 2m. But if n = m(m+1), then (√n + √(n + 1))² > 2m(m+1)+1 + 2m(m+1) = (2m+1)², so f(n) = 2m+1. Thus f(n) increments by 1 at n = m² and m² + m.

Now for n = m² - 1, 4n+1 = 4m² - 3, ... , 4n+3 = 4m² - 1, so [√(4n + 1)] = [√(4n + 2)] = [√(4n + 3)] = 2m-1. But for n = m², 4n+1 = 4m²+1, 4n+2 = 4m²+2, 4n+3 = 4m²+3, so [√(4n + 1)] = [√(4n + 2)] = [√(4n + 3)] = 2m. Similarly for n = m(m+1)-1, 4n+1 = 4m²+4m-3 = (2m+1)²-4, 4n+2 = (2m+1)²-3, 4n+3 = (2m+1)²-2, so [√(4n + 1)] = [√(4n + 2)] = [√(4n + 3)] = 2m. But for n = m(m+1), 4n+1 = (2m+1)² etc and so [√(4n + 1)] = [√(4n + 2)] = [√(4n + 3)] = 2m+1.

Obviously [√(4n + 1)], [√(4n + 2)], [√(4n + 3)] are all monotonic increasing, so they all equal f(n).