The following is an email message (actually, a concatenation of two
messages) I sent out after the 1993 Putnam. It includes more or less
complete solutions of all of the problems, but I make no claims for
readability (nor for my alleged "alternate" solution of A5).
------
A1: Find t > 0 such that \int_{0}{t}{f(x) - f(t) dx} = 0, where f(x) = 2x
- 3x^3. The solution comes out to be t = 2/3, and c = f(t) = 4/9.
A2: Since the terms are nonzero, we can define
a_n = (x_{n+1} + x_{n-1})/x_n for n \geq 1. It suffices to show a_1 = a_2
= \cdots.
But x_{n+1}^2 - x_nx_{n+2} = 1 = x_n^2 - x_{n+1}x_{n-1}
x_{n+1}(x_{n+1} + x_{n-1}) = x_n(x_n + x_{n+2})
x_{n+1}(a_nx_n) = x_n(a_{n+1}x_{n+1})
a_n = a_{n+1}
since x_n, x_{n+1} \neq 0. The result follows by induction.
A3: The functions f biject to tuples (j, S_{j+1}, \dots, S_m) such that
S_{j+1} \subseteq \cdots \subseteq S_m. The bijection is, j is the
minimum value of f and S_{i} for j+1 \leq i \leq m is the intersection of
all sets A such that f(a) \leq i.
But for fixed j, those in turn biject to functions from {1, \dots, n} to
{j+1, \dots, m+1}. The bijection is, the function gives the smallest i
such that n \in S_i, or m+1 if i \notin S_m. And the number of such
functions is (m-j+1)^n. Summing that gives the desired result.
A4: Don't you love it when they give problems you've seen at MOP? (Very
same problem, MOP 1990.)
Anyway, assume W/oLOG that the sum of the x_i is less than or equal to
the sum of the y_i. (I'm not going to use the numbers 19 or 93, so it's
okay. In fact, I'll write p and q since I can't remember whether the x's
are less than 19 or 93. So x_1, \dots, x_p \leq q and y_1, \dots, y_q
\leq p.)
For m = 0, \dots, p, let f(m) be the largest n such that
x_1 + \cdots + x_m - y_1 - \cdots - y_n
is nonnegative. Let g(m) be the value of this difference. (Note: f(0) =
g(0) = 0.)
We claim g(m) < p for all m. Indeed, f(m) < q, because the sum of all the
x's is less than the sum of all the y's. So
x_1 + \cdots + x_m - y_1 - \cdots - y_n - y_{n+1} < 0
by assumption. But y_{n+1} \leq p; adding that to both sides gives
g(m) < p.
So for each of 0, 1, \dots, p, g(m) takes a value in \{0, \dots, p-1\}.
By the Pigeonhole Principle, there are m < m' such that g(m) = g(m').
But now x_{m+1} + \cdots + x_{m'} = y_{g(m)+1} + \cdots + y_{g(m')}.
A5: The key is that the upper and lower limits of integration are
related by the transformation x -> 1/(x-1). (Remember this transformation
has period 3.) Moreover, x^3 - 3x + 1 is basically preserved by this (up
to a power of x-1, but in the integral, you get 4 powers of x-1 from the
numerator and 2 from dx, clearing the 6 from downstairs.)
First solution: Use the transformation to combine all three integrals
into one integral from, say, -100 to -10, of some quartic over (x^3 - 3x
+ 1)^2. Then discover this happens to work out nicely. (I don't recall to
what, as I didn't do this.)
Second solution (mine): Let $f(x) = (x^2 - x)^2 / (x^3 - 3x + 1)^2$,
$P(x) = x^3 - 3x + 1$, $Q(x) = 1/(x-1)$. Let r_1, r_2, r_3 be the roots
of $P$; note Q permutes them. In particular, the Galois group of Q(r_1,
r_2, r_3) (that's Q the rationals, of course) is cyclic. More on this
later.
Let $g(x)$ be an antiderivative of $f$ and let $h(x) = g(x) + g(P(x)) +
g(P(P(x)))$. We claim $h$ is a rational function with rational
coefficients (up to a constant of integration), which will solve our
problem.
Write f in its partial fraction decomposition A/(x - r_1) + B/(x - r_2) +
C/(x - r_3) + D/(x - r_1)^2 + E/(x - r_2)^2 + F/(x - r_3)^2. Observe that
g(x) = A log x - r_1 + B log x - r_2 + C log x - r_3 - D/(x - r_1) - E/(x
- r_2) - F/(x - r_3) (where I have to make some arbitrary choice about
where not to define log on the complex plane; no matter).
That means h(x) = (A + B + C)(log x - r_1 + log x - r_2 + log x - r_3)
+ (D + E + F)(1/(x - r_1) + 1/(x - r_2) + 1/(x - r_3)).
(I've long since dropped the constant of integration.)
But A + B + C = 0 from the partial fraction decomposition (A + B + C is
the coefficient of x^5 in the numerator of f(x)). So
h(x) = (D + E + F)(1 /(x - r_1) + 1/(x - r_2) + 1/(x - r_3)).
The inside is just P'(x) / P(x), which is clearly a rational function
with rational coefficients. So we need only show D + E + F is rational.
We could actually just compute it, but why bother? When you apply an
automorphism t of Q(r_1, r_2, r_3) to the coefficients of f, they're
unchanged. But t(D) becomes the coefficient of, say, 1/(x - r_2)^2, so
t(D) = E and similarly. The point is, D, E, F are conjugates, so the
trace of D, which is rational, is just D+E+F. And I'm done. (Whew! The
point is, my solution works for any quartic function in the numerator of
the integrand.)
A6: Keep in mind I was guided through this solution by previous knowledge
of problems of this ilk. Maybe you'll see what I mean in a moment.
The fact that $n = 1 + [rm]$ gives precisely the locations of the 2's in
the sequence is equivalent to the following fact:
[rn] - [r(n-1)] = 3 if n = 1 + [rm] for some m
4 otherwise.
(The point is that the locations of the 2's are just 1 + [rn] for n = 0,
1, 2, \dots.)
This in turn is equivalent to the following pair of facts:
(i) 3 < r < 4 and r is irrational;
(ii) r(n-1) - [r(n-1)] < 4-r iff n = 1 + [rm] for some m.
Again we rewrite the second condition to say:
There exists an integer s such that 0 < r(n-1) - s < 4-r
iff there exists an integer m such that 0 < rm - (n-1) < 1,
that is, such that 0 < (4 - r)rm - (4 - r)(n-1) < 4-r.
To find such r, we might as well just try setting
r(n-1) - s = (4 - r)rm - (4-r)(n-1)
which is to say
4(n-1) = s + (4 - r)rm.
And we claim here s is an integer iff m is an integer. Well, that's
guaranteed if (4 - r)r = 1, that is, r^2 - 4r + 1 = 0. (We choose 1
instead of -1 so that 3 < r < 4). The larger root of this is 2 + \sqrt 3
(NOT 2 + \sqrt 7, as I stupidly wrote while finishing this up in the last
two minutes!) and by the equivalences, that r satisfies the claim.
B1: The smallest such n is 3987. (Why can't I add? Just like last year, I
add 1993 and 1994 and get 3997. At least I was consistent about it.)
n can be no smaller because 1992/1993 < k/n < 1993/1994 must be soluble
for some k. Put j = n - k; then 1/1994 < j/n < 1/1993, which implies
1993j < n < 1994j. That's insoluble for j = 1, so j must be at least 2,
hence n is at least 3987.
On the other hand, one can show for 0 < m < 1993,
m/1993 < (2m+1)/3987 < (m+1)/1994.
B2: A never wins with perfect play by B. The simple reason is that B can
always guarantee that A will not win on the immediately following move.
Why? B holds one more card than A, and each of A's cards can cause only
one of B's cards to be a fatal play. Hence B has at least one safe play.
(Of course, B wins on the last move if not at any earlier point since the
sum of all cards is n(2n+1).)
B3: The closest integer to x/y is even iff 0 < x/y < 1/2 or
(4n-1)/2 < x/y < (4n+1)/2 for some integer n \geq 1. The former occurs
inside the triangle (0,0), (0,1), (1/2, 1), whose area is 1/4. The latter
occurs inside the triangle (0, 0), (1, 2/(4n-1)), (1, 2/(4n+1)), whose
area is 1/(4n-1) - 1/(4n+1). So the total area, which is the same as the
probability in a uniform distribution, is
1/4 + 1/3 - 1/5 + 1/7 - 1/9 + \cdots.
But we know \pi / 2 = 1 - 1/3 + 1/5 - 1/7 + cdots. (Say, from the series
expansion of arctan x. Yet ANOTHER place where Kiran made a calculation
error, dropping the 2 here.) So the final answer is
1/4 + (1 - \pi / 2) = 5/4 - \pi/2.
B4: No one seems to have solved this. Noam Elkies claimed a solution
afterwards, but I didn't follow it. The idea is to consider the linear
operator Tf(x) = \int_{0}^{1}{f(y)K(x,y) dy}. Life is MUCH easier if K(x,
y) = K(y, x); because then this operator is self-adjoint under the usual
inner product (f,g) = \int_{0}^1{f(x)g(x) dx}. But that's too much to
ask for.
B5: All solutions involve diddling with some sort of modulus, mostly mod
8 (since all odd squares are 1 there). My method:
write out the three cosines at one of the points in terms of the lengths.
Then relate them using the cosine addition formula
cos A+B = cos A cos B - sin A sin B.
The sine terms give you a humongous radical, but you can show that the
two terms under the radical are congruent to 3 mod 16, so the product is
congruent to 9 mod 16, and so the square root, which must be an integer
as it turns out, is +-3 mod 8. That ends up being a contradiction.
Aforementioned nice solution (due to Manjul Bhargava, the aforementioned
score of 7): Recall the formula for the volume of a tetrahedron in terms
of its six edges. (Or derive it. It comes to, V^2 is a five by five
determinant with fairly well-behaved entries. I think everything in there
is a square.) Then just prove mod 8 that the determinant is nonzero, so
the volume is nonzero, and the four points are not coplanar.
B6: No idea, sorry. The trouble is, some moves are reversible. Worse, you
can't always win just by making nonreversible moves. (From 1, 2, 4, you
must make the reversible move to 2, 2, 3 to win.) Argh!
Enjoy... Kiran
P.S. I should point out the reverse of the first bijection in A2.
Given j, S_{j+1}, \cdots, S_n, let f(A) be the maximum i such that
S_i \subseteq A. (Set S_j = the empty set to make this work in all cases.)
Also, I should point out why B4 is easy if K is symmetric. That makes
T self-adjoint. But since K is positive, T is positive definite with
respect to the given inner product, so all its eigenvalues are positive.
However, T(f - g) = g - f. Thus f - g = 0 otherwise f-g would be
an eigenvector of value -1, which is not allowed. (I'm actually not so
sure about the positive definiteness. Hmm. Let me get back to you all on that.)
------
I've just learned these solutions to B4 and B6. (Both solutions
devised shortly after the exam.)
B4: Let T be the operator I alluded to earlier. Notice that if
h is nonnegative and not identically zero, then Th is positive
everywhere. Now consider the expression f - rg. Clearly
T^2(f - rg) = f - rg. Let r be the smallest real such that f - rg
is nonnegative; that means it has a zero somewhere. But T(f - rg)
is strictly positive unless f - rg = 0, so T^2(f - rg) = f - rg is
too, contradiction. So f - rg = 0. That means Tf = Trg = rTg = rf,
and T^2f = r^2f = f. So r^2 = 1, and since r >= 0, r = 1, and
we're done. (Sorry. I meant r is the biggest real such that f - rg
is nonnegative. Clearly r >= 0.)
B6: I haven't sorted this out yet. But the idea is to show that,
assuming we never reach a zero doing this, that if two of x, y, z
are divisible by 2^n, we can reach a state where two are divisible
by 2^{n+1}. Since x + y + z is fixed, this will give a contradiction.
Clearly we can assume x+y+z is odd (otherwise just move to make all three
even and pretend we're working with half the numbers involved, and
repeat), and that two of x,y, z start out even (just move two odd
ones otherwise). So we start with n = 1.
Lemme see if I remember this. The result is trivial if both of the
multiples of 2^n are divisible by 2^{n+1}, or if neither is (they
both will be after one move on them). So assume one is a multiple of
2^{n+1} and the other is not. So mod 2^{n+1}, the numbers are
0, 2^n, x, where x is some odd number.
Move on the 0 and x until the 0 is larger. (This happens sooner or
later since it isn't ACTUALLY zero, and clearly as long as the 0 is
smaller the congruence mod 2^{n+1} is preserved.) Then move on them
once more to get 2x, 2^n, -x (still modulo).
If the 2^n is larger than the -x, we move them to 2^n + x and -2x.
Repeated moves now on 2x and -2x eventually produce 0, 0 (regardless
of which is bigger!). So suppose the 2^n is less than the -x. Move
them anyway to get 0, 2^n - x (remember 2^n = -2^n mod 2^{n+1}).
So we have 0, 2x, 2^n - x. Move the 0 and the 2^n - x until the 0 is
bigger, then move once more to get -2x, 2x, 2^n + x. Again move
2x and -2x until both become 0, and the induction follows.
(Both solutions due to Dylan Thurston, who, like everyone else, seems
to have solved about six questions.)
Kiran
Come to think of it, I'm no longer convinced my A5 actually works.
Certainly the claim I make in the middle about the integrand coming
out to that nice pair of terms when you put in x, 1/(1-x) and 1 - 1/x
is false. I still believe the result holds with any quartic polynomial
on top (of course you need only check five examples to prove or
disprove this) but I don't claim to have a full proof of that.
So that means my score should most properly be pegged at "9-something",
namely A1, A2, A3, A4, A6, B1, B2, B3, B5, maybe some scraps on
A5, and nothing on B4 or B6.
Kiran