Spoilers to the Putnam '94 exam follow. Last year I commented that the
questions were harder than usual; this year I think the reverse is true.
I note in particular a paucity of geometry questions (which tend to
be elementary but difficult) and of advanced undergraduate course
questions (which tend to be easy if you've taken the right course). I
think for typical undergraduates this test was pretty appropriate.
I won't comment here on generalizations or connections with interesting
theorems, although there are a number of interesting points to make.
I posted solutions to sci.math for all but A6 and B4. I've
incorporated responses from several other people as well as
independent solutions from Dan Bernstein (who posted a complete set)
when these improved or corrected mine. I adjusted the exposition a bit
from the original post, but I'm not claiming these are either the clearest
or the slickest proofs.
--- dave rusin@math.niu.edu
A1. Let S_n = a_{2^n}+...+a_{2^(n+1)-1}. Then the series is the sum of
all the S_n. The given inequalities, added together, imply
S_n < S_{n+1}. Hence the sum is larger than a sum of infinitely many a_1's,
which diverges.
A2. Apply a linear transformation which transforms the ellipse to a circle:
f(x,y) = (x/3, y) will do. This also carries lines through the origin to
other such lines; the lines in question go to y=(3/2)x and y=(3m) x
respectively. The effect on all areas is to multiply them by det(A)=(1/3),
but in particular equal areas stay equal.So the question is how to make
the lines y=(3/2)x and y=(3m)x subtend equal portions of a circle with
the two axes. Clearly (interchanging x and y) the second line ought
to be x=(3/2)y, i.e. y=(2/3) x. So it would appear that m=2/9 is needed.
Noam Elkies adds:
Simpler yet: apply the linear transformation g(x,y)=(3y,x/3).
This preserves areas, preserves (x^2)/9+y^2 and thus the ellipse,
switches the x and y axes, and takes y=3x/2 to the desired line
all in one step.
A3. (The solutions I posted was faulty but in the right direction. This
correction is based on Bernstein's posted solution.)
Suppose not. Then there is a coloring with 4 colors in which all the
points of each color lie strictly closer than D=2-sqrt(2) apart.
Consider the three vertices v1 (where the 90-degree angle is), v2, and
v3. Let the points p2 and p3 be as follows: p_i is on the line
segment joining v_i to v1, and is of distance D from v_i. Likewise
let q_i be the points on the hypotenuse of distance D from v_i
Many pairs of these are of distances at least D apart and so are
of different colors. In particular, the vertices must be of three
different colors, say colors 1, 2, and 3 at v1, v2, and v3
respectively. The point p2 is too far from v2 or v3 to have the same
color as those points, and so is of color 1 or 4. The same is true of
p3, but d(p2, p3) = D, so these two are of different colors, say, p2
is of color 1 and p3 is of color 4. By the same reasoning q2 and q3
are of colors 1 or 4, but since d(p2, q2) = D [proof: v2, p2, q2, and
p3 form a rhombus] the choice must be such that p2 has the same color (1)
as q2.
Now we have a contradiction since v1 and q2 are too far apart to have the
same color.
A4. Let f(r)=det(A+rB). This is a quadratic polynomial in r. Now,
since A+rB is integral with integral inverse, for several r,
it follow the determinants of these matrices have the same property,
i.e. are +1 or -1. But by pigeonhole principle, at least one of
these values must be obtained 3 times or more, which is impossible
for a non-constant polynomial of degree <=2. Hence f(r) is
constant, i.e. identically +1 or -1. Either way, we then have
(A+rB)^-1 = f(r)^-1. adj(A+rB), which is another integral matrix;
this applies to all r, including of course r=5.
A5. For any integer N >= 1, let S_N be the set of all sums of N
r_i's; S_1994 is the set S of the problem. We will show each
S_N has the desired property, by induction on N.
For N=1 this is trivial: if b<0 then any (a,b) doesn't meet S_1 at
all; if b>0 then by passing to a subinterval we may assume a>0
too. Then there are only finitely many r_i greater than a, so among
all of these let d = max (r_i - a). Then (a,b) contains the interval
(a, min(b,d) ) which does not meet S_1.
Now assume S_N has the desired property and assume (a,b) is given.
Find in it an interval (c,d) not meeting S_N. Let e = (c+d)/2 and
consider the right half-interval (e,d). No number in here can be
written as a sum of N+1 r's in which the last one is very small (less
than d-e), since that would require the sum of the first N terms to be
in S_N and in (c,e), contrary to the construction of (c,d).
Now, it is quite possible that (e,d) meets S_{N+1} by containing
sums the last term of which is one of the remaining r's which
happen to be larger than (d-e), but there are only finitely many
such r's to consider. Within (e-r1, d-r1), for example, we find
by induction an interval (x,y) not meeting S_N; then
(e'=x+r1, d'=y+r1) is a subinterval of (e,d) not containing any
sums in S_{N+1} in which the last term happens to be r1. Repeating
likewise we find a subinterval (e'', d'') of that containing no
elements of S_{N+1} in which the last term is either r1 or r2.
Iterating likewise for all the r_i's larger than e-d, we arrive
at an interval containing no elements of S_N in which the last term
is larger than e-d and, as we have already shown, none with last
term less than e-d either.
Noam Elkies adds:
The key is to use that a finite union of nowhere-dense sets in R
is nowhere dense to prove that if A is nowhere dense and r_n->0 then
A+{r_n} is nowhere dense. In particular it follows by induction
that B+B+B+...+B (1994 times) is nowhere dense where B={r_n}.
(Noam is referring to the Baire Category Theorem)
A6. W Jose Castrellon G solves as follows:
A-6 - By contradiction. If there are two compositions that work with both
e_10 = 0 and 1 then f_10 must map A to itself. Continue by induction for f_9...
Then they all leave A fixed, so the combination in the hyp couldn't exist.
So for each pair, one of them doesnt work, i.e. at most 512
D. J. Bernstein' solution clarifies the conclusion better, I think:
...So every f_i maps A to A.
If 0 is in A, select not in A; it is impossible for a composition of f_i's to
take 0 to n. If 0 is not in A, select n in A; it is again impossible for a
composition of f_i's to take 0 to n.
B1. If n is any positive integer, find the least square a^2 which is within
250 of it, that is, a^2 >= n-250 but (a-1)^2 < n-250. Then n is
in the solution set of this problem if and only if (a+14)^2 <= n+250
but (a+15)^2 > n+250. [We are assuming a>1 here. If a=0, the second
inequality has to be dropped, but no solutions n exist with a=0 anyway,
since the last inequality would require 225 > n + 250, and we are given that
n is positive.]
Subtracting appropriate pairs shows that if
n is a solution then 28a+196 <= 500 and 32a+224 > 500 which, for
integral a, mean 9<= a <= 10. Taking a=9 shows that
n must satisfy the inequalities n<=331, n>314, n>=279, and n<326,
that is, n=315,...,325. Likewise, taking a=10 shows the corresponding
values of n to be n=331,..., 350. Thus the complete solution set
is n=315, ..., 325, 331, ..., 350.
B2. We concentrate on the related question, for which values of p does
f(x) = x^4 + 2p x^2 + q x + r
have four distinct roots for some q and r.
Clearly, if p<0, then we can choose q=0 and r a
positive number less than |p|^2; then f has the four distinct roots
+- sqrt( |p| +- sqrt( |p|^2 - r ) ).
On the other hand, if p>=0 then the slope s(x)=4x^3+4px+q is increasing
(s'(x)=12x^2+4p>=0) and so never takes the same value twice; if there
were three roots, we would be able to apply Rolle's theorem twice to
find two zeros for s. Thus, for such p, our f has at most 2 roots.
The same reasoning works with quartics with non-zero coefficients of x^3,
but it is easier to use a translation left or right to reduce to the
previous case. Thus the polynomials g(x)=x^4+9x^3+cx^2+qx+r (with c fixed)
include some with four distinct roots iff the g(x-9/4)=x^4+(c-243/8)x^2+...
do. From the preceding paragraph this requires precisely that
c<243/8.
It is clear that finding such a g is equivalent to finding a line meeting
the given quartic in 4 distinct points, so for the original problem the
answer is again c < 243/8.
[Other solutions allow some variety in determining when a quartic has
four roots. Variants of the Mean Value Theorem, roots of the second derivative,
Descartes' Rule of Signs, Sturm sequences, and so on could be used.]
B3. The k's in question are the k<1.
Suppose that k<1 and that f is as stated. Then f>0 so we can consider
g=ln(f) - x, also differentiable for all x, and having g'(x) = f'(x)/f(x)-1>0.
Thus g is increasing, and so must cross the graph of any straight line
with negative slope. Hence if k < 1, then for all x's larger than some N
(depending on g and k of course) we will have g(x) > (k-1)x, which
means ln(f(x)) > k x, which is the desired conclusion.
Now suppose k >=1; we can build on the previous example and take g to
increase to the horizontal axis, say g(x) = -e^(-x). Then f(x) = exp(x-e^(-x))
has f'(x) = f(x).[ 1 + e^(-x) ] > f(x) but f(x)> e^(kx) requires
x-e^(-x) > kx = x + (k-1)x, which is not true for any positive x.
B4. Adapted from solutions by W Jose Castrellon G and D. J. Bernstein:
First observe by induction that all powers are of the form
A^n= [m p]
[2p m]
We will find integers x and y so that either
m+1 = 2x^2 , m-1= y^2 and p = xy, or
m+1 = x^2, m-1= 2y^2 and p = xy.
The first condition will hold for the even powers of A (starting with
x=3, y=4 for A^2), the other condition for the odd powers (starting
with x=2, y=1 for A^1).
It is awkward to determine a pattern for x and y,
because the conditions alternate with the powers of A.
However, there is a linear pattern for the x and y needed for _every
other_ power of A: indeed, if x'=3x+2y and y'=4x+3y, then from
m+1=2x^2, m-1=y^2, p=xy we obtain
2(x')^2 = 17m+24p+1 = m'+1
(y')^2 = 17m+24p-1 = m'-1
(x')(y')= 12m+17p = p'
where m' and p' are the entries in the top row of A^(n+2).
A similar pattern holds when we begin with m+1=x^2, m-1=2y^2, p=xy.
Since x, y >0 we have by induction that x>0, y'>3y>0, so that the
set of such elements y increases without bound. On the other hand,
it is clear that y divides all four entries m-1, p, 2p, and m-1
of A^n. Thus the gcd's go to infinity.
[Remark: I found it hard to start this problem. The key observation is that
det(A)=1 => det(A^n)=1, so m^2=2p^2+1, i.e., (m-1)(m+1)=2p^2. Then
unique factorization shows such x and y must exist, and moreover
shows that the gcd in question is either y or 2y. Knowing that a
linear recurrence for x and y ought to exist, it's easy to find what
coefficients to choose.]
B5. [Write A for \alpha]. Take A = e^(-1/n^2). Note that if 0< r <=1,
1-r+r^2/2 > e^(-r) > 1-r, so that in particular if 0 < k <= n we have
n^2(1-k/n^2 + k^2/(2n^4)) > A^k n^2 > n^2(1- k/n^2). The ends simplify to
n^2 - k + (1/2)(k/n)^2 and n^2-k respectively. The latter is an integer
and the former exceeds it by at most 1/2, so since A^k n^2 lies
between them, the greatest integer therein is indeed n^2-k. Thus the
second inequalities hold.
On the other side, note A(n^2-k) > (1-1/n^2)(n^2-k) = n^2-(k+1)+k/n^2
is greater than n^2-(k+1), but (as A<1 ) is less than n^2-k, so the
greatest integer here is n^2-(k+1). By induction we get the inequalities
on the left.
B6. Given this congruence mod 10100, the same congruence holds mod 100;
but mod 100, n_a =a, so the resulting congruence may be written
a+b = c+d (mod 100). Likewise reading mod 101 we get 2^a+2^b = 2^c+2^d
(mod 101). Now, 101 is prime so (using Fermat's congruence) the first of
our conclusions implies 2^(a+b) = 2^(c+d) mod 101, i.e. 2^a.2^b =2^c.2^d.
Thus the pairs { 2^a, 2^b} and {2^c, 2^d} (mod 101) have the same sums
and products, and so are roots of the same quadratic equation. Since
again Z/101 is a field, that means these pairs of roots must be equal.
Fortunately (since neither 2^50 nor 2^20 = 1) 2 is a
primitive root mod 101, so these congruences say the pairs {a,b} and
{c,d} are equal mod phi(101)=100. Since 0 <= a b c d < 100, these congruences
may be read as actual equalities among integers.
Dan Bernstein included the computations I skimmed over: modulo 101,
2^10=1024=14, 2^20=196=-6, 2^40=36, and 2^50=36.14=504=-1.