[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1530.0. "1991 Putnam Competition" by BEING::EDP (Always mount a scratch monkey.) Tue Dec 10 1991 16:07

Article: 23107
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: sci.math
Subject: 1991 Putnam problems and unofficial solutions
Message-ID: <7370.Dec903.37.4691@kramden.acf.nyu.edu>
Date: 9 Dec 91 03:37:46 GMT
Organization: IR
 
First, here are the problems. I suggest that the Putnam writers hire a
copy editor---we're in trouble when even the commas don't come in pairs.
 
 
Problem A-1
 
A 2x3 rectangle has vertices at (0, 0), (2, 0), (0, 3), and (2, 3). It
rotates 90 degrees clockwise about the point (2, 0). It then rotates 90
degrees clockwise about the point (5, 0), then 90 degrees clockwise
about the point (7, 0), and finally, 90 degrees clockwise about the
point (10,0). (The side originally on the x-axis is now back on the
x-axis.) Find the area of the region above the x-axis and below the
curve traced out by the point whose initial position is (1, 1).
 
 
Problem A-2
 
Let A and B be different nxn matrices with real entries. If A^3 = B^3
and A^2B = B^2A, can A^2 + B^2 be invertible?
 
 
Problem A-3
 
Find all real polynomials p(x) of degree n >= 2 for which there exist
real numbers r_1 < r_2 < ... < r_n such that (i) p(r_i) = 0, i = 1, 2,
...., n, and (ii) p'((r_i + r_{i+1})/2) = 0, i = 1, 2, ..., n - 1, where
p'(x) denotes the derivative of p(x).
 
 
Problem A-4
 
Does there exist an infinite sequence of closed discs D_1, D_2, D_3, ...
in the plane, with centers c_1, c_2, c_3, ..., respectively, such that
(i) the c_i have no limit point in the finite plane, (ii) the sum of the
areas of the D_i is finite, and (iii) every line in the plane intersects
at least one of the D_i?
 
 
Problem A-5
 
Find the maximum value of $\int_0^y \sqrt{x^4+(y-y^2)^2}\, dx$ for
0 <= y <= 1.
 
 
Problem A-6
 
Let A(n) denote the number of sums of positive integers a_1 + a_2 + ...
+ a_r which add up to n with
 
a_1 > a_2 + a_3, a_2 > a_3 + a_4, ..., a_{r-2} > a_{r-1} + a_r, a_{r-1} > a_r.
 
Let B(n) denote the number of b_1 + b_2 + ... + b_s which add up to n,
with
 
(i) b_1 >= b_2 >= ... >= b_s,
(ii) each b_i is in the sequence 1, 2, 4, ..., g_j, ... defined by g_1 =
1, g_2 = 2, and g_j = g_{j-1} + g_{j-2} + 1, and
(iii) if b_1 = g_k then every element in {1, 2, 4, ..., g_k} appears at
least once as a b_i.
 
Prove that A(n) = B(n) for each n >= 1.
 
(For example, A(7) = 5 because the relevant sums are 7, 6 + 1, 5 + 2, 4
+ 3, 4 + 2 + 1, and B(7) = 5 because the relevant sums are 4 + 2 + 1, 2
+ 2 + 2 + 1, 2 + 2 + 1 + 1 + 1, 2 + 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1
+ 1 + 1.)
 
 
Problem B-1
 
For each integer n >= 0, let S(n) = n - m^2, where m is the greatest
integer with m^2 <= n. Define a sequence (a_k)_{k=0}^\infty by a_0 = A
and a_{k+1} = a_k + S(a_k) for k >= 0. For what positive integers A is
this sequence eventually constant?
 
 
Problem B-2
 
Suppose f and g are non-constant, differentiable, real-valued functions
defined on (-\infty, \infty). Furthermore, suppose that for each pair of
real numbers x and y,
 
   f(x + y) = f(x)f(y) - g(x)g(y),
   g(x + y) = f(x)g(y) + g(x)f(y).
 
If f'(0) = 0, prove that (f(x))^2 + g((x))^2 = 1 for all x. [The last
equation was probably a typo; it should read (f(x))^2 + (g(x))^2 = 1.]
 
 
Problem B-3
 
Does there exist a real number L such that, if m and n are integers
greater than L, then an mxn rectangle may be expressed as a union of 4x6
and 5x7 rectangles, any two of which intersect at most along their
boundaries?
 
 
Problem B-4
 
Suppose p is an odd prime. Prove that
 
$$\sum_{j=0}^p {p\choose j}{p + j\choose j} \cong 2^p + 1 \pmod p^2.$$
 
 
Problem B-5
 
Let p be an odd prime and let Z_p denote (the field of) the integers
modulo p. How many elements are in the set
 
{ x^2 : x \in Z_p } \intersect { y^2 + 1 : y \in Z_p } ?
 
 
Problem B-6
 
Let a and b be positive numbers. Find the largest number c, in terms of
a and b, such that
 
a^x b^{1-x} <= a{\sinh ux\over\sinh u} + b{\sinh u(1-x)\over\sinh u}
 
for all u with 0 < |u| <= c and for all x, 0 < x < 1. (Note: sinh u =
(e^u - e^{-u})/2.)

Here are some unofficial but complete (except for B6) solutions. Overall
it seemed rather easy. Problem A-2 is the first Putnam problem I've seen
admitting a rigorous, one-line solution.
 
 
Problem A-1
 
A 2x3 rectangle has vertices at (0, 0), (2, 0), (0, 3), and (2, 3). It
rotates 90 degrees clockwise about the point (2, 0). It then rotates 90
degrees clockwise about the point (5, 0), then 90 degrees clockwise
about the point (7, 0), and finally, 90 degrees clockwise about the
point (10,0). (The side originally on the x-axis is now back on the
x-axis.) Find the area of the region above the x-axis and below the
curve traced out by the point whose initial position is (1, 1).
 
Solution: Draw a picture. The point (1, 1) rotates around (2, 0) to
(3, 1), then around (5, 0) to (6, 2), then around (7, 0) to (9, 1), then
around (10, 0) to (11, 1). Consider the ray between the current center
of rotation and the current position of the point which began at (1, 1).
Since each rotation goes through 90 degrees, this ray sweeps out one
fourth of a circle each time---of radius \sqrt{2} on the first rotation,
\sqrt{5} on the second, \sqrt{5} on the third, and \sqrt{2} on the last.
Thus the ray sweeps over an area of (1/4)\pi(2 + 5 + 5 + 2) = 7\pi/2.
The desired area includes the area swept out by the ray, plus five
triangles of combined area 1/2(1 + 3 + 4 + 3 + 1) = 6, for a total of
6 + 7\pi/2.
 
This problem was so straightforward that the judges will undoubtedly pay
far too much attention to irrelevant technical details, such as why (1, 1)
moves where it does, and why the arcs traced out are circular, and so on.
 
 
Problem A-2
 
Let A and B be different nxn matrices with real entries. If A^3 = B^3
and A^2B = B^2A, can A^2 + B^2 be invertible?
 
Solution: No. If C(A^2 + B^2) = I then A - B = C(A^2 + B^2)(A - B) =
C(A^3 + B^2A - A^2B - B^3) = C0 = 0 so A = B. Contradiction.
 
 
Problem A-3
 
Find all real polynomials p(x) of degree n >= 2 for which there exist
real numbers r_1 < r_2 < ... < r_n such that (i) p(r_i) = 0, i = 1, 2,
...., n, and (ii) p'((r_i + r_{i+1})/2) = 0, i = 1, 2, ..., n - 1, where
p'(x) denotes the derivative of p(x).
 
Solution: p(x) must be a quadratic with two distinct real roots. Indeed,
since p has at most n roots and r_1 through r_n are among those roots, p
must factor as C(x - r_1)(x - r_2)(x - r_3)...(x - r_n) where C is any
nonzero constant. Then, at any point x not equalling any r_i, p'(x)/p(x)
equals 1/(x - r_1) + 1/(x - r_2) + ... + 1/(x - r_n). In particular, for
x = (r_1 + r_2)/2, the first two terms cancel and the remaining terms
are all negative. If n >= 3 then there is at least one of those
remaining terms, so p'(x)/p(x) is strictly negative, but p'(x) is zero
by hypothesis. Contradiction. Thus n = 2, and p(x) is a quadratic
C(x - r_1)(x - r_2) with two distinct real roots. Any such quadratic
does satisfy the given conditions, as p'(x) then equals C(x - r_1) +
C(x - r_2) = C(2x - (r_1 + r_2)), and this is zero for x = (r_1 + r_2)/2.
 
 
Problem A-4
 
Does there exist an infinite sequence of closed discs D_1, D_2, D_3, ...
in the plane, with centers c_1, c_2, c_3, ..., respectively, such that
(i) the c_i have no limit point in the finite plane, (ii) the sum of the
areas of the D_i is finite, and (iii) every line in the plane intersects
at least one of the D_i?
 
Solution: Yes. For example, let X_n be the disc of radius 10/n centered
at (H_n,0), for all integers n > 0. Here H_n = 1 + 1/2 + 1/3 + ... + 1/n,
which diverges. Clearly the collection of discs X_n covers the positive
x axis including the origin. Similarly define Y_n along the positive y
axis, X'_n along the negative x axis, and Y'_n along the negative y
axis. Then set D_{4n} = X_n, D_{4n - 1} = Y_n, D_{4n - 2} = X'_n, and
D_{4n - 3} = Y'_n for all integers n > 0. The D_n cover both the x axis
and the y axis, so they intersect any given line in the plane. Their
total area is the sum of 4/n^2 for n > 0, which is finite. The centers
have no limit point since in any given ball there are only finitely many
of the centers.
 
 
Problem A-5
 
Find the maximum value of $\int_0^y \sqrt{x^4+(y-y^2)^2}\, dx$ for
0 <= y <= 1.
 
Solution: The derivative with respect to y of \int_0^{f(y)}g(x,y) dx
is g(f(y),y)f'(y) + \int_0^{f(y)}g_y(x,y) dx, where g_y is the partial
derivative of g with respect to y. So the derivative of the integral we
are asked to maximize, at any y with 0 < y < 1, is
 
D = \sqrt{y^4 + (y - y^2)^2} + (1-2y)\int_0^y (y-y^2)/\sqrt{x^4+(y-y^2)^2} dx.
 
Call the new integral I. The integrand is everywhere positive as y>y^2.
Also the denominator dominates the numerator, so I is between 0 and y.
If y <= 1/2 then (1-2y)I is nonnegative so D is positive. If y > 1/2
then |(1-2y)I| < y(2y-1) = y\sqrt{1-4y(1-y)} < y\sqrt{1-2y(1-y)} so D is
again positive. Hence the maximum can only be at the right endpoint,
where the integral is \int_0^1 x^2 dx = 1/3.
 
Another solution is to observe that \sqrt{x^4+(y-y^2)^2}<=x^2+y-y^2, so
the integral in the problem is bounded by y^3/3+y^2-y^3 = y^2(1 - 2y/3),
which is increasing on (0,1) and hence everywhere bounded by its value
at 1, namely 1/3. So the maximum can't possibly exceed 1/3, but the
original integral achieves 1/3 at 1. Q.E.D. Thanks to Peter Montgomery
and others for this solution. Thanks to Peter Montgomery also for
catching an error in my solution.
 
 
Problem A-6
 
Let A(n) denote the number of sums of positive integers a_1 + a_2 + ...
+ a_r which add up to n with
 
a_1 > a_2 + a_3, a_2 > a_3 + a_4, ..., a_{r-2} > a_{r-1} + a_r, a_{r-1} > a_r.
 
Let B(n) denote the number of b_1 + b_2 + ... + b_s which add up to n,
with
 
(i) b_1 >= b_2 >= ... >= b_s,
(ii) each b_i is in the sequence 1, 2, 4, ..., g_j, ... defined by g_1 =
1, g_2 = 2, and g_j = g_{j-1} + g_{j-2} + 1, and
(iii) if b_1 = g_k then every element in {1, 2, 4, ..., g_k} appears at
least once as a b_i.
 
Prove that A(n) = B(n) for each n >= 1.
 
(For example, A(7) = 5 because the relevant sums are 7, 6 + 1, 5 + 2, 4
+ 3, 4 + 2 + 1, and B(7) = 5 because the relevant sums are 4 + 2 + 1, 2
+ 2 + 2 + 1, 2 + 2 + 1 + 1 + 1, 2 + 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1
+ 1 + 1.)
 
Solution: First we observe that for any sequence a_1, a_2, a_3, ...,
which is zero past some point, we have a_1 + a_2 + a_3 + ... =
(a_1 - (a_2 + a_3))g_1 + (a_2 - (a_3 + a_4))g_2 + (a_3 - (a_4 + a_5))g_3
+ ..., for the coefficients of various a_i are (i = 1) g_1 = 1,
(i = 2) -g_1 + g_2 = 1, (i > 2) -g_{i-2} - g_{i-1} + g_i = 1.
 
Consider a sum from A(n). Pad the a_i's with zeros, so that in general
a_i >= 0, a_i > a_{i+1} + a_{i+2} for i <= r, a_i = 0 for i > r. By our
previous observation, n also equals the sum of (a_i-a_{i+1}-a_{i+2})g_i,
and these coefficients are positive for i <= r, zero for i > r. Write
this sum in reverse and split (a_i-a_{i+1}-a_{i+2})g_i into
a_i-a_{i+1}-a_{i+2} copies of g_i. It is clear that this satisfies the
conditions for a B sum. It is also clear that this map from A sums to B
sums is invertible, for given the multiplicities h_i of each g_i up to
g_r, we can recover a_i by working backwards from a_r = h_r. Hence A(n)
equals B(n).
 
 
Problem B-1
 
For each integer n >= 0, let S(n) = n - m^2, where m is the greatest
integer with m^2 <= n. Define a sequence (a_k)_{k=0}^\infty by a_0 = A
and a_{k+1} = a_k + S(a_k) for k >= 0. For what positive integers A is
this sequence eventually constant?
 
Solution: Fix n and define m as in the problem. I claim that n + S(n) <
(m+2)^2. Indeed, n < (m+1)^2 by construction of m, so n - m^2 < 2m + 1,
so n + S(n) = n + n - m^2 < n + 2m + 1 < (m+1)^2 + 2m + 1 = m^2 + 4m + 2
< (m+2)^2. Next I claim that n + S(n) is not a perfect square if n is
not a square. Indeed, n > m^2 so S(n) > 0 so n + S(n) > m^2; and
certainly n + S(n) < (m+2)^2; so n + S(n) can be a square only if it
equals (m+1)^2. But n + S(n) - (m+1)^2 = 2n - m^2 - m^2 - 2m - 1 which
is odd and hence nonzero.
 
Finally, if a_k is not a square, then a_{k+1} is not a square, and
S(a_k) will never reach 0. So the sequence is eventually constant only
if it is initially constant, i.e., A is a square.
 
 
Problem B-2
 
Suppose f and g are non-constant, differentiable, real-valued functions
defined on (-\infty, \infty). Furthermore, suppose that for each pair of
real numbers x and y,
 
   f(x + y) = f(x)f(y) - g(x)g(y),
   g(x + y) = f(x)g(y) + g(x)f(y).
 
If f'(0) = 0, prove that (f(x))^2 + g((x))^2 = 1 for all x. [The last
equation was probably a typo; it should read (f(x))^2 + (g(x))^2 = 1.]
 
Solution: (Am I the only one annoyed by this careless use of the word
``suppose''? One *assumes* something which will remain true throughout
the discussion. One *supposes* something which will lead to a
contradiction.) Expand g(x + 0) and f(x + 0) to see that g(x)(1 - f(0))
= f(x)g(0) and f(x)(1 - f(0)) = -g(x)g(0). Thus f(x)g(x)(1 - f(0))^2
= -f(x)g(x)g(0)^2, so 2f(x)g(x)((1 - f(0))^2 + g(0)^2) = 0. Also
2f(x)g(x) = g(2x), and since g is nonconstant there must be some x for
which g(2x) is nonzero. Thus (1 - f(0))^2 + g(0)^2 = 0 and hence f(0) =
1, g(0) = 0. Thus f(0)^2 + g(0)^2 = 1. To complete the proof we need
only show that the derivative of (f(x))^2 + (g(x))^2, i.e., double
f'(x)f(x) + g'(x)g(x), is zero.
 
Consider f(x + h) = f(x)f(h) - g(x)g(h). Then (f(x + h) - f(x))/h =
f(x)((f(h)-1)/h) - g(x)g(h)/h = f(x)(f(h)-f(0))/h - g(x)(g(h)-g(0))/h.
All three difference quotients tend to limits as h approaches 0: to wit,
f'(x) = f(x)f'(0) - g(x)g'(0). Similarly g'(x) = f(x)g'(0) + g(x)f'(0).
Since by assumption (supposition?!) f'(0) = 0, we have f'(x) = -g(x)g'(0)
and g'(x) = f(x)g'(0). Thus f'(x)f(x) + g'(x)g(x) =
(g(x)f(x)-f(x)g(x))g'(0) = 0 as desired.
 
In checking one's work for this sort of problem it helps to make sure
that the equations work out correctly for special cases---in this case,
f(x) = cos(x), g(x) = sin(x) practically leap off the page.
 
 
Problem B-3
 
Does there exist a real number L such that, if m and n are integers
greater than L, then an mxn rectangle may be expressed as a union of 4x6
and 5x7 rectangles, any two of which intersect at most along their
boundaries?
 
Solution: The problem is ambiguous; must an mxn rectangle have m rows
and n columns, or could it have m columns and n rows? I assume that both
orientations are valid, so that we can use 4x6, 5x7, 6x4, and 7x5
rectangles. Under this interpretation, the answer is yes.
 
Let p(m,k) be the proposition ``any rectangle with m rows and kn columns
may be expressed as a union of 4x6, 5x7, 6x4, and 7x5 rectangles
intersecting at most along their boundaries, for sufficiently large n.''
Clearly p(4,6), p(5,7), p(6,4), p(7,5). Also if p(m,k) and p(m,j) then
p(m,d) where d is the gcd of j and k, for any multiple of d larger than
jk can be expressed as a nonnegative integer combination of j and k.
Also p(m,k) and p(n,k) together imply p(m+n,k), and p(m,k) implies
p(m,tk). We compute: p(8,6). p(4,12). p(6,12). p(10,12). p(5,7).
p(10,7). p(10,1). p(7,5). p(14,5). p(10,6). p(4,6). p(14,6). p(14,1).
p(15,7). p(7,30). p(8,30). p(15,30). p(15,1). Thus we can construct any
rectangle with 14 or 15 rows and n columns, for n larger than some
number, say M. Given any rectangle of m rows and n columns with m > 210
and n > M, we may write m as a sum of 14's and 15's, and hence may
construct the mxn rectangle. Q.E.D. We choose L as max{210,M}.
 
 
Problem B-4
 
Suppose p is an odd prime. Prove that
 
$$\sum_{j=0}^p {p\choose j}{p + j\choose j} \cong 2^p + 1 \pmod p^2.$$
 
Solution: 2^p equals 2 + \sum_{j=1}^{p-1} p choose j. Each term of the
sum is divisible by p; set c(p,j)=(p choose j)/p, so that 2^p - 2 equals
\sum pc(p,j). p+j choose j is congruent to 1 mod p, so the sum of
c(p,j)((p+j choose j) - 1) is divisible by p, so the sum of
pc(p,j)((p+j choose j) - 1) is divisible by p^2, so that 2^p - 2 is
congruent to \sum_{j=1}^{p-1} (p choose j)(p+j choose j) mod p^2.
Furthermore, (p choose 0)(p choose 0) equals 1. So we need only show
that (p+p choose p) is congruent to 2 mod p^2. But this follows from the
identity (p+p choose p) = \sum_{k=0}^p (p choose k)(p choose k), where
all the terms for 0 < k < p are divisible by two factors of p, and the
outer terms equal 1. Q.E.D.
 
 
Problem B-5
 
Let p be an odd prime and let Z_p denote (the field of) the integers
modulo p. How many elements are in the set
 
{ x^2 : x \in Z_p } \intersect { y^2 + 1 : y \in Z_p } ?
 
Solution: First note that x^2 = y^2 + 1 is equivalent to (x+y)(x-y) = 1.
Inside Z_p, 2 is invertible, so the set of pairs (x,y) is equivalent to
the set of pairs (u,v) under the map u = x+y, v = x-y; this map is
invertible since its determinant is 2. Under this equivalence, x^2 =
y^2 + 1 becomes uv = 1. So the pairs (x,y) for which x^2 = y^2 + 1 are
in one-to-one correspondence with the pairs (u,v) for which uv = 1,
which are in one-to-one correspondence with the elements u which are
units in the field, i.e., nonzero elements.
 
So given any nonzero u we construct v = 1/u and x = (u+v)/2 = (u+1/u)/2,
then x^2 = (u+1/u)^2/4. This is in our set. How many distinct such x^2
can we produce? It suffices to consider the range of u^2 + 1/u^2 over
all units u. If u^2 + 1/u^2 = w^2 + 1/w^2 then u^2 - w^2 = 1/w^2 - 1/u^2
= (u^2 - w^2)/(uw)^2 so either u^2 = w^2 or (uw)^2 = 1 so either u = w,
u = -w, uw = 1, or uw = -1. Conversely, u^2 + 1/u^2 and w^2 + 1/w^2
coalesce in each of these four cases. Hence the size of our set is the
number of equivalence classes left after we identify each element with
its negative and then identify each element with its reciprocal.
 
If u is not 1 or -1, and u^2 does not equal -1, then u, -u, 1/u, and
-1/u are all distinct. 1 and -1 join the same equivalence class. Also
the square roots of -1, if any, join the same equivalence class. If p is
congruent to 1 mod 4 then there are 2 square roots of -1; a class for 1
and -1; and (p-5)/4 classes of other units; for a total of (p+3)/4. If p
is congruent to 3 mod 4 then there are no square roots of -1; 1 and -1;
and (p-3)/4 classes of other units; for a total of (p+1)/4.
 
 
Problem B-6
 
Let a and b be positive numbers. Find the largest number c, in terms of
a and b, such that
 
a^x b^{1-x} <= a{\sinh ux\over\sinh u} + b{\sinh u(1-x)\over\sinh u}
 
for all u with 0 < |u| <= c and for all x, 0 < x < 1. (Note: sinh u =
(e^u - e^{-u})/2.)
 
Solution: Since sinh ux/sinh u and sinh u(1-x)/sinh u are odd functions
of u, we may restrict attention to 0 < u <= c, where sinh u > 0. Also we
may assume a >= b: otherwise replace x by 1 - x. After this, I am told
by Peter Montgomery that c should equal ln(a/b) (or |ln(a/b)| in the
general case; to see this, consider x = 1/2), but I don't have a proof
that this is a sufficiently small value.
 
---Dan
T.RTitleUserPersonal
Name
DateLines