UNIVERSITY OF MARYLAND MATHEMATICS COMPETITION

2003 PART II Solutions

1. a) (15 points) Find three positive integers a,b,c whose sum is 407, and whose product when written in base 10 ends in six 0's.

Answer: 250, 125, 32.

b) (15 points) Prove that there do NOT exist positive integers a,b,c whose sum is 407 and whose product ends in seven 0's.

Answer: If 0 < m < 408 and m is divisible by 5k, then k is at most 3. There are exactly 2 numbers under 408 divisible by 53; they are 125 and 250. It is not possible for all three numbers, a,b,c, to be divisible by 5 because in this case their sum would be divisible by 5 (and 407 is not). If none of a,b,c is divisible by 5, then the product does not end with a 0. If exactly one of a,b,c is divisible by 5, the product ends with at most two 0s. If exactly two of a,b,c are divisible by 5, the product ends with six 0s (and not more). It is also possible to argue that the product of any 3 postive numbers whose sum is 407 must be less than 10,000,000 (=107).

2. (30 points) Three circles, each of radius r, are placed on a plane so that the center of each circle lies on a point of intersection of the other two circles. The region R consists of all points inside or on at least one of these three circles. Find the area of R.

Answer: The region in question can be split into four dijoint regions: An equilateral triangle with side length 2r, together with three semicircles, each of radius r.
***We are having troubles getting a picture into a readable format.
The area of each semicircle is (1/2)pi r2. The equilateral triangle has base 2r and height (using the Pythagorean theorem) 31/2 r. So the area of the triangle is (1/2)(2r)(31/2r)= 31/2r2. Thus the total area is
(3pi/2+31/2)r2.

3. (30 points) Let f 1(x)= a1 x2+b1x+c1, f 2(x)=a2 x2+b2x+c2, and f 1(x)=a3 x2+b3x+c3 be the equations of three parabolas such that a1 > a2 > a3. Prove that if each pair of parabolas intersects in exactly one point, then all three parabolas intersect in a common point.

Answer: Let xi,j denote the point of intersection of fi and fj. Since f1 and f2 have exactly one common point we have
f1(x) - f2(x) = (a1 - a2)(x -x1,2)2.
It follows that f1(x) > f2(x) for all x except x1,2. Likewise, f2(x) > f3(x) for all x except x2,3. Combining these inequalities with the equation f1(x1,3) = f3(x1,3) we must have x1,3 = x1,2 and x1,3 = x2,3.

4. Gigafirm is a large corporation with many employees.
a) (10 points) Show that the number of employees with an odd number of acquaintances is even.

Answer: Let n be the total number of instances of one employee knowing another, let e be the number of employees with an even number of acquaintances, and let f be the number with an odd number of acquaintances. The number n is even, because if A knows B then B knows A, so each relationship contributes 2 to n. Also, n equals a sum of e even numbers plus a sum of f odd numbers. If f is odd, this sum is odd. Therefore, f must be even.

b) (20 points) Suppose that each employee with an even number of acquaintances sends a letter to each of these acquaintances. Each employee with an odd number of acquaintances sends a letter to each non-acquaintance. So far, Leslie has received 99 letters. Prove that Leslie will receive at least one more letter.
(Notes: ``acquaintance'' and ``non-acquaintance'' refer to employees of Gigafirm. If A is acquainted with B, then B is acquainted with A. However, no one is acquainted with himself.)

Answer: We claim that each employee receives an even number of letters, so Leslie will receive at least one more. There are four types of people (other than Leslie):
(1) even number of acquaintances and know Leslie
(2) odd and know Leslie
(3) even and don't know Leslie
(4) odd and don't know Leslie
Leslie receives letters from the people in types (1) and (4). Now, remove Leslie from Gigafirm. Then all the people in (1) become odd, those in (2) become even, those in (3) stay even, and those in (4) stay odd. By part (a), applied to Gigafirm without Leslie, the total number of odds is even. This means that (1) plus (4) is even. Since Leslie receives (1)+(4) letters, she receives an even number of letters.

5. a) (5 points) Prove that for every positive integer N, if A is a subset of the numbers {1,2,...,N} and A has size at least 2N/3+1, then A contains a three-term arithmetic progression (i.e., there are positive integers a and b so that all three of the numbers a,a+b, and a+2b are elements of A).

Answer: Take the elements {1,2,..., N} and break them up into groups of 3 as follows:
{1,2,3}, {4,5,6}, ...
(Ignore the last 1 or 2 elements if N is not divisible by 3). There are at most N/3 such sets. Since A has size at least 2N/3+1, A must contain all three elements of at least one of these sets. Thus, A has an arithmetic progression of length 3.

b) (25 points) Show that if A is a subset of {1,2,...,3500} and A has size at least 2003, then A contains a three-term arithmetic progression.

Answer: As above, break the set {1,...,3500} into 500 groups of size 7, namely
{1,...,7}, {8,...,14}, ... {3494,...,3500}
If A has at least 2003 elements then one of these groups must have at least 5 elements (else A would have at most 4· 500 = 2000 elements.) So, it suffices to prove the following Claim:
Claim: Any 5-element subset B of any 7 consecutive integers has an arithmetic progression of length at least 3.
Proof of Claim: Since arithmetic progressions are invariant under translations (i.e., if a, a+r, a+2r is an arithmetic progression, then so is a+b, (a+r)+b, (a+2r)+b) it suffices to prove this for the set {1,2,3,4,5,6,7}. There are two cases:
CASE 1: 4 is in B.
Look at the sets {1,7}, {2,6}, {3,5}. Since B has size 5 one of these sets must contribute 2. This yields an arithmetic progression of length 3 (either 1,4,7 or 2,4,6 or 3,4,5).
CASE 2: 4 is not in B.
Look at the sets {1,2,3}, {5,6,7}. Since B has size 5 one of these sets must contribute 3. This yields an arithmetic progression of length 3 (either 1,2,3 or 5,6,7).