FIFTY-SIXTH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 2, 1995 Examination A

A-1. Let S be a set of real numbers which is closed under multiplication (that is, if a and b are in S, then so is ab). Let T and U be disjoint subsets of S whose union is S. Given that the product of any three (not necessarily distinct) elements of T is in T and that the product of any three elements of U is in U, show that at least one of the two subsets T, U is closed under multiplication.

A-2. For what pairs (a, b) of positive real numbers does the improper integral

∫_{b}^{∞} (\sqrt{\sqrt{x + a} − \sqrt{x}} − \sqrt{\sqrt{x} − \sqrt{x − b}}) dx

converge?

A-3. The number d_{1}d_{2} … d_{9} has nine (not necessarily distinct) decimal digits. The number e_{1}e_{2} … e_{9} is such that each of the nine 9-digit numbers formed by replacing just one of the digits d_{i} in d_{1}d_{2} … d_{9} by the corresponding digit e_{i} (1 ≤ i ≤ 9) is divisible by 7. The number f_{1}f_{2} … f_{9} is related to e_{1}e_{2} … e_{9} is the same way: that is, each of the nine numbers formed by replacing one of the e_{i} by the corresponding f_{i} is divisible by 7. Show that, for each i, d_{i} − f_{i} is divisible by 7. [For example, if d_{1}d_{2} … d_{9} = 199501996, then e_{6} may be 2 or 9, since 199502996 and 199509996 are multiples of 7.]

A-4. Suppose we have a necklace of n beads. Each bead is labeled with an integer and the sum of all these labels is n − 1. Prove that we can cut the necklace to form a string whose consecutive labels x_{1}, x_{2}, …, x_{n} satisfy

∑_{i=1}^{k} x_{i} ≤ k − 1 for k = 1, 2, …, n.

A-5. Let x_{1}, x_{2}, …, x_{n} be differentiable (real-valued) functions of a single variable t which satisfy

\begin{aligned}\frac{dx_{1}}{dt} & = a_{11}x_{1} + a_{12}x_{2} + ⋯ + a_{1n}x_{n} \\ \frac{dx_{2}}{dt} & = a_{21}x_{1} + a_{22}x_{2} + ⋯ + a_{2n}x_{n} \\ ⋮ & ⋮  ⋮ \\ \frac{dx_{n}}{dt} & = a_{n1}x_{1} + a_{n2}x_{2} + ⋯ + a_{nn}x_{n} \end{aligned}

for some constants a_{ij} > 0. Suppose that for all i, x_{i}(t) → 0 as t → ∞. Are the functions x_{1}, x_{2}, …, x_{n} necessarily linearly dependent?

A-6. Suppose that each of n people writes down the numbers 1, 2, 3 in random order in one column of a 3 × n matrix, with all orders equally likely and with the orders for different columns independent of each other. Let the row sums a, b, c of the resulting matrix be rearranged (if necessary) so that a ≤ b ≤ c. Show that for some n ≥ 1995, it is at least four times as likely that both b = a + 1 and c = a + 2 as that a = b = c.

FIFTY-SIXTH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 2, 1995 Examination B

B-1. For a partition π of {1, 2, 3, 4, 5, 6, 7, 8, 9}, let π(x) be the number of elements in the part containing x. Prove that for any two partitions π and π′, there are two distinct numbers x and y in {1, 2, 3, 4, 5, 6, 7, 8, 9} such that π(x) = π(y) and π′(x) = π′(y). [A partition of a set S is a collection of disjoint subsets (parts) whose union is S.]

B-2. An ellipse, whose semi-axes have lengths a and b, rolls without slipping on the curve y = c sin(x/a). How are a, b, c related, given that the ellipse completes one revolution when it traverses one period of the curve?

B-3. To each positive integer with n^{2} decimal digits we associate the determinant of the matrix obtained by writing the digits in order across the rows. For example, for n = 2, to the integer 8617

we associate det( \begin{matrix}8 & 6 \\ 1 & 7 \end{matrix} ) = 50. Find, as a function of n, the sum of all the determinants associated

with n^{2}-digit integers. (Leading digits are assumed to be nonzero; for example, for n = 2, there are 9000 determinants.)

B-4. Evaluate

8 \sqrt{2207 − \frac{1}{2207 − \frac{1}{2207−...}}} .

Express your answer in the form (a + b\sqrt{c})/d, where a, b, c, d are integers.

B-5. A game starts with four heaps of beans, containing 3,4,5 and 6 beans. The two players move alternately. A move consists of taking either

a. one bean from a heap, provided at least two beans are left behind in that heap, or b. a complete heap of two or three beans.

The player who takes the last heap wins. To win the game, do you want to move first or second? Give a winning strategy.

B-6. For a positive real number α, define

S(α) = {⌊nα⌋ : n = 1, 2, 3, …}.

Prove that {1, 2, 3, …} cannot be expressed as the disjoint union of three sets S(α), S(β) and S(γ). [As usual, ⌊x⌋ is the greatest integer ≤ x.]