Some suggested answers to the 1997 Putnam exam. The first part is the set
of solutions as I originally deposited them the evening after the test.
At the end I have some posts to the newsgroup sci.math which fill in the
holes and correct the calculations in B6.
dave rusin@math.niu.edu
------------------------------------------------------------------------------
A1. Let us commit the heresy of introducing coordinates with O at the
center, so we have points
O: (0,0) H: (-11,0) F: (-11, -5) M:(0,-5).
The descriptions of M and O make B and C equidistant from both of
them; thus the line of points equidistant from B and C is the vertical
axis. Since BC is then horizontal and contains F we have coordinates
B: (-x, -5) C: (x, -5).
Since FH is in the altitude through A, we also have the point A:(-11,y).
The altitude through B passes through H, so its slope is 5/(x-11). THe
line AC has slope - (y+5)/(x+11). Since those two are perpendicular, we
find x^2-11^2 = 5(y+5) = 5y + 25
On the other hand, A and B are equidistant from O too, so we find
y^2+11^2=x^2+5^2, i.e. x^2-11^2 = y^2-25.
Comparing these equations shows y^2-5y-50=0, i.e. y=10 (not -5). Then
x = 14, so segment BC has length 28.
------------------------------------------------------------------------------
A2.
------------------------------------------------------------------------------
A3. I don;t know. The first factor is x*exp(-x^2/2). The second is a
Bessel function or hypergeometric or something, but the key property
(I suppose) is that it satisfies a DE xg'' + g' = x g. Thus an
integral int x f g can be written int f (x g') ' and we can use
integration by parts twice. But I end up with int x^2 f g, which doesn't
close the loop quite like I expected. Hmm.
------------------------------------------------------------------------------
A4. This is essentially a group cohomology question, asking us to recognize
some 1-cycles.
From the equation x e x^(-1) = e x x^(-1) we deduce (after cancellation)
that phi(x) phi(e) = phi(e) phi(x), i.e., whatever E = phi(e) is, it's in the
center of G.
From the equation x x^(-1) e = e e e we deduce (after cancellation) that
phi(x) phi(x^(-1)) = E^2, so phi(x^(-1)) = phi(x)^(-1) E^2.
From the equation y^(-1) x^(-1) (xy) = e e e we deduce
phi(y^(-1)) phi(x^(-1)) phi(xy) = E^3; from the previous two paragraphs we
see this becomes
phi(y)^(-1) phi(x)^(-1) phi(xy) = E^(-1).
If we set psi(x) = E^(-1) phi(x), then this implies
psi(xy) = E^(-1) phi(xy) = E^(-2) phi(x) phi(y) = psi(x) psi(y)
so psi is indeed a homomorphism.
------------------------------------------------------------------------------
A5. The symmetric group S_10 acts on the n-tuples in the obvious way, and
so breaks the collection of them into orbits; each orbit is of cardinality
[S_10 : G] where G is the stabilizer of an element in that orbit. This
stabilizer is easy to compute: within a given S_10 orbit we may obviously
find a unique representative with a_1 <= a_2 <= ... <= a_10. Its stabilizer
G is the product of symmetric groups S_(n1) x S_(n2) x ..., where
a_1 = a_2 = ... = a_(n1) < a_(n1+1) = ... = a_(n1+n2) < ...
Thus the number of elements in that orbit is 10! / (n1! n2! ... ).
(Note that n1 + n2 + ... = 10.).
To decide whether this is even or odd, we look at the cardinality of the
2-Sylow subgroups, that is, the 2-part of this product of factorials. We
computer 2^r || n! as shown in this table:
n 1 2 3 4 5 6 7 8 9 10
r 0 1 1 3 3 4 4 7 7 8
Now consider the partitions of 10:
10 = 10
10 = 9 + 1 (or 1 + 9)
10 = 8 + 2
10 = 8 + 1 + 1
etc. Each partition determines a subgroup as above, we can compute the
2-part of its index. For example, the partition 10 = 8 + 2 determines a
subgroup of order 2^7 * 2^1 * odd, which is therefore of odd index in S_10.
Rather than enumerate all partitions, observe that if any summand n_i is
equal to 1, the corresponding stabilizer group has S_1 = {e} as a factor,
and so up to isomorphism is a subgroup of S_9, whose index in S_10 is
already even. So it suffices to consider partitions with all summands > 1:
10 = 10, 8+2, 7+3, 6+4, 5+5, 6+2+2, 5+3+2, 4+4+2, 4+3+3, 4+2+2+2,
3+3+2+2, and 2+2+2+2+2.
We compute the 2-power of the stabilizer from the table above: respectively,
8, 8, 5, 5, 6, 6, 5, 7, 5, 6, 4, 5
Very well, then, all orbits have stabilizers of odd index except those with
stabilizer isomorphic to S_10 or S_2 x S_8. Thus, all ordered 10-tuples
of solutions to the original equation fall into orbits of even length except
those of the form a_1 + ... = a_10 ( = 10, obviously) or of the form
a_1 = a_2 <> a_3 + ... + a_10.
Call these last two numbers x = a_1 and y = a_10. Then we are to have
2/x + 8/y = 1, or y = 8x/(x-2). Since gcd(x,x-2) = 1 or 2, the integrality
of this y forces x-2 to divide 8, if x is odd, and forces x/2 -1 to
divide 8 if x is even. This gives solutions x=3, 4, 6, 10, 18
(with y=24, 16, 12, 10, 9 respectively). Note that this includes the
case x=y of the previous paragraph.
Thus there are evenly many permutations of all solutions except the
oddly many permutations of solutions (3, 3, 24, 24, ...), (4, 4, 16, ...),
(6, 6, 12, 12, ...), (18, 18, 9, 9, ...), and of course (10,10, ...).
N_10 is ODD.
------------------------------------------------------------------------------
A6.
------------------------------------------------------------------------------
B1. Their {x} is only applied to numbers in (0, 2). In particular,
{m/6n} = m/6n, if m < 3n, and otherwise is (6n-m)/m. The other
{m/3n} is a bit harder, but is clearly one of
m/3n, if m < (3/2)n
(3n-m)/3n, if (3/2)n <= m <= 3n
(m-3n)/3n, if 3n < m < (9/2)n
(6n-m)/3n, if (9/2)n <= m < 6n
So we are asked to compute a sum of terms of the form (1/6n)*min(A,B).
These A and B are, in the various intervals,
m and 2m, if m < (3/2)n
m and 2(3n-m), if (3/2)n <= m <= 3n
6n-m and 2(m-3n), if 3n < m < (9/2)n
6n-m and 2(6n-m), if (9/2)n <= m < 6n
We can select the minimum in finer ranges: it's
m, if m < (3/2)n
m, if (3/2)n <= m <= 2n
6n-2m, if 2n < m <=3n
2m-6n, if 3n <= m <=4n
6n-m, if 4n <= m < (9/2) n
6n-m, if (9/2)n <= m < 6n
So we sum m for m = 1, 2, ..., 2n and get (2n)(2n+1)/2;
we sum 6n-2m for m = 2n+1, ..., 3n and get 6n(n) - ((3n)(3n+1)-(2n)(2n+1));
we sum 2m-6n for m = 3n+1, ..., 4n and get ((4n)(4n+1)-(3n)(3n+1)) - 6n(n);
we sum 6n-m for m = 4n+1, ..., 6n-1 and get (2n-1)+...+1 = (2n-1)(2n)/2.
Looks to me like the sum is 6n^2, so S_n = n .
(I'm positive there's a better solution somewhere!)
------------------------------------------------------------------------------
B2. We are given that
f f' + f' f'' = - x g (f')^2.
But the left side is half the derivative of F = f^2+(f')^2; the right side
is clearly <= 0 for x>0 and >=0 for x < 0. So F is increasing on
( - oo , 0 ) and decreasing on (0, oo ). In particular, its maximum
value is at x=0. Of course its bounded below by zero, too, so F is
bounded. It follows that f (and f') are also bounded.
This is a simple variant of the well-known tricks we calc teachers inflict
on students learning how f+f'' is related to sine and cosine...
------------------------------------------------------------------------------
B3. In order to keep this argument elementary, let us make it an integer
question. Let L be the LCM of all the integers m = 1, .., n; it's
the product of the largest power of each prime less than n. Then
S = Sum(L/m) is a sum of integers; it sums to (L/q_n) * p_n, so
5 doesn;t divide q_n iff S is congruent to zero modulo the
largest power 5^k less than n. That is, our problem is to show:
if n = a0*5^k + a1*5^(k-1) + ... is the base-5 representation
of a number n, then the integer sum S = Sum (L/m) is congruent
to zero mod 5^k iff ...
We will show that having the sum be a multiple of 5^k is well-nigh
impossible; indeed, one can't even get it to be a multiple of 125,
so if k>=3, then we're sunk.
Well, why wouldn't S be a multiple of 125? After all, four out of five
terms being added have m prime to 5, hence L/m is a multiple of 5^k,
and hence (for k>2) a multiple of 125. We need only check the
remaining terms, in fact, we need only check those terms with m a
multiple of 5^(k-2); for in these cases L/m is not a multiple of 5^3.
Is S even a multiple of 5? Well, every term L/m being summed is a
multiple of 5 except when m = 5^k, 2*5^k, ..., a0*5^k. These contribute
a sum of L'+L'/2+L'/3+..., where L'=L/5^k is an integer prime to 5.
Depending on a0 this sum is either L', 3*(L'/2), 11*(L'/6), or 25*(L'/12).
Only the last is a multiple of 5, that is, we must have a0=4.
Is S a multiple of 25? Again the answer depends only on the few terms
5^(k-1), .., 5^(k-1)*(5*a0+a1). As a0=4, this is the sum of 20 to 24 terms.
We've summed the ones actually divisible by 5^k (and got 25(L'/12) ).
The others can be summed easily if a1=4: we are adding 5L'/i where i
ranges over the integers less than and prime to 25, that is, for i
in Z/25^*. Well, in Z/25, this is 5L' times the sum of the reciprocals
of all elements, which is the sum of all elements, which is preserved under
negation, and thus is zero. So S is indeed a multiple of 25 if a1=4.
Counting backwards we compute that the same is _not_ true if a1=3, 2, or 1,
but holds if a1=0.
Well, now, is S a multiple of 125? Once again, we sum only over the
m which are multiples of 5^(k-2). We have seen that the multiple of
5^k sum to 25(L'/12), and the other multiples of 5^(k-1) sum to
(5L')*(a multiple of 25). Now we need only sum over the _other_ multiples of
5^(k-2). Each gives a summand which is a multiple of 25L'; we need only
determine if that multiplier is a multiple of 5. It's easily
checked to be so for the sum of any 5 consecutive 5-regular reciprocals.
The final value of the sum thus depends only the value of a2: the last
a2 summands increase the total by an amount congruent to 25, 100, 100, 25, or 0
mod 125, respectively.
But now we have all the terms grouped into multiples of 125 except a few:
the multiples of 5^k gave a sum of the form 25(L'/12) (which is congruent
to 75 mod 125), and the final (ungrouped) multiples of 5^(k-2) add
either 0, 25, or 100 mod 125. In no case is the sum = 0 mod 125.
Thus S cannot be congruent to 0 mod 125. If k>=3, that means S
is not a multiple of 5^k, and thus 5 | q_n . So all the values of
n in problem B3 must be n = a0*5^k + ... with k <=2, so that n < 125.
For k>0 we have the constraint a0=4, and for k>=1 we have the
additional constrain a1=(0 or 4).
Thus our n must be
k=0: a0
k=1: 4*5 + a1
k=2: 4*25 + 4*5 + a2, or
4*25 + 0*5 + a2
that is, n={1, 2, 3, 4; 20, 21, 22, 23, 24; 100, 101, 102, 103, 104; 120, 121, 122, 123, 124}
(The only idea here is to note that the sum of the "top 4" "sinks down"
2 "levels", as does the sum of the "next 20"; but the former sinks down
to 1/12 mod 5, which can't be balanced by anything in the "next level".
On the other hand, actually getting that to paper without "quotes" proved
to be a real challenge!)
------------------------------------------------------------------------------
B4. Note that by construction a(m,n)=0 if n<0 or n>2m, so the sum
S_k in question is really a sum over all integers i. This makes the
bookkeeping a little simpler.
I claim S_(k+1) = S_k-S_(k-1)+S_(k-2). Indeed, by definition we have
a(m+1,n)=a(m,n)+a(m,n-1)+a(m,n-2)
so a((k+1)-i,i) = a(k-i,i) + a((k-1)-(i-1),i-1) + a((k-2)-(i-2),i-2)
Taking an alternating sum over all i now proves my assertion.
Since a brief calculuation give S_k for k=0, 1, 2 to be
1, 1, 0 we then compute succeeding values to be 0, 1, 1, 0, ... In
particular, we have returned to the original sequence of 3 values, so
of course the remaining values will repeat (in blocks of 4) and so
especially we see S_K is either 0 or 1.
------------------------------------------------------------------------------
B5. So we have a sequence of integers a_1 = 2 and a_(i+1) = 2^(a_i).
We must show a_n = a_(n-1) mod n, but in fact more is then true:
a_i = a_(i-1) for all i>= n.
This we prove by induction (it's clearly true when n=1,2). Suppose it's
known to be true for all n < N.
If N is odd, 2 is an invertible element of Z/NZ, and so by Euler's
theorem, 2^phi(N) = 1 mod N. More generally, then, 2^r = 2^s whenever
r = s mod phi(N). Since phi(N) < N, we have by induction that
a_i = a_(i-1) mod phi(N) for all i >= phi(N), and in particular for all
i >= N-1. So Euler's theorem gives 2^(a_i) = 2^(a_(i-1)) mod N, that is,
a_(i+1) = a_i mod N whenever i+1 >= N. That completes the induction
in this case.
If N is a power of 2, say N=2^k, then all a_i = 0 mod N as long as
a_(i-1) > k. In particular, a_i = a_(i-1) mod N for i >= N, which
is the induction statement.
Finally, if N = N1*N2 with N1 a power of 2 and N2 odd, then
a_i = a_(i-1) modulo both N1 and N2 as long as i is at least
as big as both. By the Chinese Remainder Theorem, a_i = a_(i-1) mod N
for those i.
This completes the induction; taking in particular i = N gives the
desiredd conclusion.
------------------------------------------------------------------------------
B6. Dissection in what category? Is a "part" just a subset or a triangle
or ... ? I assume this problem allows decompositions into arbitrary subsets.
I will describe a decomposition first, then show it is optimal.
ASCII is hardly the right medium here, so let me advise the reader to draw a
picture something like this: place a roughly regular pentagon in the
middle of the triangle, with two edges along the two longest edges of the
triangle, one edge marking off an isoceles triangle at the top of the figure,
and the other two edges meeting a little above the bottom of the triangle.
Mark an edge from there to the middle of the short leg so as to create a
quadrilateral in each of the two lower corners. That will be an optimal
dissection with suitable length sides.
Here is the construction in detail. Label the vertices of the original
triangle A, O, and B, with OA the vertical edge and OB the horizontal one.
Mark off segments of length r on each end of the hypotenuse and on the
top end of the vertical side. (I will compute r in a moment; it's about
1.90. For this construction to make sense, we will need 3/2 < r < 2.) Mark
also the midpoint of the bottom edge and a point on that edge of distance r
from B. Finally mark a point on the vertical edge a distance r from this
last point. We now have points on the perimeter of the triangle which I
label, in clockwise order, O, C, D, A, E, F, B, G, H. Also construct a point
X in the interior to be directly above G and of distance r from O. (It's also
of distance r from B, right?) Then pentagon will be CDEFX, the quadrilaterals
OCXH and BFXH and the isoceles triangle ADE.
What is the diameter of this dissection? The diameter of ADE is r (since
angle A is less than pi/3). Likewise BFXH has 3 interpoint distances
equal to r; FH is less because the angle at B is less than pi/3, and
likewise FX must be even less; finally, a little Pythagorean work on
HGBX shows HX is less than r assuming r < 3.
We must work harder to get the diameters of the other two pieces.
HC and OX are of length r; OH is 3-r < r, and we have seen HX < r.
OC must be less than HC. A prodigious effort to track right triangles
suggests CX^2 = (r^2+6r-9) - (2r-3)sqrt(6r+9); the condition that CX be
more than r is that r < 3/2, which we have agreed not to do.
Thus the diameter of this quadrilaterial is only r.
We turn finally to the pentagon. All its outer edges have lengths less
than r by previous results. I will compute the conditions necessary to
guarantee that the other five inter-point distances be <=r; the condition
that EX be <=r will force an lower bound on r which we then
take as our definition of r.
I must use coordinates: in order of ease we have
O(0,0) A(0,4) B(3,0) G(3/2,0) D(0,3-r) H(3-r,0) C(0,sqrt(6r-9))
AB is 4x+3y=12, so we find E((3/5)r, 4-(4/5)r), F(3-(3/5)r, (4/5)r)
Finally, X( 3/2, sqrt(r^2-9/4) ).
I compute the five distance, set equal to r, solve for r. Clearly as
r decreases from 2 to 3/2, say, these distances will decrease, so the
diamter is less than or equal to r as long as we keep r larger
than the largest of these roots in the interval (3/2, 2). For example,
the equation for DX has a root around 1.65, meaning that DX < r as
long as r > 1.65. For CE, the root is about 1,74; for EX it's 1.75;
for CF it's 5/8; and for DF it's
r0 = (36-3sqrt(14))/13,
which is about 1.90, the largest of the five. This then is the constraint:
keep r around 2, and the pentagon will have small diameter. Shrink it to
1.90, and the diameter increases to something larger than r.
So we have our construction and have proved that its diameter is really r0.
Now suppose there is a construction with a smaller diameter. In particular,
O, A, B, and (say) (3/2, 4/2) must be in different parts. In addition,
the parts containing A and B must lie in semicircles of radius r (the
diameter of the dissection) passing near D and E (respectively F, X, and H).
But if r < r0, this will leave points D and F outside these three regions,
hence in the same remaining region, hence of distance less than r, a
contradiction if r < r0.
As you can see, this last paragraph is simple. It's fairly clear at the
outset how to proceed. But I see no easy proof that with this r, the
remaining pieces do indeed have a diameterat most r0. I used Maple to
verify my calculations, which is of course not permitted on the exam.
dave
==============================================================================
From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Putnam exam 1997 -- some answers available.
Date: 7 Dec 1997 09:44:41 GMT
Well, it's that time again. The Putnam exam was administered today at
colleges and universities in North America. Usually we get a flood of
posts right away, but I don't see any yet. I'd like to see answers to
a few of the ones I missed.
Rather than post solutions this year, I'll just leave some at
http://www.math.niu.edu/~rusin/problems-math/putnam.97
Maybe it's just brain atrophy but I had a hard time with several of the
problems this year. There were also some that I thought would be
straightforward, but took more work than I expected to get it at all
close to complete. I wasted kind of a long time with problem A3 and
didn't get what I thought I should get; consequently I haven't yet
even had a chance to really think about a couple of others (A2 and A6).
A1 was the standard get-your-feet-wet problem; a good one, I thought.
I though A4 and B4 were really closer to homework problems than
Putnam problems, (but I guess that explains why my students think my
homework sets are too hard.) B2 was really a generalization of the
formula sin^2+cos^2=1, so calculus teachers have a better chance with
that one. I had a hard time expressing answers to B1 and B3, although
the ideas are simple enough. Problem A5 was also clear from the start
although I didn;t expect the answer I got. I also liked B5, but
don't tell my abstract algebra students, who have a test on Euler's
theorem next Wednesday, and I may have just found a test question...
Problem B6 seemed really laborious. I must have done something wrong.
Here's the problem. Imagine that my ascii-art consisted of straight
line segments:
"The dissection of the 3-4-5 triangle shown below has diameter 5/2.
*
|\
| \
|____\ 5
| /|\
| / | \
|/ | \
*____|____*
3
Find the least diameter of a dissection of this triangle into four parts.
(The diameter of a dissection is the least upper bound of the distances between
pairs of points belonging to the same part.)"
That's it. (When did "dissection" and "part" become standard nomenclature and
why wasn't I informed? Are we to work with line segments? curves? arbitary
subsets of the triangle?)
Anyway, I think I see what to do, as I can make a construction with the
lowest possible diameter, but _proving_ that I've got the LUB of the
distances is quite a chore; there are so many pairs of vertices to consider.
Did anyone see an easier way out?
dave
==============================================================================
From: bhunt@noJUNKipst.umd.edu (Brian R. Hunt -- delete noJUNK to reply)
Newsgroups: sci.math
Subject: Re: Putnam exam 1997 -- some answers available.
Date: 7 Dec 97 16:38:53 GMT
rusin@vesuvius.math.niu.edu (Dave Rusin) writes:
>Well, it's that time again. The Putnam exam was administered today at
>colleges and universities in North America. Usually we get a flood of
>posts right away, but I don't see any yet. I'd like to see answers to
>a few of the ones I missed.
>Rather than post solutions this year, I'll just leave some at
> http://www.math.niu.edu/~rusin/problems-math/putnam.97
Looks good to me, except I disagree w/ B6 (see below). Your solution
to B4 is much nicer than the ugly mess I had in mind. Some comments
on the other problems:
A2: The basic idea is this. Once you have n players with multiple
pennies in front of them, an odd value of n tends to produce a stable
cycle (BAD), while an even n tends to redistribute the wealth to n/2
"haves" and n/2 "have-nots" (GOOD). The have-nots all drop out in the
same round. So then the question is whether n/2 is odd or even. By
looking at what goes on in the first couple rounds, you can deduce
that n = 2^k + 1 or 2^k + 2 is necessary and sufficient.
But all you really need to do is take one of these sequences, say n =
2^k + 2, and show what happens. After the first 2 players drop out,
you have a distribution 311...1 with 2^k players remaining. After 1
round you have 422...2 with 2^(k-1) players. After another couple
rounds you have 644...4 with 2^(k-2) players. Etc.
A3: I only gave this one a cursory look at the time; I'm not sure I
remember what the second term was, but I suspect now that I was errant
in viewing it as an exponential as well. In any case, once you
reduce the first term to x*e^(-x^2/2), you can multiply everything
out, integrate term-by-term, and perhaps something nice will happen.
A6: Work out the first few values of n and you start to see Pascal's
triangle. If I recall the notation correctly, c = n-1 and x_k = (n-1
choose k-1). This makes the recursion work, and it shouldn't be too
hard to show that any larger value of c makes x_(n+1) positive.
B6: I got 25/13, as did one of the students I was proctoring. Then
again I thought the answer was 15/8 for a while, so who knows -- seems
like a problem that lends itself to convincing but wrong answers.
Here's a rough picture of what I have in mind.
A
|\
| \
| \E
D|__-\
| \F
|____/\
| / \
|__|____\
C G B
Coordinates: A = (0,4), B = (3,0), C = (0,0), D = (0,27/13),
E = (15/13,32/13), F = (24/13,20/13), G = (14/13,0).
DE and FG are circular arcs of radius 25/13. The unlabeled horizontal
line runs from (0,15/13) to (19/13,15/13). Note that D is exactly
25/13 from F. I think that all other relevant distances are smaller.
Suppose a diameter r < 25/13 were possible. The sets containing A and
B could respectively extend no further than circular arcs DE and FG
with radius r. Assume all sets are closed, so that C, D, E, F, G must
each belong to one of the remaining 2 sets. Check that lengths CE and
GE are > r, so that C and G must be in the same set. Check that DG
and CF are > r, so that D and F must both be in the opposite set as C
and G. Thus DF must be at most r, which requires r >= 25/13.
--
Brian R. Hunt
bhunt@ipst.umd.edu
==============================================================================
From: "Travis Fisher"
Newsgroups: sci.math
Subject: Re: Putnam exam 1997 -- some answers available.
Date: Sun, 7 Dec 1997 11:14:15 -0600
Dave Rusin wrote in message <66dr69$rtt$1@gannett.math.niu.edu>...
>
>Well, it's that time again. The Putnam exam was administered today at
>colleges and universities in North America. Usually we get a flood of
>posts right away, but I don't see any yet. I'd like to see answers to
>a few of the ones I missed.
Well, I can fill you in on problem A2. Two possible sets are {2^n+1} and
{2^n+2} for n in N. The second one is a bit easier to prove, so that's what
I'll do here.
I will call a player live who still has coins.
I will call a round the series of passes that starts with the lowest
numbered live player passing and ends with the highest numbered live player
passing.
Note that in the first round, the first player is eliminated, all
even-numbered players are eliminated, and all odd numbered players except
for player 3 end up with 2 coins. Player 3 has 2 coins plus the additional
one or two passed by the last player; with n=2^n+2 the last player is even
and passes two coins. So after the first round, 2^(n-1) players remain,
where the first has 4 coins and is about to pass 1, while all subsequent
players have 2 coins.
This is begging for proof by induction, where the inductive assumption is
that a round begins with 2^k live players (k>=1), where all but the first
player have the same number of coins. Call the players p1,p2,..,pk in that
playing order. The claim is that given such a setup, the next round where
players are eliminated, players p2,p4,..,pk will all be elimanated, leaving
2^(k-1) players where all but the first have the same number of coins. We
can see this by noting that each round, the even numbered players receive 1
coin and pass 2, and so have a net loss of one coin for the round, while the
odd players receive 2 coins and pass 1, and so have a net gain of one coin
for the round. Since all the even players start with the same number of
coins, they all run out during the same round. Note this does not affect
their coin passing that round. Similarly, all odd players except the first
have the same net gain through this process, and so end that round with the
same number of coins.
So then by induction, there will be a round where 2^0 = 1 players remain.
Clearly this last remaining player must have all the coins.
--Travis Fisher
tfisher@math.unl.edu
==============================================================================
From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Putnam A3 (was: Re: Putnam exam 1997 -- some answers available.)
Date: 7 Dec 1997 19:09:21 GMT
Problem A3 asks us to evaluate a definite integral
\int_0^\infty (...)*(...)
where the two factors are written as power series. I was heading down a
blind alley yesterday, which not only prevented me from solving this
problem but kept me from working on the others!
The first power series is easily recognized to be that of x*exp(-x^2/2).
The second is g(x) =
1 + x^2/2^2 + x^4/(2^2 4^2) + x^6/(2^2 4^2 6^2) + ...
This is actually a Bessel function ( BesselI(0,x) ) but I assume we're
not supposed to know that. I thought we were supposed to notice that
g satisfies a differential equation
x g''(x) + g'(x) = x g(x)
so that an integral int( x f(x) g(x) ) can be rewritten as
int(f(x) (x g')'(x)), thus allowing the use of integration by parts.
Now I think this is wrong; at least according to maple there is no
closed form antiderivative of int( x exp(-x^2/2) BesselI(0,x) ).
Here's what I think we're supposed to do: write the integral as
int_0^\infty x exp(-x^2/2) Sum( x^(2n)/(n!)^2/2^(2n) )
and expand into a sum
Sum( (1/n!)^2 (1/2^(2n)) int_0^\infty x^(2n+1) exp(-x^2/2)
That last integral is easy to get by induction. It's
= 2^n int_0^\infty u^n exp(-u) du
= 2^n [ -u^n exp^(-u) + n int u^(n-1) exp(-u) du ]
using first substitution then integration by parts. Thus by induction the
portion in the brackets is just n!, so the integral is 2^n n!, and the
sum is
Sum( (1/n!) (1/2^n) ) = exp(1/2),
that is the answer to the original problem is sqrt(e).
dave
==============================================================================
From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Putnam exam 1997 -- some answers available.
Date: 7 Dec 1997 19:23:24 GMT
In article ,
Brian R. Hunt -- delete noJUNK to reply wrote:
>Looks good to me, except I disagree w/ B6 (see below).
Hunt is quite right; I had a brain-o (that's like a typo but it's not
the typing fingers which are to blame...). For some reason I set
the coordinates of his point D to (0,3-r) rather than (0,4-r),
giving a slightly wrong answer. But the analysis was the same.
I stand by my original complaint: in this problem, establishing a
lower bound of 25/13 on the diameter is easy because five points ABCDF
can be found all of whose distances are at least 25/13, requiring each
to be in a different "part" if parts of diameter < 25/13 are used.
But to show a diameter of 25/13 is in fact achievable, one has to
demonstrate that the diameters of the parts in a particular configuration
really are 25/13 or less.
>B6: I got 25/13, as did one of the students I was proctoring. Then
>again I thought the answer was 15/8 for a while, so who knows -- seems
>like a problem that lends itself to convincing but wrong answers.
>Here's a rough picture of what I have in mind.
>
> A
> |\
> | \
> | \E
>D|__-\
> | \F
> |____/\
> | / \
> |__|____\
>C G B
>
>Coordinates: A = (0,4), B = (3,0), C = (0,0), D = (0,27/13),
>E = (15/13,32/13), F = (24/13,20/13), G = (14/13,0).
>
>DE and FG are circular arcs of radius 25/13. The unlabeled horizontal
>line runs from (0,15/13) to (19/13,15/13). Note that D is exactly
>25/13 from F. I think that all other relevant distances are smaller.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This is the part which seems like a real pain in the extremity.
dave
==============================================================================
Date: Mon, 08 Dec 1997 10:57:42 +0000
From: Robin Chapman
To: rusin@math.niu.edu
Subject: Putnam solutions
A4: E = phi(e) needn't be central. We can take phi to be constant,
and this constant need not be in the centre. Note that E commuting
with phi(x) for all x doean't imply E commutes with y for all y in G.
A5: This is easier if you recall the result (due to Kummer?)
that a prime p divides a binmomial coefficient (a+b choose a)
to the order m, if m is the number of carries when a and b are
added in base p. Thus as 10 is 1010 in base 2, the only
odd binomial coefficients (10 a) occur when a = 0, 2, 8 and 10.
Now refining a partition mulitplies the corresponding
multinomial coefficient by a factor, so the only odd multinomial
coefficients corrrespond to the partitions which are not
refinements of (10-a) + a for a <> 2, 8. The only non-trivial
one is 8+ 2 itself.
--
Robin Chapman "256 256 256.
Department of Mathematics O hel, ol rite; 256; whot's
University of Exeter, EX4 4QE, UK 12 tyms 256? Bugird if I no.
rjc@maths.exeter.ac.uk 2 dificult 2 work out."
http://www.maths.ex.ac.uk/~rjc/rjc.html Iain M. Banks - Feersum Endjinn
==============================================================================
From: Keith Wolcott
Newsgroups: sci.math
Subject: Different solution to Putnam A1
Date: Tue, 09 Dec 1997 16:44:18 -0600
Here is a different solution than I have seen posted for problem A1 of
the Putnam competition. This solution is due to Hillel Gauchman.
%Format: LaTeX2e
\documentclass[12pt]{article}
\pagestyle{headings}
\setlength{\textwidth}{6.0in}
\setlength{\textheight}{9.0in}
\setlength{\oddsidemargin}{0.25in} % 1.25" margin on the side
\setlength{\topmargin}{-1in} % the page head 0.5" from the top
\begin{document}
\thispagestyle{empty}
\centerline{\bf PROBLEM A1, PUTNAM 1997}
\medbreak
\centerline {\bf PROBLEM}
\medbreak
\noindent A rectangle, $HOMF$, has sides $HO=11$ and $OM=5$. A triangle
$ABC$ has $H$ as
the intersection of the altitudes, $O$ the center of the circumscribed
circle,
$M$ the midpoint of $BC$, and $F$ the foot of the altitude from $A$.
What is the length of $BC$?
\vspace{4cm}
\centerline {\bf SOLUTION}
\bigbreak
\centerline {\bf by Hillel Gauchman (Eastern Illinois University,
cfhvg@eiu.edu)}
\bigbreak
\noindent Let $R$ be the circumradius of $\triangle ABC$.
Denote by $K$ the point of intersection of median $AM$ and segment $OH$.
It is known that the three points: the circumcenter, the centroid, and
the orthocenter belong to the same line (the so-called ``Euler's
line'').
Therefore point $K$ must be the centroid of $\triangle ABC$. This allows
us
to make simple calculations:
$AK/KM=2$, so $AH=2\cdot HF=10$, and from right $\triangle OHA$,
~~$R=OA=\sqrt{OH^2+AH^2}=\sqrt{11^2+10^2}$. Then from right $\triangle
OBM$,
in which $OB=R$, we find $BM=\sqrt{BO^2-OM^2}=\sqrt{11^2+10^2-5^2}=14$.
Hence $BC=2\cdot BM=28$.
\vspace{3cm}
\noindent{\bf Notes.~~ (1).} If $HO=a$ and $OM=b$, then
$BC=2\sqrt{a^2+3b^2}$.
If $OHFM$ is a square with side $a$, then $BC=4a$.
\bigbreak
\noindent {\bf (2).} Triangle $ABC$ is determined uniquely since
$AC=\sqrt{15^2+3^2}=\sqrt{234}$
(from right $\triangle AFC$), and $AB=\sqrt{25^2+15^2}=5\sqrt{34}$
(from right $\triangle AFB$).
\medbreak
\noindent In general case, $AB=\sqrt{2a^2+12b^2+2a\sqrt{a^2+3b^2}}$,
and $AB=\sqrt{2a^2+12b^2-2a\sqrt{a^2+3b^2}}$. We conclude that
$\triangle ABC$ exists (the inequality $2a^2+12b^2>2a\sqrt{a^2+3b^2}$
holds for all $a$'s and $b'$s) and is determined uniquely always.
\end{document}
==============================================================================
From: gross@math.utah.edu (Fletcher Gross)
Newsgroups: sci.math
Subject: Re: 00A07 1997 Putnam problems and unofficial solutions (TeX)
Date: Tue, 09 Dec 1997 08:30:19 -0600
I have a shorter proof of A5. Namely if S is the set of all ordered
10-tuples that satisfy the condition and if G is the group of all
permutations of 10 objects, then G operates on S and under this action, S
is partitioned into orbits. The problem then becomes that of determining
those orbits of odd length. The length of an orbit is the index in G of
the subgroup fixing some member of the orbit so an orbit has odd length if
and only if it is fixed by a Sylow 2-subgroup of G. Now a Sylow 2-subgroup
of G has, in its action on {1, ..., 10}, exactly 2 orbits, one of length 8
and one of length 2. Thus if a member of S is fixed by a Sylow 2-subgroup
of G, 8 of the integers must be equal and the other 2 are also equal,
i.e., we must have
8/a + 2/b = 1.
This is equivalent to (a - 8)(b - 2) = 16. This leads at once to five
possibilities a - 8 = 1, 2, 4, 8, and 16. When a and b are not equal,
there are 45 elements of S while if a = b, there is only one such element.
Thus there are exactly 4(45) + 1 elements of S which are in orbits of odd
length. Hence the number of elements in S is odd.
--
Fletcher Gross
Department of Mathematics
University of Utah
Salt Lake City, Utah 84112
email: gross@math.utah.edu
==============================================================================
Date: Mon, 08 Dec 1997 14:56:15 +0000
From: Robin Chapman
To: rusin@math.niu.edu
Subject: Putnam B4
The generating function sum a_{m,n} x^n y^m is
1/(1-y(1+x+x^2)). The sum we're after is the y^k coefficient
when we replace x by -y in this, i.e., the y^k coefficient
of 1/(1-y+y^2-y^3) = (1+y)/(1-y^4). This is 1 if k is 0 or
1 mod 4 and 0 otherwise.
--
Robin Chapman "256 256 256.
Department of Mathematics O hel, ol rite; 256; whot's
University of Exeter, EX4 4QE, UK 12 tyms 256? Bugird if I no.
rjc@maths.exeter.ac.uk 2 dificult 2 work out."
http://www.maths.ex.ac.uk/~rjc/rjc.html Iain M. Banks - Feersum Endjinn
==============================================================================
Date: Mon, 8 Dec 1997 22:16:44 -0800 (PST)
From: Ryan McCorvie
To: rusin@math.niu.edu
Subject: Re: Putnam exam 1997 -- some answers available. (fwd)
Problem A6 works like this:
Let X(z) be the generating function for the series.
X(z) = x_k+1 * z^k
It is routine to verify that the recurrance is equivalent to the
following:
X'(z) = cX - nzX + z(zX)'
Or: X'/X = (c + (1-n)z) / (1 - z^2)
Solving for X:
X = (1+z)^-alpha * (1-z)^beta
where alpha and beta are the values one obtains by partial fraction
decomposition.
2*alpha = c + 1-n
2*beta = c + n-1.
Recognize that X must be a polynomial if x_n+1 is zero because then
xn+2 = (cx_n+1)/(n) = 0
and by the recurrance, all successive terms are zero.
So -alpha, beta are nonnegative integers. c is maximized when c=n-1. SO
(n-1 )
xk = ( ) (<-- binomial coefficient)
( k-1)
Ryan McCOrvie
==============================================================================
From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Putnam question A3, finally the "right" solution
Date: 19 Dec 1997 15:06:23 GMT
I had written previously that I was sure problem A3 on the Putnam exam was
to be solved by working with the differential equation which the (Bessel)
function satisfies, but that I couldn't make that approach work. The
problem's proposer wrote to remind me of the trick needed to make it
work; now I can give this solution.
Recall that problem A3 asks us to evaluate a definite integral of the form
C = \int x*e(x)*g(x) dx
(this and all other integrals below taken over [0, \infty]).
The two factors were written as power series. The first power
series is easily recognized to be that of e(x) = exp(-x^2/2). The second is
g(x) = 1 + x^2/2^2 + x^4/(2^2 4^2) + x^6/(2^2 4^2 6^2) + ...
This g satisfies a differential equation
x g''(x) + g'(x) = x g(x).
It turns out that this, and the DE e'(x) = -e(x), are really the only
ingredients we need for the answer.
The trick is to view the desired computation C as a particular value of
a function with an extra parameter. Let
H(y) = \int x*e(x)*g( x*y ) dx,
Thus we seek H(1). For comparison, we have
H(0) = \int x*e(x) dx = \int -e'(x) = -e(x) {\big |}_0^\infty = 1.
We deduce H by looking to see what differential equation _it_ satisfies.
We simplify notation a bit by writing H(y) = \int x*F(x,y) dx where
F(x,y) = e(x)*g( x*y ).
Since e and g satisfy second-order DEs, there will be relations among the
second-order derivatives of F, too. Indeed, we compute
F_y (x,y) = x*e(x)* g'( x*y ) and thus
F_{yx} (x,y) = e(x)g'(xy) - x^2 e(x)g'(xy) + xy e(x)g''(xy)
= -x F_y (x,y) + xy F(x,y)
which may be interpreted as an integral equation instead:
-\int xF_y (x,y) dx + y*\int x F(x,y) = F_y(x,y) {\big |}_0^\infty = 0.
But the left-hand side is simply -H'(y) + y*H(y) ! (Well, OK, we do have
to justify differentiating under the integral sign.)
Very well, then, H(y) is the solution to H'(y) = y H(y) with H(0)=1.
It is now elementary to deduce that H(y) = exp( y^2/2 ). In particular,
C = H(1) = exp( 1/2 ).
dave
==============================================================================
From: Fred Galvin
Newsgroups: sci.math
Subject: Re: 1998 Putnam exam -- some solutions [SPOILER]
Date: Tue, 8 Dec 1998 03:57:18 -0600
On 6 Dec 1998, Dave Rusin wrote:
> B2. This is the closest I have seen to a mathematical physics problem on
> the Putnam exam!
Problem B2 on the 1997 Putnam contest was also a mathematical physics
problem: "Let f be a twice-differentiable real-valued function satisfying
f(x)+f''(x) = -xg(x)f'(x), where g(x) >= 0 for all real x. Prove that
|f(x)| is bounded."
Change the notation f(x) to u(t). For t > 0 it's a damped vibration
problem, with time-dependent damping coefficient tg(t). For t < 0 the
damping becomes negative, i.e., damped vibration in reverse time. By
physical reasoning, the energy is maximum at t = 0. The mathematical proof
of B2 consists of verifying this by taking the derivative of the energy.