1995 Putnam problems and unofficial solutions

As usual, first come the problems, then the problems with solutions. Comments and criticism at the end.

Send any followup remarks to the USENET newsgroup sci.math.

Problems

Problem A1

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.

Problem A2

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?

Problem A3

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} in 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.]

Problem A4

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.

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

\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}

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? Problem A6 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. Problem B1 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.] Problem B2 An ellipse, whose semi-axes have lengths a and b, rolls without slipping on the curve y = c sin (\frac{x}{a}). How are a, b, c related, given that the ellipse completes one revolution when it traverses one period of the curve? Problem B3 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.)

Problem B4 Evaluate

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

Express your answer in the form \frac{a + b\sqrt{c}}{d}, where a, b, c, d are integers. Problem B5 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. Problem B6 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.]

Unofficial solutions

Problem A1 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. Solution: If neither T nor U is closed under multiplication then there are a, b ∈ T with ab ∉ T, i.e., ab ∈ U, and also c, d ∈ U with cd ∉ U, i.e., cd ∈ T. But then abcd = (a)(b)(cd) ∈ T and abcd = (ab)(c)(d) ∈ U, contradiction. Problem A2 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?

Solution: The integrand is continuous for x ≥ b so ∫_{b}^{t} is a proper integral for any t ≥ b. We need only check how this integral behaves as t → ∞.

If a ≠ b then our integral does not converge. Indeed, note that

\begin{aligned}\sqrt{\sqrt{x + a} − \sqrt{x}} − \sqrt{\sqrt{x} − \sqrt{x − b}} & = \sqrt{\frac{a}{\sqrt{x} + \sqrt{x + a}}} − \sqrt{\frac{b}{\sqrt{x} + \sqrt{x − b}}} \\ & = \frac{1}{\sqrt[4]{x}} \frac{a/(1 + \sqrt{1 + a/x}) − b/(1 + \sqrt{1 − b/x})}{\sqrt{a/(1 + \sqrt{1 + a/x})} + \sqrt{b/(1 + \sqrt{1 − b/x})}}. \end{aligned}

The numerator a/(1 + \sqrt{1 + a/x}) − b/(1 + \sqrt{1 − b/x}) converges to (a − b)/2 ≠ 0, so for all sufficiently large x it is at least |a − b| /4 in absolute value. The denominator

\sqrt{a/(1 + \sqrt{1 + a/x})} + \sqrt{b/(1 + \sqrt{1 − b/x})} is at most \sqrt{a} + \sqrt{b}. Thus the integrand is at

least |a − b| /4(\sqrt{a} + \sqrt{b}) times 1/ ^{4} \sqrt{x}. The integral of 1/ ^{4} \sqrt{x} does not converge, so our integral does not converge.

If a = b then our integral converges. Indeed, note that

\begin{matrix}|\frac{b}{1 + \sqrt{1 + b/x}} − \frac{b}{1 + \sqrt{1 − b/x}}| = b\frac{\sqrt{1 + b/x} − \sqrt{1 − b/x}}{(1 + \sqrt{1 + b/x})(1 + \sqrt{1 − b/x})} \\ = \frac{2b^{2}}{x} \frac{1}{(\sqrt{1 + b/x} + \sqrt{1 − b/x})(1 + \sqrt{1 + b/x})(1 + \sqrt{1 − b/x})} ≤ \frac{2b^{2}}{x} . \end{matrix}

Thus the integrand is, in absolute value, at most a constant times 1/x^{5/4}. The integral of 1/x^{5/4} converges, so our integral converges.

Problem A3

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} in 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.]

Solution: Define S = ∑_{n} d_{n}10^{9−n} and T = ∑_{n} e_{n}10^{9−n}. By assumption, 7 divides S + (e_{i} − d_{i})10^{9−i} for each i ∈ {1, 2, 3, 4, 5, 6, 7, 8, 9}, so 7 divides

∑_{i}(S + (e_{i} − d_{i})10^{9−i}) = ∑_{i} S + ∑_{i} e_{i}10^{9−i} − ∑_{i} d_{i}10^{9−i} = 9S + T − S = 8S + T.

Thus 7 divides S + T. We also know that 7 divides T + (f_{i} − e_{i})10^{9−i}, so 7 divides S + T + (f_{i} − d_{i})10^{9−i}. Hence 7 divides (f_{i} − d_{i})10^{9−i}. Since 7 and 10 are coprime, 7 divides f_{i} − d_{i}.

Problem A4

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.

Solution: We induct on n.

If there are no positive labels, we may cut the necklace anywhere. Then x_{1}, x_{2}, …, x_{n} are nonpositive, so ∑_{i=1}^{k} x_{i} ≤ 0 ≤ k − 1 for each k.

Now say there is a positive label. We can find a nonpositive label, say L, immediately followed by a positive label, say M. (Indeed, there must be a nonpositive label—if not, all labels would be positive, and the sum would be at least n, contradiction. Now, starting from a nonpositive label, move forwards in the necklace to the first positive label. That positive label is M, and the label immediately before it is L.)

We now construct a smaller necklace, by merging L and M into L + M − 1. The new necklace has exactly n − 1 beads. The sum of its labels is exactly n − 2. Hence, by induction, there is a way to cut the smaller necklace so that its labels y_{1}, y_{2}, …, y_{n−1} satisfy ∑_{i=1}^{k} y_{i} ≤ k − 1 for each k.

Now the “same” cut of the original necklace will work. In y_{1}, y_{2}, …, y_{n−1} we un-merge L + M − 1 into L and M to obtain x_{1}, x_{2}, …, x_{n}; if the merged label L + M − 1 appears at position p, we have x_{i} = y_{i} for i < p, x_{p} = L, x_{p+1} = M, and x_{i+1} = y_{i} for i > p. We check the desired condition in several cases. For k < p we have ∑_{i=1}^{k} x_{i} = ∑_{i=1}^{k} y_{i} ≤ k − 1. For k = p we have ∑_{i=1}^{k} x_{i} = L + ∑_{i=1}^{p−1} y_{i} ≤ L + p − 2 < p − 1 since L < 1. For k ≥ p + 1 we have ∑_{i=1}^{k} x_{i} = 1 + ∑_{i=1}^{k−1} y_{i} ≤ 1 + (k − 2) = k − 1.

Problem A5

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

\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}

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?

Solution: Yes, x_{1}, …, x_{n} are linearly dependent. Let A be the matrix of coefficients in this system of differential equations. By assumption A is a nonnegative matrix, so it has a nonnegative real eigenvalue λ. Let (v_{1}, v_{2}, …, v_{n}) ≠ 0 be a corresponding eigenvector. Define x = v_{1}x_{1} + ⋯ + v_{n}x_{n}. Then x′ = λx, so x is of the form t ↦ re^{λt} for some real number r. But x(t) → 0 as t → ∞, so r must be 0. Hence x = 0.

Problem A6

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.

Solution: Let (x, y, z) be the original row sums. Note that x + y + z = 6n.

Now a = b − 1 = c − 2 if and only if (x − 2n, y − 2n, z − 2n) is in S, where S = {(0, 1, −1), (0, −1, 1), (1, 0, −1), (−1, 0, 1), (1, −1, 0), (−1, 1, 0)}; and a = b = c if and only if (x − 2n, y − 2n, z − 2n) = (0, 0, 0).

For any (a, b, c), write p_{n}(a, b, c) for the probability that (x, y, z) equals (2n + a, 2n + b, 2n + c). We are asked to show that 4p_{n}(0, 0, 0) ≤ ∑_{s∈S} p_{n}(s) for some n ≥ 1995. In fact, this is true for n = 2001 or n = 2002.

Define X = {(1, 1, −2), (−1, −1, 2), (1, −2, 1), (−1, 2, −1), (−2, 1, 1), (2, −1, −1)}, Y = {(0, 2, −2), (0, −2, 2), (2, 0, −2), (−2, 0, 2), (2, −2, 0), (−2, 2, 0)}, and C = {(0, 0, 0)}.

Define S_{n} = ∑_{s∈S} p_{n}(s); define X_{n}, Y_{n}, and C_{n} similarly.

With some work one can verify that 6C_{m+1} = S_{m}; 6S_{m+1} = 6C_{m} + 2S_{m} + 2X_{m} + Y_{m}; 6X_{m+1} ≥ 2S_{m}+2Y_{m}; and 6Y_{m+1} ≥ S_{m}+2X_{m}. Hence 36C_{m+2} = 6C_{m}+2S_{m}+2X_{m}+Y_{m} and 36S_{m+2} ≥ 12C_{m} + 15S_{m} + 6X_{m} + 6Y_{m}.

If 4C_{m+1} > S_{m+1} then

4S_{m} > 6C_{m} + 2S_{m} + 2X_{m} + Y_{m}

so 2S_{m} > 6C_{m} + 2X_{m} + Y_{m}. If also 4C_{m+2} > S_{m+2} then

24C_{m} + 8S_{m} + 8X_{m} + 4Y_{m} > 12C_{m} + 15S_{m} + 6X_{m} + 6Y_{m}

so 12C_{m} + 2X_{m} > 7S_{m} + 2Y_{m} ≥ 4S_{m} > 12C_{m} + 4X_{m} + 2Y_{m} so 0 > 2X_{m} + 2Y_{m}, contradiction.

In particular, for m = 2000, we must have 4C_{m+1} ≤ S_{m+1} or 4C_{m+2} ≤ S_{m+1} as claimed.

Problem B1

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.]

Solution: Say π(z) ≥ 4 for some z. Select four distinct elements x_{1}, x_{2}, x_{3}, x_{4} in the part of π containing z. Suppose π′(x_{1}), π′(x_{2}), π′(x_{3}), π′(x_{4}) are all distinct. Then x_{1}, x_{2}, x_{3}, x_{4} are in different parts of π′, so π′(x_{1}) + π′(x_{2}) + π′(x_{3}) + π′(x_{4}) is at most 9, the size of our original set. But π′(x_{1}), π′(x_{2}), π′(x_{3}), π′(x_{4}), being distinct positive integers, must have sum at least 1 + 2 + 3 + 4 = 10. Contradiction. Hence there is some repetition π′(x_{i}) = π′(x_{j}) with i ≠ j; since π(x_{i}) = π(z) = π(x_{j}) we are done.

Similarly, if π′(z) ≥ 4 for any z then we are done. So assume that, for every z, π(z) and π′(z) are at most 3. Suppose that all pairs (π(z), π′(z)) are distinct. Then there are nine values of (π(z), π′(z))—but there are only nine possibilities, namely (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3). Hence each possibility occurs exactly once. By inspection there are exactly three z’s with π(z) = 2. This is impossible, since there must be an even number of z’s in size-2 parts.

Problem B2

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

Solution: The rolling condition means that the circumference of the ellipse equals the arc length of one period of the sine curve. We will show that this occurs exactly when b = \sqrt{a^{2} + c^{2}}. (Note that b, being a length, cannot be negative.)

The curve (x, y) = (a cos θ, b sin θ), with 0 ≤ θ ≤ 2π, traces out an ellipse with semi-axes a and b. The circumference of the ellipse is

∫_{0}^{2π} \sqrt{(x′)^{2} + (y′)^{2}} dθ = ∫_{0}^{2π} \sqrt{a^{2} sin^{2} θ + b^{2} cos^{2} θ} dθ = ∫_{0}^{2π} \sqrt{a^{2} + (b^{2} − a^{2}) cos^{2} θ} dθ.

The curve (x, y) = (aθ, c sin θ), with 0 ≤ θ ≤ 2π, traces out one period of the given sine curve y = c sin(x/a). The arc length of the sine curve is

∫_{0}^{2π} \sqrt{(x′)^{2} + (y′)^{2}} dθ = ∫_{0}^{2π} \sqrt{a^{2} + c^{2} cos^{2} θ} dθ.

Thus the circumference equals the arc length when b = \sqrt{a^{2} + c^{2}}. The circumference and arc length cannot be equal for any other value of b, since the circumference of the ellipse is a strictly increasing function of b.

Problem B3

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.)

Solution: For n = 1 the determinants are 1, 2, 3, 4, 5, 6, 7, 8, 9, with sum 9(10)/2 = 45.

For n = 2 the determinants are ad − bc for a ∈ {1, 2, …, 9} and b, c, d ∈ {0, 1, 2, …, 9}. Now

∑_{a,b,c,d} ad = (∑_{a} a)(∑_{b} 1)(∑_{c} 1)(∑_{d} d) = (45)(10)(10)(45)

and

∑_{a,b,c,d} bc = (∑_{a} 1)(∑_{b} 1)(∑_{c} c)(∑_{d} d) = (9)(45)(45)(10)

so the sum of determinants is (10 − 9)(10)45^{2} = 20250.

For n ≥ 3, consider the effect of swapping the second and third row of each matrix. This preserves the set of matrices, and hence the sum of determinants. But this also negates each determinant and hence negates the sum. So the sum must be 0.

Problem B4

Evaluate

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

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

Solution: Define x_{0} = 2207; define x_{n+1} = 2207 − 1/x_{n} for n ≥ 0.

By induction 2206 < x_{n+1} < x_{n} ≤ 2207 for all n ≥ 0. (For n = 0 we have 2206 < 2207 − 1/2207 < 2207. If n ≥ 1 and 2206 < x_{n} < x_{n−1} ≤ 2207 then 2206 < 2207 − 1/2206 < 2207 − 1/x_{n} < 2207 − 1/x_{n−1} so 2206 < x_{n+1} < x_{n}.)

Hence the x_{n}’s converge. Write x = lim x_{n}. Then x = 2207 − 1/x so x^{2} − 2207x + 1 = 0; since x ≥ 2206 > 2207/2 we must have x = (2207 + \sqrt{2207^{2} − 4})/2. Note that 2207 = 47^{2} − 2 so 2207^{2} − 4 = 2205 · 47^{2} = 5 · 21^{2} · 47^{2}. Thus x = (2207 + 21 · 47\sqrt{5})/2.

We are asked to evaluate ^{8} \sqrt{x}. The answer is (3 + 1\sqrt{5})/2. Indeed, ((3 + \sqrt{5})/2)^{8} = ((7 + 3\sqrt{5})/2)^{4} = ((47 + 21\sqrt{5})/2)^{2} = (2207 + 21 · 47\sqrt{5})/2 = x.

Problem B5

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.

Solution: The first player wins by moving to 2456.

Easy proof: The following table exhibits a winning strategy. Each line begins with a position p and pairs of positions q, r. By inspection, (1) the q’s are all possible results of moves from p; (2) the r’s are valid moves from q; (3) each r is either “empty” or another position p in the table. Hence, by induction, (1) whoever moves from a q position will force a win by moving to r; (2) whoever moves from a p position will be forced to lose. In particular, whoever moves from 2456 will be forced to lose.

4: 3, empty. 6: 5, 4. 44: 34, 4. 46: 36, 6; 45, 44. 55: 45, 44. 256: 56, 55; 246, 46; 255, 55. 444: 344, 44. 446: 346, 46; 445, 444. 455: 355, 55; 445, 444. 2456: 456, 455; 2356, 256; 2446, 446; 2455, 455.

Hard proof: By induction on the number of beans, a position of the form m_{1}, m_{2}, …, m_{r}, with all m_{i} ≥ 4 and ∑ m_{i} even, is a losing position. Indeed, from a position of the form m_{1}, m_{2}, …, m_{r}, with all m_{i} ≥ 4 and ∑ m_{i} even, the player might either (1) decrement an m_{i} = 4 down to 3, or (2) decrement an m_{i} > 4. In the first case, the other player can either win or create a smaller losing position by removing the 3; the sum of the remaining m_{i}’s is even. In the second case, since the number of beans is now odd, the other player can find a pile with more than 4 beans, and remove a bean from it to create a smaller losing position. By a similar induction on the total number of beans, a position of the form 2, m_{1}, m_{2}, …, m_{r}, with all m_{i} ≥ 4 and ∑ m_{i} odd, is a losing position. In particular, 2456 is a losing position.

Problem B6

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.]

Solution: Suppose that {1, 2, 3, …} is the disjoint union of S(α), S(β), S(γ). Without loss of generality take α ≤ β ≤ γ.

Let t be an integer. For i ≤ ⌈t/α⌉ − 1 we have iα < t so ⌊iα⌋ ≤ t − 1. Thus there are at least ⌈t/α⌉ − 1 ≥ t/α − 1 multiples of α in {1, 2, …, t − 1}. Similarly there are at least t/β −1 multiples of β and t/γ −1 multiples of γ. Hence t/α−1+t/β −1+t/γ −1 ≤ t−1; in other words 1/α + 1/β + 1/γ ≤ 1 + 2/t. This is true for arbitrarily large t, so 1/α + 1/β + 1/γ ≤ 1.

If α ≥ 2 then ⌊iα⌋ , ⌊iβ⌋ , ⌊iγ⌋ ≥ 2, contradiction. Thus α < 2.

Write n = ⌊γ⌋. Let k be the number of multiples of β in {1, 2, …, n − 1}. Then α has exactly n−k multiples in {1, 2, …, n − 1}, so ⌊(n − k)α⌋ ≤ n−1 and ⌊(n − k + 1)α⌋ ≥ n. On the other hand ⌊(n − k + 1)α⌋ cannot equal ⌊γ⌋ = n, so ⌊(n − k + 1)α⌋ ≥ n+1. Thus

(n − k)α = (n − k + 1)α − α ≥ ⌊(n − k + 1)α⌋ − α ≥ n + 1 − 2 = n − 1.

So ⌊(n − k)α⌋ = n − 1. Next ⌊kβ⌋ ≤ n − 1, but ⌊kβ⌋ cannot equal ⌊(n − k)α⌋ = n − 1, so ⌊kβ⌋ ≤ n − 2.

We have (n − k)α < n so 1/α > (n − k)/n; kβ < n − 1 so 1/β > k/(n − 1); and γ < n + 1 so 1/γ > 1/(n + 1). Add: 1 ≥ 1/α + 1/β + 1/γ > (n − k)/n + k/(n − 1) + 1/(n + 1). Clear denominators: n(n − 1)(n + 1) ≥ (n − 1)(n + 1)(n − k) + n(n + 1)k + n(n − 1) = n^{3} + (k − 2)n + n^{2} + k. Hence 0 ≥ n^{2} + (k − 1)n + k. Since n ≥ 1 and k ≥ 1, this is absurd.

Comments

Did the B5 author realize that one can easily solve the problem by enumerating a small portion of the game tree?

A4 is well known in the following form: a string of numbers with positive sum can be rotated so that all its initial substrings have positive sum. Is it really the purpose of the Putnam to measure contestants by the number of Halmos talks they have had the opportunity to attend?

As usual, several exam questions were poorly worded. B4 should have said either (1) assume that the continued fraction converges or (2) prove that the continued fraction converges; a contestant who assumes (1) will lose points if the grader thinks (2), and a contestant who assumes (2) will waste time if the grader thinks (1). Similarly, A4 did not make clear whether one is allowed to reverse the orientation of the necklace; a contestant who thinks of this possibility may waste lots of time considering it. A5 should have stated n ≥ 1—the result is false for n = 0. B3 should have stated n ≥ 1. At the beginning of A3 it is not clear whether d_{1}d_{2} … d_{9} is supposed to be a product or a decimal expansion; this ambiguity is later implicitly resolved (“the digits d_{i}”), but it should have been eliminated entirely.

The theorem I used in A5—any nonnegative matrix has a nonnegative eigenvalue (namely its spectral radius)—is perhaps too heavy for the Putnam. You can instead observe that the matrix has nonnegative trace, hence an eigenvalue with nonnegative real part. You’ll have to do a bit more work than I did if the eigenvalue is not real.

—Daniel J. Bernstein, djb@silverton.berkeley.edu, 4 December 1995