15th USA Mathematical Olympiad 1986 Problems

15th USA Mathematical Olympiad 1986 Problems

1.  Do there exist 14 consecutive positive integers each divisible by a prime less than 13? What about 21 consecutive positive integers each divisible by a prime less than 17?

2.  Five professors attended a lecture. Each fell asleep just twice. For each pair there was a moment when both were asleep. Show that there was a moment when three of them were asleep.

3.  What is the smallest n > 1 for which the average of the first n (non-zero) squares is a square?

4.  A T-square allows you to construct a straight line through two points and a line perpendicular to a given line through a given point. Circles C and C' intersect at X and Y. XY is a diameter of C. P is a point on C' inside C. Using only a T-square, find points Q,R on C such that QR is perpendicular to XY and PQ is perpendicular to PR.

5.  A partition of n is an increasing sequence of integers with sum n. For example, the partitions of 5 are: 1, 1, 1, 1, 1; 1, 1, 1, 2; 1, 1, 3; 1, 4; 5; 1, 2, 2; and 2, 3. If p is a partition, f(p) = the number of 1s in p, and g(p) = the number of distinct integers in the partition. Show that ∑ f(p) = ∑ g(p), where the sum is taken over all partitions of n.

Solution

15th USA Mathematical Olympiad 1986

Problem 1

Do there exist 14 consecutive positive integers each divisible by a prime less than 13? What about 21 consecutive positive integers each divisible by a prime less than 17?

Solution

Answer: no, yes.

There are 7 odd numbers. At most one can be a multiple of 7 and one a multiple of 11. It is only possible to have two of them multiples of 5 if either the largest or smallest is a multiple of 5. But it is only possible to have three of them multiples of 3 if both the largest and the smallest are multiples of 3. So at most four numbers are multiples of 3 or 5. That leaves one odd number unaccounted for.

A little juggling shows that we want the odd numbers to be divisible by: 3, 7, 5, 3, 11, 13, 3, 5, 7, 3 (or the 11 and 13 can be interchanged). We need the 6th odd to be 13 mod 143 to get the 11 and 13 correct, and hence the 1st in the sequence to be 2 mod 143. But the 1st must be even, so it must be 2 mod 286. The 2nd must be divisible by 3, so the 1st must be 2 mod 858. But we need the 4th to be divisible by 7, so the 1st must be 3434 mod 6006. Then the 6th must be divisible by 5, so the 1st must be 9440 mod 30030. Thus an example is 9440, 9441, ... , 9460.

Comment. Essentially the same as ASU 81/19. Problem 2

Five professors attended a lecture. Each fell asleep just twice. For each pair there was a moment when both were asleep. Show that there was a moment when three of them were asleep.

Solution

This is a slightly tricky application of the pigeonhole principle.

For each pair take the first moment when they are both asleep. There are ten pairs, so ten such moments. If two coincide, then we are done because at that moment at least three professors were asleep. So suppose they are all distinct and form a set S. Each such moment must also be one of the 10 occasions when a professor falls asleep. But consider the earliest member of S. Two professors were asleep at that moment so two fell asleep at or before that moment. Thus each of the remaining 9 members of S must be one of the 8 later occasons when a professor fell asleep. So they cannot all be distinct. Contradiction.

---

Problem 3

What is the smallest n > 1 for which the average of the first n (non-zero) squares is a square?

Solution

Answer: 337.

We need 1/6 (n+1)(2n+1) a square. We need n = 6m+1 for it to be an integer. So (3m+1)(4m+1) must be a square. But 3m+1 and 4m+1 are relatively prime, so each must be a square. Suppose 3m+1 = a² and 4m+1 = (a+k)², then (subtracting) m = 2ak + k², so a² - 6ak - (3k² + 1) = 0, so a = 3k + √(12k²+1). By inspection the smallest solution of this is k = 2, giving a = 13 and hence m = 56 and n = 337.

---

Problem 4

A T-square allows you to construct a straight line through two points and a line perpendicular to a given line through a given point. Circles C and C' intersect at X and Y. XY is a diameter of C. P is a point on C' inside C. Using only a T-square, find points Q,R on C such that QR is perpendicular to XY and PQ is perpendicular to PR.

Solution

C' seems slightly odd. Why not just say that XY is a diameter of C, P is a point inside C and we want points Q, R on C such that QR is perpendicular etc.? So presumably it is there to help.

Note that PQ perpendicular to PR means that P lies on the circle diameter QR. So take M to be the midpoint of QR. Then MQ = MR = MP. Guided by the hint about C', we extend PM to meet C' at S. Then QM·MR = XM·MY (circle C) = PM·MS (circle C'). So M is also the midpoint of PS. So we want to find S on C' so that XY bisects SP.

Let the line XP meet C at U. Draw the line through U perpendicular to XY to meet C again at V. Draw XV. Draw the line through P perpendicular to XY to meet XV at T. Then XY bisects PT, which is parallel to QR. Now draw the line through T perpendicular to PT (and hence parallel to XY) to meet C' at S. XY must also bisect ST. So we have the required point M. Draw the line through M perpendicular to XY to meet the circle C at Q and R.

---

Problem 5

A partition of n is an increasing sequence of integers with sum n. For example, the partitions of 5 are: 1, 1, 1, 1, 1; 1, 1, 1, 2; 1, 1, 3; 1, 4; 5; 1, 2, 2; and 2, 3. If p is a partition, f(p) = the number of 1s in p, and g(p) = the number of distinct integers in the partition. Show that ∑ f(p) = ∑ g(p), where the sum is taken over all partitions of n.

Solution

Let π(n) be the number of partitions of n. If p = a₁, a₂, ... , a_m is a partition of n, then h(p) = 1, a₁, ... , a_m is a partition of n+1 which contains a 1. Moreover, h is obviously a bijection between partitions of n and partitions of n+1 which contain a 1. But h(p) also contains one more 1 than p, so ∑ f(p) for n+1 is ∑ f(p) for n plus π(n). Thus ∑ f(p) for n is 1 + π(1) + π(2) + ... + π(n-1). [Obviously ∑ f(p) for n = 1 is 1.]

Checking, we find π(1) = 1, π(2) = 2, π(3) = 3, π(4) = 5, π(5) = 7. So this formula gives ∑ f(p) for n = 5 is 1 + 1 + 2 + 3 + 5 = 12, which is correct.

Now fix n and consider the number of pairs (p, m), where p is a partition of n containing m. For each p the number of such pairs is g(p). So the total number of such pairs ∑ g(p). But the number of pairs (p, m) for fixed m is just π(n - m) (taking π(0) = 0). So the total is also ∑ π(n - m). So ∑ g(p) = 1 + π(1) + ... + π(n-1) = ∑ f(p).