Putnam Mathematical Competition, 3 December 2005

Problem A1

Show that every positive integer is a sum of one or more numbers of the form 2^{r}3^{s}, where r and s are nonnegative integers and no summand divides another. (For example, 23 = 9 + 8 + 6.)

Problem A2

Let S = {(a, b) | a = 1, 2, …, n, b = 1, 2, 3}. A rook tour of S is a polygonal path made up of line segments connecting points p_{1}, p_{2}, …, p_{3n} in sequence such that (i) p_{i} ∈ S, (ii) p_{i} and p_{i+1} are a unit distance apart, for 1 ≤ i < 3n, (iii) for each p ∈ S there is a unique i such that p_{i} = p. How many rook tours are there that begin at (1, 1) and end at (n, 1)? (An example of such a rook tour for n = 5 is depicted below.)

• • • • • • • • • • • • • • •

Problem A3

Let p(z) be a polynomial of degree n, all of whose zeros have absolute value 1 in the complex plane. Put g(z) = p(z)/z^{n/2}. Show that all zeros of g′(z) = 0 have absolute value 1.

Problem A4

Let H be an n × n matrix all of whose entries are ±1 and whose rows are mutually orthogonal. Suppose H has an a × b submatrix whose entries are all 1. Show that ab ≤ n.

Problem A5

Evaluate ∫_{0}^{1} \frac{ln(x + 1)}{x^{2} + 1}dx.

Problem A6

Let n be given, n ≥ 4, and suppose that P_{1}, P_{2}, …, P_{n} are n randomly, independently and uniformly, chosen points on a circle. Consider the convex n-gon whose vertices are the P_{i}. What is the probability that at least one of the vertex angles of this polygon is acute?

Problem B1 Find a nonzero polynomial P (x, y) such that P (⌊a⌋, ⌊2a⌋) = 0 for all real numbers a. (Note: ⌊v⌋ is the greatest integer less than or equal to v.) Problem B2 Find all positive integers n, k_{1}, …, k_{n} such that k_{1} + ⋯ + k_{n} = 5n − 4 and

\frac{1}{k_{1}} + ⋯ + \frac{1}{k_{n}} = 1.

Problem B3 Find all differentiable functions f : (0, ∞) → (0, ∞) for which there is a positive real number a such that

f′ (\frac{a}{x}) = \frac{x}{f(x)}

for all x > 0. Problem B4 For positive integers m and n, let f(m, n) denote the number of n-tuples (x_{1}, x_{2}, …, x_{n}) of integers such that |x_{1}| + |x_{2}| + ⋯ + |x_{n}| ≤ m. Show that f(m, n) = f(n, m). Problem B5 Let P (x_{1}, …, x_{n}) denote a polynomial with real coefficients in the variables x_{1}, …, x_{n}, and suppose that

(a)  (\frac{∂^{2}}{∂x_{1}^{2}} + ⋯ + \frac{∂^{2}}{∂x_{n}^{2}} ) P (x_{1}, …, x_{n}) = 0  (identically)

and that

(b)  x_{1}^{2} + ⋯ + x_{n}^{2} divides P (x_{1}, …, x_{n}).

Show that P = 0 identically. Problem B6 Let S_{n} denote the set of all permutations of the numbers 1, 2, …, n. For π ∈ S_{n}, let σ(π) = 1 if π is an even permutation and σ(π) = −1 if π is an odd permutation. Also, let v(π) denote the number of fixed points of π. Show that

∑_{π∈S_{n}} \frac{σ(π)}{v(π) + 1} = (−1)^{n+1} \frac{n}{n + 1}.

Solutions

D. J. Bernstein, 4 December 2005

Problem A1

Show that every positive integer is a sum of one or more numbers of the form 2^{r}3^{s}, where r and s are nonnegative integers and no summand divides another. (For example, 23 = 9 + 8 + 6.)

Solution: For each n ≥ 0 define a sequence E(n) of elements of 2^{N}3^{N} as follows:

• if n = 0 then E(n) is the empty sequence ();

• if n > 0 and n is even then E(n) is 2E(n/2), the sequence obtained by doubling each component of E(n/2);

• if n > 0 and n is odd then E(n) is (E(n − 3^{k}), 3^{k}), the sequence obtained by appending 3^{k} to E(n − 3^{k}), where k is the largest integer such that 3^{k} ≤ n.

I claim that the sum of E(n) is n; that each component of E(n) is even if n is even; and that no component of E(n) divides another component. Proof:

• n = 0: E(n) is empty so it has sum 0.

• n > 0 and n is even: Assume inductively that E(n/2) has sum n/2 and that no component of E(n/2) divides another component. Then E(n) = 2E(n/2) has sum 2(n/2) = n; each component of E(n) is even; and no component divides another component.

• n > 0 and n is odd: Find the largest integer k such that 3^{k} ≤ n. Note that n − 3^{k} is even. Assume inductively that E(n − 3^{k}) has sum n − 3^{k}; that each component of E(n − 3^{k}) is even; and that no component of E(n − 3^{k}) divides another component. Then E(n) = (E(n − 3^{k}), 3^{k}) has sum (n − 3^{k}) + 3^{k} = n; each component of E(n−3^{k}), being even, does not divide 3^{k}; and each component of E(n − 3^{k})/2, being at most (n − 3^{k})/2 < (3^{k+1} − 3^{k})/2 = 3^{k}, is not divisible by 3^{k}, so each component of E(n − 3^{k}) is not divisible by 3^{k}.

In particular, for n ≥ 1, the components of E(n) are one or more elements of 2^{N}3^{N}, adding up to n, none dividing the others.

Problem A2

Let S = {(a, b) | a = 1, 2, …, n, b = 1, 2, 3}. A rook tour of S is a polygonal path made up of line segments connecting points p_{1}, p_{2}, …, p_{3n} in sequence such that (i) p_{i} ∈ S, (ii) p_{i} and p_{i+1} are a unit distance apart, for 1 ≤ i < 3n, (iii) for each p ∈ S there is a unique i such that p_{i} = p. How many rook tours are there that begin at (1, 1) and end at (n, 1)? (An example of such a rook tour for n = 5 is depicted below.)

• • • • • • • • • • • • • • •

Solution: The answer is 0 for n = 1 and 2^{n−2} for n ≥ 2.

For each n ≥ 1, define r_{n} as the number of n × 3 rook tours beginning at (1, 1) and ending at (n, 1), and define s_{n} as the number of n × 3 rook tours beginning at (1, 1) and ending at (n, 3).

One can obtain an n × 3 rook tour beginning at (1, 1) and ending at (n, 1) as follows. Choose k ∈ {1, 2, …, n − 1}. Take a k × 3 rook tour beginning at (1, 1) and ending at (k, 3). Step to the right n−k times to (n, 3); then down once to (n, 2); then left n−k −1 times to (k + 1, 2); then down once to (k + 1, 1); then right n − k − 1 times to (n, 1).

Every n × 3 rook tour beginning at (1, 1) and ending at (n, 1) can be obtained uniquely in this way. Indeed, the final step down on the tour must be from (k + 1, 2) to (k + 1, 1) for a unique k ∈ {1, 2, …, n − 1}; it must be followed by n − k − 1 steps right to (n, 1); it must be preceded by n − k − 1 steps left from (n, 2), since any earlier step up (or left) would prevent the tour from reaching (n, 2); (n, 2) must be preceded by a step down from (n, 1); and (n, 1) must be preceded by n − k steps right from (k, 1).

Consequently r_{n} = s_{1} + s_{2} + ⋯ + s_{n−1} for all n ≥ 1. In particular, r_{1} = 0.

Similarly, one can obtain an n × 3 rook tour beginning at (1, 1) and ending at (n, 3) by choosing k ∈ {1, 2, …, n − 1}, taking a k × 3 rook tour beginning at (1, 1) and ending at (k, 1), stepping to the right n − k times, stepping up once, stepping left n − k − 1 times, stepping up once, and stepping right n − k − 1 times; or by simply starting from (1, 1), stepping to the right n − 1 times, stepping up once, stepping left n − 1 times, stepping up once, and stepping right n − 1 times. Every n × 3 rook tour beginning at (1, 1) and ending at (n, 3) can be obtained uniquely in this way.

Consequently s_{n} = r_{1} + r_{2} + ⋯ + r_{n−1} + 1 for all n ≥ 1. In particular, s_{1} = 1.

Now r_{n} = s_{n} = 2^{n−2} for all n ≥ 2. Indeed, assume inductively that r_{k} = s_{k} = 2^{k−2} for 2 ≤ k < n. Then r_{n} = s_{1} + s_{2} + ⋯ + s_{n−1} = 1 + 2^{0} + ⋯ + 2^{n−3} = 2^{n−2} and s_{n} = r_{1} + r_{2} + ⋯ + r_{n−1} + 1 = 0 + 2^{0} + ⋯ + 2^{n−3} + 1 = 2^{n−2}.

Problem A3 Let p(z) be a polynomial of degree n, all of whose zeros have absolute value 1 in the complex plane. Put g(z) = p(z)/z^{n/2}. Show that all zeros of g′(z) = 0 have absolute value 1.

Solution: I’m annoyed by this problem, for two reasons.

First, the definition of g(z) is ambiguous when n is odd. Does z^{n/2} mean the principal branch of the n/2 power, applied to z? Or does it mean the principal branch of the square root, applied to z^{n}? Or is z not actually a complex number, but an element of a Riemann sheet chosen so that the square root does not need a branch cut? My proof works for any of these choices of g, but I can imagine proofs that work with all the roots of g and that occasionally break down for the first two choices of g. The problem should have said “Show that all zeros of zp′(z) − (n/2)p(z) have absolute value 1.”

Second, the statement is false for n = 0. Consider, for example, p(z) = 1. This is a polynomial of degree 0, and it has no zeros, so all of its zeros have absolute value 1. The function g(z) = p(z)/z^{n/2} is then constant, so its derivative is 0, so its derivative has every complex number (in the ambiguous domain) as a root, not just complex numbers of absolute value 1.

Assume from now on that n ≥ 1. Factor p(z) as p_{n}(z − r_{1})(z − r_{2}) ⋯ (z − r_{n}). By hypothesis each r_{i} has absolute value 1. If |z| > 1 then, by Lemma 2, (z + r_{j})/(z − r_{j}) has positive real part for each j, so—since n ≥ 1—∑_{j}(z + r_{j})/(z − r_{j}) has positive real part. Similarly, if |z| < 1 then ∑_{j}(z + r_{j})/(z − r_{j}) has negative real part. Either way ∑_{j}(z + r_{j})/(z − r_{j}) is nonzero; i.e., ∑_{j} 2z/(z − r_{j}) ≠ ∑_{j}(z − r_{j})/(z − r_{j}) = n; i.e., 2zp′(z)/p(z) ≠ n; i.e., g′(z) ≠ 0.

Lemma 1: If z ∈ C then (z + 1)/(z − 1) has positive real part when |z| > 1 and negative real part when |z| < 1.

Proof: Write z in polar coordinates as re^{iθ}. Then (z + 1)/(z − 1) = (re^{iθ} + 1)/(re^{iθ} − 1) has real part (r^{2} − 1)/((r cos θ − 1)^{2} + (r sin θ)^{2}), which is positive if r > 1 and negative if 0 ≤ r < 1.

Lemma 2: If r ∈ C, |r| = 1, and |z| ∈ C, then (z + r)/(z − r) has positive real part when |z| > 1 and negative real part when |z| < 1.

Proof: Apply Lemma 1 to z/r.

Problem A4

Let H be an n × n matrix all of whose entries are ±1 and whose rows are mutually orthogonal. Suppose H has an a × b submatrix whose entries are all 1. Show that ab ≤ n.

Solution: Write v_{1}, v_{2}, …, v_{b} for the length-n row vectors covering H. By assumption each entry of v_{i} is ±1, so v_{i} has squared length n. By assumption v_{1}, v_{2}, …, v_{b} are pairwise orthogonal, so v_{1} + v_{2} + ⋯ + v_{b} has squared length nb. On the other hand, by assumption v_{1} + v_{2} + ⋯ + v_{b} has a entries equal to b, so v_{1} + v_{2} + ⋯ + v_{b} has squared length at least ab^{2}. Thus ab^{2} ≤ nb; consequently ab ≤ n, whether or not b = 0.

Problem A5

Evaluate ∫_{0}^{1} \frac{ln(x + 1)}{x^{2} + 1}dx.

Solution: The answer is (π/8) log 2. Fast proof by Bhargava, Kedlaya, and Ng: The integral is ∫_{0}^{π/4} log(tan θ + 1) dθ = ∫_{0}^{π/4}((1/2) log 2 + log cos(π/4 − θ) − log cos θ) dθ = ∫_{0}^{π/4}((1/2) log 2) dθ = (π/8) log 2 since ∫_{0}^{π/4} log cos(π/4 − θ) dθ = ∫_{0}^{π/4} log cos θ dθ.

Problem A6

Let n be given, n ≥ 4, and suppose that P_{1}, P_{2}, …, P_{n} are n randomly, independently and uniformly, chosen points on a circle. Consider the convex n-gon whose vertices are the P_{i}. What is the probability that at least one of the vertex angles of this polygon is acute?

Solution: The answer is (n^{2} − 2n)/2^{n−1}.

Define θ(p, q) ∈ [0, 2π), where p and q are points on the circle, as the angle from p to q in the clockwise direction.

Define a vertex as “happy” if it is immediately before an acute-angled vertex. In other words, if v, w, x are consecutive vertices in clockwise order, then v is happy if and only if the angle at vertex w is acute. Equivalently: v is happy if and only if θ(v, x) > π. Equivalently: v is happy if and only if at most one other vertex P has θ(v, P) ≤ π.

Critical fact 1: P_{1} is happy with probability n/2^{n−1}.

Indeed, here is a partition of P_{1}’s happiness into n disjoint possibilities, each occurring with probability 1/2^{n−1}:

• θ(P_{1}, P_{i}) > π for all i ≠ 1;
• θ(P_{1}, P_{i}) > π for all i ∉ {1, 2} while θ(P_{1}, P_{2}) ≤ π;
• θ(P_{1}, P_{i}) > π for all i ∉ {1, 3} while θ(P_{1}, P_{3}) ≤ π;
• …;
• θ(P_{1}, P_{i}) > π for all i ∉ {1, n} while θ(P_{1}, P_{n}) ≤ π.

Critical fact 2: P_{1} and P_{2} are simultaneously happy with probability 1/2^{n−3}(n − 1).

This probability is the average, over P_{1}, P_{2}, of the conditional probability given P_{1}, P_{2}. I claim that the conditional probability is exactly ((π−α)^{n−2}+(n−2)α(π−α)^{n−3})/(2π)^{n−2} where α = min {θ(P_{1}, P_{2}), θ(P_{2}, P_{1})}. The distribution of α is uniform over [0, π], so the average of ((π − α)^{n−2} + (n − 2)α(π − α)^{n−3})/(2π)^{n−2} is

\frac{1}{π} ∫_{0}^{π} \frac{(π − α)^{n−2} + (n − 2)α(π − α)^{n−3}}{(2π)^{n−2}} dα

= \frac{1}{π} ∫_{0}^{π} \frac{(3 − n)(π − α)^{n−2} + (n − 2)π(π − α)^{n−3}}{(2π)^{n−2}} dα

= \frac{1}{2^{n−2}π^{n−1}} ((3 − n)\frac{π^{n−1}}{n − 1} + (n − 2)π \frac{π^{n−2}}{n − 2})

= \frac{3 − n}{2^{n−2}(n − 1)} + \frac{n − 1}{2^{n−2}(n − 1)} = \frac{1}{2^{n−3}(n − 1)}.

Proof of the claim: Assume without loss of generality that θ(P_{1}, P_{2}) ≤ π, i.e., that α = θ(P_{1}, P_{2}). Now P_{1} is happy if and only if θ(P_{1}, P_{3}), …, θ(P_{1}, P_{n}) are all > π; and P_{2} is happy if and only if at most one of θ(P_{2}, P_{3}), …, θ(P_{2}, P_{n}) is ≤ π. Thus P_{1} and P_{2} are simultaneously happy if and only if one of the following disjoint events occurs:

• π + α < θ(P_{1}, P_{i}) < 2π for each i ∉ {1, 2}—which, given P_{1} and P_{2}, occurs with

conditional probability (π − α)^{n−2}/(2π)^{n−2};

• π + α < θ(P_{1}, P_{i}) < 2π for each i ∉ {1, 2, 3} while π < θ(P_{1}, P_{3}) ≤ π + α—which,

given P_{1} and P_{2}, occurs with conditional probability α(π − α)^{n−3}/(2π)^{n−2};

• π + α < θ(P_{1}, P_{i}) < 2π for each i ∉ {1, 2, 4} while π < θ(P_{1}, P_{4}) ≤ π + α—which,

given P_{1} and P_{2}, occurs with conditional probability α(π − α)^{n−3}/(2π)^{n−2};
• …;

• π + α < θ(P_{1}, P_{i}) < 2π for each i ∉ {1, 2, n} while π < θ(P_{1}, P_{n}) ≤ π + α—which,

given P_{1} and P_{2}, occurs with conditional probability α(π − α)^{n−3}/(2π)^{n−2}.

Add to obtain ((π − α)^{n−2} + (n − 2)α(π − α)^{n−3})/(2π)^{n−2} as claimed.

Critical fact 3: P_{1}, P_{2}, P_{3} are all happy with probability 0.

Indeed, in each of the above ways for P_{1}, P_{2} to be happy, P_{3} is visibly unhappy: either π + α < θ(P_{1}, P_{3}) ≤ 2π, in which case both θ(P_{3}, P_{1}) and θ(P_{3}, P_{2}) are below π, or π < θ(P_{1}, P_{3}) ≤ π + α while π + α < θ(P_{1}, P_{4}) ≤ 2π, in which case both θ(P_{3}, P_{1}) and θ(P_{3}, P_{4}) are below π. This is where the proof uses the hypothesis that n ≥ 4.

Putting it all together: Permute indices to see that P_{i} is happy with probability n/2^{n−1}; that P_{i}, P_{j} are simultaneously happy with probability 1/2^{n−3}(n − 1), if the indices i, j are distinct; and that P_{i}, P_{j}, P_{k} are simultaneously happy with probability 0, if i, j, k are distinct. By inclusion-exclusion, the probability of at least one happy vertex is n(n/2^{n−1}) − \binom{n}{2}(1/2^{n−3}(n − 1)) = (n^{2} − 2n)/2^{n−1}.

Problem B1

Find a nonzero polynomial P (x, y) such that P (⌊a⌋, ⌊2a⌋) = 0 for all real numbers a. (Note: ⌊v⌋ is the greatest integer less than or equal to v.)

Solution: One answer is the nonzero polynomial P (x, y) = (y − 2x)(y − 2x − 1).

Define i = ⌊a⌋. Then i ≤ a < i + 1. If i ≤ a < i + 0.5 then 2i ≤ 2a < 2i + 1 so ⌊2a⌋ = 2i = 2⌊a⌋ so ⌊2a⌋−2⌊a⌋ = 0. Otherwise i+0.5 ≤ a < i+1 so 2i+1 ≤ 2a < 2i+2 so ⌊2a⌋ = 2i + 1 = 2⌊a⌋ + 1 so ⌊2a⌋ − 2⌊a⌋ − 1 = 0. Either way P (⌊a⌋, ⌊2a⌋) = 0.

Problem B2

Find all positive integers n, k_{1}, …, k_{n} such that k_{1} + ⋯ + k_{n} = 5n − 4 and

\frac{1}{k_{1}} + ⋯ + \frac{1}{k_{n}} = 1.

Solution: 1, 1; 3, 2, 3, 6; 3, 2, 6, 3; 3, 3, 2, 6; 3, 3, 6, 2; 3, 6, 2, 3; 3, 6, 3, 2; 4, 4, 4, 4, 4.

By inspection each of these possibilities works. Conversely, assume that k_{1} + ⋯ + k_{n} = 5n−4 and 1/k_{1} +⋯+1/k_{n} = 1; I will show that n, k_{1}, …, k_{n} is one of these possibilities.

If k_{1}, …, k_{n} are all equal then 1 = 1/k_{1} + ⋯ + 1/k_{n} = n/k_{1} so k_{1} = n and 5n − 4 = k_{1} + ⋯ + k_{n} = nk_{1} = n^{2}. Hence (n − 4)(n − 1) = n^{2} − 5n + 4 = 0. Either n = 1, in which case (n, k_{1}, …, k_{n}) = (1, 1); or n = 4, in which case (n, k_{1}, …, k_{n}) = (4, 4, 4, 4, 4).

Assume from now on that k_{1}, …, k_{n} are not all equal. The average of k_{1}, …, k_{n} is (5n − 4)/n so the geometric average of k_{1}, …, k_{n} is below (5n − 4)/n. The average of 1/k_{1}, …, 1/k_{n} is 1/n so the geometric average of 1/k_{1}, …, 1/k_{n} is below 1/n. Thus the geometric average of k_{1}, …, k_{n}, 1/k_{1}, …, 1/k_{n} is below \sqrt{((5n − 4)/n)(1/n)}; but this geometric average is equal to 1. Therefore 1 < (5n − 4)/n^{2}; so (n − 1)(n − 4) < 0; so 1 < n < 4; so n = 2 or n = 3.

If n = 2 then k_{1} +k_{2} = 5n−4 = 6 so 1/k_{1} +1/k_{2} is one of 1/1+1/5, 1/2+1/4, 1/3+1/3, none of which equal 1.

If n = 3 then k_{1} + k_{2} + k_{3} = 5n − 4 = 11 so 1/k_{1} + 1/k_{2} + 1/k_{3} is one of 1/1 + ⋯, 1/2 + 1/2+⋯, 1/2+1/3+1/6, 1/2+1/4+1/5, 1/3+1/3+1/5, 1/3+1/4+1/4. By inspection none of these are 1 except 1/2 + 1/3 + 1/6. Thus (k_{1}, k_{2}, k_{3}) is a permutation of (2, 3, 6).

Problem B3

Find all differentiable functions f : (0, ∞) → (0, ∞) for which there is a positive real number a such that

f′ (\frac{a}{x}) = \frac{x}{f(x)}

for all x > 0.

Solution: Here are two classes of qualifying functions f:

• Define f(x) = x. Then f′(x) = 1 so f′(1/x) = 1 = x/f(x).

• Choose positive real numbers α, β with β ≠ 1, and define f(x) = αx^{β}. Then f′(a/x)f(x) = αβ(a/x)^{β−1}αx^{β} = α^{2}βa^{β−1}x = x where a = (1/α^{2}β)^{1/(β−1)}.

I claim that there are no other possibilities: if f′(a/x) = x/f(x) then f is one of the above functions. Indeed, substitute a/x for x: f′(x) = a/xf(a/x). The right side is differentiable, so the left side is too:

f′′(x) = \frac{−a}{(xf(a/x))^{2}} (xf′(a/x)\frac{−a}{x^{2}} + f(a/x)) .

Substitute f(a/x) = a/xf′(x) and f′(a/x) = x/f(x):

\begin{aligned}f′′(x) & = \frac{−a}{(a/f′(x))^{2}} (\frac{x^{2}}{f(x)} \frac{−a}{x^{2}} + \frac{a}{xf′(x)}) \\ & = \frac{−f′(x)^{2}}{a} (\frac{−a}{f(x)} + \frac{a}{xf′(x)}) = \frac{f′(x)^{2}}{f(x)} − \frac{f′(x)}{x}. \end{aligned}

Define g(x) = log f(x). Then g′(x) = f′(x)/f(x); note that f′(x) > 0 so g′(x) > 0. Differentiate again:

g′′(x) = \frac{f(x)f′′(x) − f′(x)^{2}}{f(x)^{2}} = \frac{−f(x)f′(x)/x}{f(x)^{2}} = \frac{−f′(x)}{xf(x)} = \frac{−g′(x)}{x}.

Define h(x) = log g′(x). Then h′(x) = g′′(x)/g′(x) = −1/x. Integrate: there is a real number d such that h(x) = d − log x. Exponentiate: g′(x) = β/x where β = exp d. Integrate again: there is a real number c such that g(x) = c + β log x. Exponentiate: f(x) = αx^{β} where α = exp c. If β = 1 then f(x) = αx so α = f′(a/x) = x/f(x) = 1/α so α = 1 so f(x) = x as claimed. Otherwise α, β are positive real numbers, β ≠ 1, and f(x) = αx^{β} as claimed.

Problem B4

For positive integers m and n, let f(m, n) denote the number of n-tuples (x_{1}, x_{2}, …, x_{n}) of integers such that |x_{1}| + |x_{2}| + ⋯ + |x_{n}| ≤ m. Show that f(m, n) = f(n, m).

Solution: Extend the same definition to all nonnegative integers m, n.

If n = 0 then there is exactly one n-tuple, and its sum of absolute values is 0 ≤ m. Thus f(m, 0) = 1.

If m = 0 then the only qualifying n-tuple is (0, 0, …, 0). Thus f(0, n) = 1.

If n ≥ 1 and m ≥ 0 then one can construct a qualifying n-tuple as follows: choose x_{n} in {−m, −m + 1, …, m − 1, m}; choose an (n − 1)-tuple (x_{1}, x_{2}, …, x_{n−1}) satisfying |x_{1}| + |x_{2}| + ⋯ + |x_{n−1}| ≤ m − |x_{n}|. Every qualifying n-tuple arises uniquely in this way. Thus f(m, n) = f(m, n − 1) + 2f(m − 1, n − 1) + 2f(m − 2, n − 1) + ⋯ + 2f(0, n − 1).

Consequently, f(m + 1, n + 1) = f(m, n + 1) + f(m + 1, n) + f(m, n) if n ≥ 0 and m ≥ 0. Indeed, f(m, n + 1) = f(m, n) + 2f(m − 1, n) + 2f(m − 2, n) + ⋯ + 2f(0, n). and f(m + 1, n + 1) = f(m + 1, n) + 2f(m, n) + 2f(m − 1, n) + 2f(m − 2, n) + ⋯ + 2f(0, n); subtract.

Theorem: f(m, n) = f(n, m) for all nonnegative integers m, n. Proof: If m = 0 then f(m, n) = f(0, n) = 1 = f(n, 0) = f(n, m) as claimed. If n = 0 then f(m, n) = f(m, 0) = 1 = f(0, m) = f(n, m) as claimed. So assume that m ≥ 1 and n ≥ 1. Then f(m, n) = f(m − 1, n) + f(m, n − 1) + f(m − 1, n − 1) and f(n, m) = f(n − 1, m) + f(n, m − 1) + f(n − 1, m − 1). Induct on m + n.

Alternate approaches: One can, with marginally more work, prove the symmetric formula f(m, n) = 1 + 2(m + n − 1)!/(m − 1)!(n − 1)!. One can use other bijections; partitioning by choices of x_{n} is straightforward but might not produce the shortest proof.

Problem B5

Let P (x_{1}, …, x_{n}) denote a polynomial with real coefficients in the variables x_{1}, …, x_{n}, and suppose that

(a)  (\frac{∂^{2}}{∂x_{1}^{2}} + ⋯ + \frac{∂^{2}}{∂x_{n}^{2}} ) P (x_{1}, …, x_{n}) = 0  (identically)

and that

(b)  x_{1}^{2} + ⋯ + x_{n}^{2} divides P (x_{1}, …, x_{n}).

Show that P = 0 identically.

Solution: Assume that n ≥ 1. Define X = x_{1}^{2}+⋯+x_{n}^{2} and D = ∂^{2}/∂x_{1}^{2}+⋯+∂^{2}/∂x_{n}^{2}. The problem is to show that if X divides P and D(P) = 0 then P = 0.

Suppose that P ≠ 0. Find the maximum positive integer e such that X^{e} divides P. Write P/X^{e} as ∑_{i≥0} H_{i} where H_{i} is homogeneous of degree i.

Then 0 = D(P) = D(∑_{i} X^{e}H_{i}) = ∑_{i} D(X^{e}H_{i}). The terms D(X^{e}H_{i}) are homogeneous of different degrees, namely 2e − 2 + i, so D(X^{e}H_{i}) = 0 for each i. Thus XD(H_{i}) + e(4(e−1)+4 deg H_{i} +2n)H_{i} = 0 by Lemma 2. The coefficient e(4(e−1)+4 deg H_{i} +2n) is positive since n ≥ 1 and e ≥ 1; thus H_{i} is a multiple of X. This is true for every i, so P/X^{e} is a multiple of X, contradicting the definition of e.

Lemma 1: If H is homogeneous then D(XH) = XD(H) + (4 deg H + 2n)H.

Proof: \frac{∂^{2}XH}{∂x_{i}^{2}} = X \frac{∂^{2}H}{∂x_{i}^{2}} +2\frac{∂X}{∂x_{i}} \frac{∂H}{∂x_{i}} +H \frac{∂^{2}X}{∂x_{i}^{2}} = X \frac{∂^{2}H}{∂x_{i}^{2}} +4x_{i} \frac{∂H}{∂x_{i}} +2H. By homogeneity

∑_{i} x_{i}(∂H/∂x_{i}) = (deg H)H.

Lemma 2: If H is homogeneous and e ≥ 0 then

D(X^{e}H) = X^{e}D(H) + e(4(e − 1) + 4 deg H + 2n)X^{e−1}H.

Proof: For e = 0: D(X^{e}H) = D(H) = X^{e}D(H) + e(⋯). For e ≥ 1: D(X^{e}H) = XD(X^{e−1}H) + (4 deg X^{e−1}H + 2n)X^{e−1}H by Lemma 1. Assume inductively that D(X^{e−1}H) = X^{e−1}D(H) + (e − 1)(4(e − 2) + 4 deg H + 2n)X^{e−2}H. Then

D(X^{e}H) = X^{e}D(H) + (e − 1)(4(e − 2) + 4 deg H + 2n)X^{e−1}H
+ (4 deg X^{e−1}H + 2n)X^{e−1}H
= X^{e}D(H) + (4(e − 1)(e − 2) + 4(e − 1) deg H + 2(e − 1)n
+ 4(e − 1) deg X + 4 deg H + 2n)X^{e−1}H
= X^{e}D(H) + (4(e − 1)(e) + 4e deg H + 2en)X^{e−1}H

since deg X = 2.

Problem B6

Let S_{n} denote the set of all permutations of the numbers 1, 2, …, n. For π ∈ S_{n}, let σ(π) = 1 if π is an even permutation and σ(π) = −1 if π is an odd permutation. Also, let v(π) denote the number of fixed points of π. Show that

∑_{π∈S_{n}} \frac{σ(π)}{v(π) + 1} = (−1)^{n+1} \frac{n}{n + 1}.

Solution: Define e_{n} as the number of even permutations of {1, 2, …, n}. Recall that e_{n} = 1 if n = 0; e_{n} = 1 if n = 1; and e_{n} = n!/2 if n ≥ 2.

Define f_{k} as the number of even derangements of {1, 2, …, k}, i.e., the number of even permutations with no fixed points. Define g_{k} as the number of odd derangements of {1, 2, …, k}, i.e., the number of odd permutations with no fixed points.

By choosing k elements of {1, …, n}, choosing an even derangement of those k elements, and fixing the other n − k elements, one obtains an even permutation of {1, …, n} with exactly n − k fixed points. Every such permutation arises in this way. Thus there are exactly \binom{n}{k}f_{k} even permutations of \{1, …, n\} with exactly n − k fixed points. Sum over k to see that ∑_{0≤k≤n} \binom{n}{k}f_{k} = e_{n}.

Similarly, there are exactly \binom{n}{k}g_{k} odd permutations of \{1, …, n\} with exactly n−k fixed points, and ∑_{0≤k≤n} \binom{n}{k}g_{k} = n! − e_{n}.

I claim that f_{n} − g_{n} = (−1)^{n−1}(n − 1) for all n ≥ 0. Proof: The point is that f_{n} − g_{n} is determined recursively by the equation ∑_{k} \binom{n}{k}(f_{k} − g_{k}) = 2e_{n} − n!; so one simply has to check that ∑_{k} \binom{n}{k}(−1)^{k−1}(k − 1) = 2e_{n} − n!. For n = 0 the latter sum is (−1)^{−1}(−1) = 1 = 2e_{0} − 0! as desired. For n = 1 the sum is (−1)^{−1}(−1) + (−1)^{0}(0) = 1 = 2e_{1} − 1! as desired. For n ≥ 2 one has ∑_{k} \binom{n}{k}(−1)^{k} = (1 − 1)^{n} = 0 and ∑_{k} \binom{n}{k}(−1)^{k−1}k = ∑_{k} \binom{n−1}{k−1}(−1)^{k−1} = (1 − 1)^{n−1} = 0 so ∑_{k} \binom{n}{k}(−1)^{k−1}(k − 1) = 0 = 2e_{n} − n! as desired.

Now if n ≥ 1 then ∑_{0≤k≤n} \binom{n+1}{k}(f_{k} − g_{k}) = (−1)^{n+1}n. Proof: \binom{n+1}{n+1}(f_{n+1} − g_{n+1}) = (−1)^{n}n and ∑_{0≤k≤n+1} \binom{n+1}{k}(f_{k} − g_{k}) = 2e_{n+1} − (n + 1)! = 0.

The problem asks for the sum of σ(π)/(1 + v(π)) over all permutations π of {1, …, n}. There are \binom{n}{k}f_{k} even permutations π with v(π) = n−k, contributing \binom{n}{k}f_{k}/(1+n−k) = \binom{n+1}{k}f_{k}/(n+1) to the sum. There are also \binom{n}{k}g_{k} odd permutations π with v(π) = n−k, contributing −\binom{n}{k}g_{k}/(1 + n − k) = −\binom{n+1}{k}g_{k}/(n + 1) to the sum. Overall the sum is ∑_{0≤k≤n} \binom{n+1}{k}(f_{k} − g_{k})/(n + 1) = (−1)^{n+1}n/(n + 1) if n ≥ 1.

Beware that this formula is wrong for n = 0. The problem should have said that n is a positive integer.