Putnam Practice Problem Statements Chris Street

Instructions. These problems are not presented in any particular order. Problems with a • are generally the easiest - try and get a very concise, quick solution. Problems with a † are either a little tricky, or there is an important detail which you shouldn’t miss. Solutions are given in a separate file if needed; however, do your best to work the problems. Try every problem! If the approach most natural to you doesn’t seem to work, set the problem aside (and try another) before returning to the fray.

Some of the problems are done by bookwork; clever tricks liven up your day, however. Strive for the shortest, neatest proof.

These should be pretty good practice, and the mental exercise will make you feel good.

Almost all of these problems require no more than basic undergraduate math. I will say that some basic familiarity with linear algebra is a big plus. If you can use super nice tools like abstract algebra, complex analysis, or generating functions for a neater solution, all the more power to you.

Problem, Putnam 1932 A-2. Determine all polynomials P (x) such that P (x^{2} + 1) = (P (x))^{2} + 1 and P (0) = 0.

Problem, Putnam 1977 A-4. For 0 < x < 1, express

∑_{n=0}^{∞} \frac{x^{2^{n}}}{1 − x^{2^{n+1}}}

as a rational function of x.

Problem, Putnam 1977 B-1. Evaluate the infinite product

∏_{n=2}^{∞} \frac{n^{3} − 1}{n^{3} + 1}.

Problem, Putnam 1968 B-5. Let p be a prime number. Let J_{p} be the set of all

2×2 matrices ( \begin{matrix}a & b \\ c & d \end{matrix} ) whose entries are chosen from the set \{0, 1, 2, ⋯, p−1\}

and which satisfy the conditions a + d ≡ 1 mod p and ad − bc ≡ 0 mod p. Determine how many members J_{p} has.

• Problem, Putnam 1965 A-1. At a party, assume that no boy dances with every girl but each girl dances with at least one boy. Prove that there are two couples gb and g′b′ which dance, whereas b does not dance with g′ nor does g dance with b′.

• Problem, Putnam 1983 A-1. How many positive integers n are there such that n is an exact divisor of at least one of the numbers 10^{40}, 20^{30}?

Problem, Putnam 1967 A-3. Consider polynomial forms ax^{2} + bx + c with integer coefficients which have two distinct zeros in the open interval 0 < x < 1. Exhibit with a proof the least positive integer value of a for which such a polynomial exists.

• Problem, Putnam 1965 B-2. Suppose n players play a round-robin tournament (ie, every player plays every other player exactly once.) Each game results in a win or loss for a player: there are no ties. Let w_{k} be the number of wins by player k, and let l_{k} be the number of losses by player k. Show that

∑_{i=1}^{n} w_{i}^{2} = ∑_{i=1}^{n} l_{i}^{2}

• Problem, from Putnam 1967 B-4. We have a hallway with n lockers, labeled 1 through n. The lockers have two possible states, open and closed. Initially they are all closed. The first kid walking down the hallway flips every locker to the opposite state (that is, he opens them all). The 2nd kid flips the locker door 2 and every other locker door after that. The kth kid flips the state of every kth locker door. After infinitely many kids have done this, which locker doors are closed and which are open?

Problem, Putnam 1977 A-1. Consider all lines that meet the graph of

y = 2x^{4} + 7x^{3} + 3x − 5

in four distinct points, say (x_{i}, y_{i}), i = 1, 2, 3, 4. Show that

\frac{x_{1} + x_{2} + x_{3} + x_{4}}{4}

is independent of the line, and find its value.

• Problem, Putnam 1978 A-1. Let A be any set of 20 distinct integers chosen from the arithmetic progression 1, 4, 7, ⋯, 100. Prove that there must be two distinct integers in A whose sum is 104.

Problem, Putnam 1988 A-2. A not uncommon calculus mistake is to believe that the product rule for derivatives says that (fg)′ = f′g′. If f(x) = e^{x^{2}}, determine, with proof, whether there exists an open interval (a, b) and a nonzero function g defined on (a, b) such that the wrong product rule is true for x in (a, b).

Problem, Putnam 1987 A-2. The sequence

{1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 2, 0, ⋯ }

is obtained by writing the positive integers in order. If the 10^{n}’th digit in this sequence occurs in the part of the sequence in which the m-digit numbers are placed, define f(n) to be m. For example f(2) = 2 because the 100th digit enters the sequence in the placement of the two-digit integer 55. Find, with proof, f(1987).

† Problem, Putnam 1988 A-5. Prove that there exists a unique function from the set ℝ^{+} of positive real numbers to ℝ^{+} such that

f(f(x)) = 6x − f(x)

and f(x) > 0 for all x > 0.

Problem, Putnam 1966 B-2. Prove that among any ten consecutive integers at least one is relatively prime to each of the others.

• Problem, Putnam 1960 B-4. Consider the arithmetic progression a, a + d, a + 2d ⋯, where a and d are positive integers. For any positive integer k, prove that the progression has either no exact kth powers, or infinitely many.

Problem, Putnam 1961 A-1. The graph of the equation x^{y} = y^{x} in the first quadrant (i.e., the region where x > 0 and y > 0) consists of a straight line and a curve. Find the coordinates of the intersection point of the line and the curve.

Problem, Putnam 2001 A-2. You have coins C_{1}, C_{2}, ⋯, C_{n}. For each k, coin C_{k} is biased so that, when tossed, it has probability \frac{1}{2k+1} of falling heads. If the n coins are tossed, what is the probability that the number of heads is odd? Express the answer as a rational function of n.

† Problem, Putnam 2001 A-5. Prove that there exist unique positive integers a, n such that

a^{n+1} − (a + 1)^{n} = 2001.

• Problem, Putnam 2001 B-1. Let n be an even positive integer. Write the numbers 1, 2 ⋯, n^{2} in the squares of an n × n grid so that the kth row, from left to right, is

(k − 1)n + 1, (k − 1)n + 2, ..., (k − 1)n + n.

Color the squares of the grid so that half of the squares in each row and in each column are red and the other half are black (a checkerboard coloring is one possibility.) Prove that for each coloring, the sum of the numbers on the red squares is equal to the sum of the numbers on the black squares.

Problem, Putnam 2001 B-3. For any positive integer n let ⟨n⟩ denote the closest integer to \sqrt{n}. Evaluate

∑_{n=1}^{∞} \frac{2^{⟨n⟩} + 2^{−⟨n⟩}}{2^{n}} .

Problem, Putnam 1968 A-3. Prove that a list can be made of all the subsets of a finite set in such a way that

(i.) The empty set is first in the list,

(ii.) each subset occurs exactly once, and

(iii.) each subset in the list is obtained either by adding one element to the preceding subset or by deleting one element of the preceding subset.

Problem, Putnam 1961 B-2. Let a, b be given positive real numbers with a < b. If two points are selected at random from a straight line of length b, what is the probability that the distance between them is at least a?

Problem, Putnam 1956 A-5. Given n objects arranged in a row, a subset of these objects is called unfriendly if no two of its elements is consecutive. Show

that the number of unfriendly subsets each having k elements is ( \begin{matrix}n − k + 1 \\ k \end{matrix} ).

• Problem, Putnam 1975 A-1. Supposing that an integer n is the sum of two triangular numbers,

n = \frac{a^{2} + a}{2} + \frac{b^{2} + b}{2},

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

Show that, conversely, if 4n+1 = x^{2}+y^{2}, then n is the sum of two triangular numbers.

Problem, Putnam 1969 A-5. Let u(t) be a continuous function in the system of differential equations

\frac{dx}{dt} = −2y + u(t), \frac{dy}{dt} = −2x + u(t).

Show that, regardless of the choice of u(t), the solution of the system which satisfies x = x_{0}, y = y_{0} at t = 0 will never pass through (0, 0) unless x_{0} = y_{0}. When x_{0} = y_{0}, show that for any positive value t_{0} of t, it is possible to choose u(t) so the solution is at (0, 0) when t = t_{0}.

Problem, Putnam 1973 A-6. Prove that it is impossible for seven distinct straight lines to be situated in the Euclidean plane so as to have at least six points where exactly three of these lines intersect and at least four points where exactly two of these lines intersect.

Problem, Putnam 1998 A-4. Define the sequence a_{n} as follows: a_{0} = 0, a_{1} = 1, and a_{n+2} is obtained by writing the digits of a_{n+1} immediately followed by the digits of a_{n}. When is a_{n} divisible by 11?

Problem, Putnam 1998 B-6. Show that for any integers a, b, c, we can find a positive integer n such that n^{3} + an^{2} + bn + c is not a perfect square.