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 5^{k}, then k is at most 3.
There are exactly 2 numbers under 408 divisible by 5^{3}; 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 (=10^{7}).

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 r^{2}. The equilateral
triangle has base 2r and height (using the Pythagorean theorem) 3^{1/2} r.
So the area of the triangle is
(1/2)(2r)(3^{1/2}r)= 3^{1/2}r^{2}.
Thus the total area is

(3pi/2+3^{1/2})r^{2}.

3. (30 points)
Let f_{ 1}(x)=
a_{1} x^{2}+b_{1}x+c_{1},
f_{ 2}(x)=a_{2} x^{2}+b_{2}x+c_{2},
and
f_{ 1}(x)=a_{3} x^{2}+b_{3}x+c_{3}
be the equations of three parabolas such that
a_{1} > a_{2} > a_{3}.
Prove that if each pair of parabolas intersects in exactly one point, then
all three parabolas intersect in a common point.

Answer:
Let x_{i,j} denote the point of intersection of f_{i} and f_{j}.
Since f_{1} and f_{2} have exactly one common point we have

f_{1}(x) - f_{2}(x) =
(a_{1} - a_{2})(x -x_{1,2})^{2}.

It follows that f_{1}(x) > f_{2}(x) for all x except x_{1,2}.
Likewise, f_{2}(x) > f_{3}(x) for all x except
x_{2,3}.
Combining these inequalities with
the equation
f_{1}(x_{1,3}) = f_{3}(x_{1,3}) we must have
x_{1,3} = x_{1,2} and x_{1,3} = x_{2,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).