PUTNAM PROBLEM ARCHIVE

1. September 11-15, 2000

Problem A1 December 1999

Find polynomials f(x), g(x), and h(x), if they exist, such that, for all x,

Solution: Try f(x), g(x), and h(x) as linear polynomials since the given function is piece-wise linear. A bit of simple computation yields .

2. September 18-22, 2000

Problem A1 December 1975

Supposing that an integer n is the sum of two triangular numbers,

write 4n+1 as the sum of two squares, , and show how x and y can be expressed in terms of a and b.

Show that, conversely, if , then n is the sum of two triangular numbers.

[Of course a, b, x, and y are understood to be integers.]

Solution.

Suppose that a and b are integers and . Since are sums of two even or two odd numbers then each sum is even. Thus n is an integer. Compute 4n+1. We want to write this as the sum of two squares of integers. Experimenting with terms like (a + b), (a – b), and (a + b + 1) yields

Thus we have the first part if we let x = a + b + 1 and y = a-b.

For the second part we simply solve the equations above for a and b in terms of x and y. Adding x and y gives x + y = 2a + 1. Hence. We need to show that a is an integer. Since is odd it follows that one of x and y is even and one is odd. thus x + y –1 is even and a is an integer. Solving for b by subtracting y from x gives x – y = 2b + 1 or which is also an integer by the same argument.

3. September 25-29

Problem B1 December 1975

In the additive group of ordered pairs of integers (m,n) [with addition defined componentwise: (m,n) + (m’,n’) = (m + m’,n + n’)] consider the subgroup H generated by the three elements

(3,8) (4,-1) (5,4).

then H has another set of generators of the form (1,b) and (0,a) for some integers a and b with a positive. Find a.

[Elements u and v generate H if every element h of H can be written as mu + nv for some integers m and n.]

Solution

The desired generators must be combinations of the three given elements. (5,4) - (4,-1) yields the element (1,5) which is an element of the form (1,b). The generator of the form (0,a) with a positive is a bit harder to find. (3,8) + (5,4) – 2(4,-1) = (14,0). (0,14) wont work as a generator with (1,5). Try to express (3,8) with just (1,5) and (10,14). If (0,a) is a generator then a must be a factor of 14. Try (0,7).

(3,8) = 3(1,5) – (0,7)

(4,-1) = 4(1,5)-3(0,7)

(5,4) = 5(1,5)-4(0,7).

Thus all the given generators can be expressed in terms of (1,5) and (0,7). All we need to do to finish the problem is to express (0,7) in terms of the given generators.

2(3,8) + (4,-1) – 2(5,4) = (0,7).

4. October 2 – 6

Problem A1 – December 1973

Let there be given nine lattice points (points with integral coordinates) in three dimensional Euclidean space. Show that there is a lattice point on the interior of one of the line segments joining two of these points.

Solution.

Consider a lattice point (x, y, z). Classify it according to the parity (oddness or evenness) of its entries. For example (2, 4, 11) would be (even, even, odd). There are exactly eight different ordered triples of even and odd. Thus two of the nine given points must have the same parity. Suppose that (x, y, z) and (a, b, c) are two points such that each coordinate has the same parity. Then are all integers and are the coordinates of the midpoint of the line joining (x, y, z) and (a, b, c). This midpoint is a lattice point on the interior of the line segment joining (x, y, z) and (a, b, c).

5. October 9 -15

Problem A1 – December 1966

Let f(n) be the sum of the first n terms of the sequence 0, 1, 1, 2, 2, 3, 3, 4, 4, 5,…, where the nth term is given by

Show that if x and y are positive integers and then

Solution. Computing f(x) for a few small values of x yields the conjecture that f(2n) = n². Prove this by induction. f(2) = 1 = 1² by direct computation. Assume that f(2n) = n². Now compute f(2n+2) = f(2n) + a_2n+1 + a_2n+2 = n² + n + (n+1) = (n+1)². For odd integers x = 2n + 1 we have f(2n+1)= n² + n by direct computation.

Case 1. If x+y is even, then so is x-y. Assume that x is greater than or equal to y. then we have f(x+y) – f(x-y) = .

Case 2. If x+y is odd, then so is x-y. Then f(x+y) – f(x-y) =

6. October 16 – 20

Problem B1 December 1966

Prove that among any ten consecutive integers at least one is relatively prime to the others.

Solution. If two integers are not relatively prime then they share a prime factor. If a and b are integers with then any common prime factor must be less than 10, since any common factor of a and b also is a factor of a – b. Thus we need to consider the primes 2, 3, 5, and 7 as possible common factors. Let a set A of ten consecutive integers be given. Exactly five of these numbers are even and hence none of these is relatively prime to all the rest. Of the remaining five odd integers at most 2 are divisible by 3. Removing these leaves at least three integers in A that do not share 2 or 3 as a common factor with any other integers in A. Of the three remaining at most one is divisible by five. Remove it. From the remaining two integers at most one is divisible by 7. This leaves at least one integer in A which is not divisible by 2, or by 3, or by 5, or by 7. Thus that integer can share no common factors with any other integer in A.

7. October 23 - 27

Problem A1 December 1998

A right circular cone has base radius 1 and height 3. A cube is inscribed in the cone so that one face of the cube is contained in the base of the cone. What is the side length of the cube?

Solution. A cube whose base is in the base of the cone must touch the cone at the four upper vertices. If the side of the cube is x then at height x the cone must have diameter equal to the face diagonal of the cube. Draw a picture of the cone and set up similar triangles. This will yield the proportion . Solving the proportion for x yields .

8. October 30-November 3

Problem A1 December 1974

Call a set of positive integers “conspiratorial” if no three of them are pairwise relatively prime. (A set of integers is “pairwise relatively prime” if no pair of them has a common divisor greater than 1.) What is the largest number of elements in any “conspiratorial” subset of the integers 1 through 16?

Solution.

Let S be a conspiratorial subset. Then S can contain at most two elements of the set {1,2,3,5,7,11,13} since this set is pairwise relatively prime. Thus S can have at most two of these and the other 9 numbers in the set {1, 2, 3, …,16}. The maximum for S is thus 11 elements. Try the set {2,3,4,6,8,9,10,12,14,15,16} that has 11 elements. It is conspiratorial.

9. November 6 - 10

Problem A1 – December 1965

Let ABC be a triangle with angle A < Angle C < 90° < angle B. Consider the bisectors of the external angles at A and B, each measured from the vertex to the opposite side (extended). Suppose both these line segments are equal to AB. Compute the angle A.

Solution.

Let the measures of angles A, b, and C be a, b, and c respectively. By drawing a picture and using supplementary angles one sees that the bisected exterior angles at A and B have measure and . Let D be the point of intersection of the bisector at A and side BC extended. Then by the condition of the problem ABD is an isosceles triangle with AD=AB. Angle ABD is supplementary to angle B so its measure is 180-b. Thus angle ADB is also 180-b (by the property of base angles of isosceles triangles). Since the sum of the measures of the angles of a triangle is 180 we have 2(180-b) + angle DAB =180. Thus angle DAB has measure 2b-180. This angle is one-half of a supplement to angle A hence 2b-180 = . This yields the equation a + 4b = 540. Very similarly using the other angle bisector we develop the equation . This gives us a system of three equations in three unknowns:

Solving these yields a= 12.

Why are the conditions on the sizes of A, B, and C given?

10. November 13-17, 2000

Problem B1 – December 1999

Find the minimum value of

for x>0.