### 19th Putnam 1958

 A1.  Define f(i, j) as follows: f(i, 1) = f(1, j) = 1, f(i+1, j+1) = f(i, j+1) + f(i+1, j) + f(i, j). Let d(n) = f(1, n-1) + f(2, n-2) + ... + f(n-1, 1). Show that d(n + 2) = d(n) + 2 d(n + 1). A2.  Define a1 = 1, an+1 = 1 + n/an. Show that √n ≤ an < 1 + √n. A3.  Assuming that there is a unique function f(x) satisfying f(0) = 1, f '(x) = f(x) + ∫01 f(t) dt, find it. A4.  Find the general solution in real numbers a, b, c, d to the inequalities 2a > a + b > a + c > 2b > b + c > a + d > 2c > b + d > c + d > d + d. Find the smallest solution in positive integers. A5.  Let A = (aij) be the n x n matrix with aij = 1 if i ≠ j, and aii = 0. Show that the number of non-zero terms in the expansion of det A is n! ∑on (-1)i/i! . A6.  R is the reals. α ∈ [0, 1). f : [0, 1] → [0, α] and g : [0, 1] → R are continuous. β satisfies β = max (g(x) + f(x) β). When do we have β = max g(x)/(1 - f(x) )? A7.  m, n are relatively prime positive integers with n even. Given any positive integer r, define f(r) to be the integer which minimizes |f(r)/r - m/n|. Show that limk→∞ ∑1k |f(r)/r - m/n| r/k = 1/4. B1.  Let an = ∑0n 1/nCr. Show that an = 1 + an-1 (n + 1)/(2n). Deduce that lim an = 2. B2.  Let X be the set {1, 2, 3, ... , 2n}, take Y ⊆ X with |Y| = n + 1. Show that we can find a, b ∈ Y with a dividing b. B3.  Show that if X is a square side 1 and X = A ∪ B, then A or B has diameter at least √5 /2. Show that we can find A and B both having diameter ≤ √5 /2. B4.  Let R be the reals. f : R → R is three times differentiable. As x → ∞, f(x) tends to a finite limit, and f '''(x) tends to zero. Show that f '(x) and f ''(x) also tend to zero. B5.  A sequence of points Pn in the plane is defined by: P0 is at the origin; P1 is at (1, 0); and Pn-1Pn is length 1/n and at an angle θ to the previous segment. Find the coordinates of lim Pn. B6.  A graph has n vertices {1, 2, ... , n} and a complete set of edges. Each edge is oriented, as either i → j or j → i. Show that we can find a permutation of the vertices ai so that a1 → a2 → a3 → ... → an. B7.  Let N = {1, 2, ... , n}. Given a permutation f : N → N, define d(f) = no. of i such that f(i) > f(j) for all j > i. Find the mean of d(f) over all permutations f on N.

To avoid possible copyright problems, I have changed the wording, but not the substance, of all the problems. The original text and solutions are available in: A M Gleason, R E Greenwood & L M Kelly, The William Lowell Putnam Mathematical Competition, Problems and Solutions, 1938-1964, MAA 1980. Out of print, but available in some university libraries.

Putnam home