1995 Putnam exam. Here you will find
	  I. The questions
	 II. Answers I posted
	III. Completions of the problems, and other comments, posted or
		emailed to me by others. 

You will note that A6 and B6 are the hardest, generating a lot of
interesting commentary, extensions, and differing solutions; these
discussions occupy over half this file. There was also a fair amount
of commentary on A4 and B5.

I. First the questions

From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Putnam exam: list of questions
Date: 3 Dec 1995 08:01:37 GMT

56th Putnam Exam, 12/2/95 [You have 6 hours, good luck.]

A1. Let  S be a set of real numbers which is closed under multiplication
(that is, if  a  and  b  are in  S  then so is  ab). Let  T  and  U  be 
disjoint subsets of  S  whose union is  S. Given that the product of any 
_three_ (not necessarily distinct) elements of  T  is in  T  and that the
product of any three elements of  U  is in  U,  show that at least one of
the two subsets  T, U  is closed under multiplication.

A2. For what pairs  (a,b)  of positive real numbers does the improper
integral
	\integral_b^\infty ( ... ) dx
converge?

[sorry for loss of clarity; integrand is   
	sqrt( sqrt(x+a) - sqrt(x) ) - sqrt( sqrt(x) - sqrt(x-b) )
--djr ]

A3. The number  d_1 d_2 ... d_9  has nine (not necessarily distinct) decimal 
digits. The number  e_1 e_2 ... e_9  is such that each of the nine
9-digit numbers formed by replacing just one of the digits  d_i  in 
d_1 d_2 ... d_9  by the corresponding digit  e_i  (1 <= i <= 9)  is
divisible by  7. The number  f_1 f_2 ... f_9  is related to  e_1 e_2...e_9
in the same way: that is, each of the nine numbers formed by replacing
one of the  e_i  by the corresponding  f_i  is divisible by  7. Show that, 
for each  i,  d_i-f_i  is divisible by  7.
(For example, if  d_1 d_2 ... d_9 = 199501996, then  e_6  may be  2  or  9
since  199502996  and  199509996  are multiplies of  7.)

A4.  Suppose we have a necklace of n beads.  Each bead is labeled with
an integer and the sum of all these labels is n-1.  Prove that we can
cut the necklace to form a string whose consecutive labels  x_1, x_2, ...
x_n  satisfy

	Sum_{i=1}^k  x_i  <= k-1  for  k=1, 2, ..., n

A5. Let  x_1, x_2, ..., x_n  be differentiable (real-valued) functions of a 
single variable  t  which satisfy

	dx_1/dt = a_11 x_1 + a_12 x_2 + ... + a_1n x_n
	dx_2/dt = a_21 x_1 + a_22 x_2 + ... + a_2n x_n
	...		...		...
	dx_n/dt = a_n1 x_1 + a_n2 x_2 + ... + a_nn x_n

for some constants  a_ij >= 0.  Suppose that for all  i,  x_i(t) -> 0  as
t --> oo.  Are the functions  x_1, x_2, ..., x_n  necessarily linearly 
dependent?


A6. Suppose that each of  n  people writes down the numbers  1, 2, 3
in random order in one column of a  3 x n  matrix, with all orders
equally likely and with the orders for different columns independent of
each other. Let the row sums  a, b, c  of the resulting matrix be 
rearranged (if necessary) so that  a <= b <=c. Show that for some
n >= 1995, it is at least four times as likely that both  b=a+1
and  c=a+2  as that  a=b=c.

==============================================================================

B1. For a partition  pi  of {1, 2, 3, 4, 5, 6, 7, 8, 9}, let  pi(x)  be
the number of elements in the part containing  x.  Prove that for any
two partitions  pi  and  pi', there are two distinct numbers  x  and  y
in  {1, 2, 3, 4, 5, 6, 7, 8, 9}  such that  pi(x)=pi(y)  and
pi'(x)=pi'(y).
(A _partition_ of a set  S  is a collection of disjoint subsets (parts)
whose union is  S.)

B2.  An ellipse, whose semi-axes have lengths  a  and  b, rolls without 
slipping on the curve  y = c sin(x/a).  How are  a, b, c  related, given that 
the ellipse completes one revolution when it traverses one period of the curve?

B3. To each positive integer with  n^2  decimal digits we associate the
determinant of the matrix obtained by writing the digits in order across
the rows. For example, for  n=2, to the integer  8617  we associate  
det([[8,6],[1,7]]) = 50.  Find, as a function of  n,  the sum of all the 
determinants associated with  n^2-digit integers. (Leading digits are
assumed to be nonzero; for example, for  n=2,  there are 9000 determinants.)

B4. Evaluate
            ________________________________
           /                  1
    \   8 / 2207 -  ------------------------   .
     \   /                         1
      \ /            2207 - ----------------
       v                      2207 - ...

Express your answer in the form   (a + b sqrt(c))/d, where  a, b, c, d  
are integers.

B5. A game starts with four heaps of beans, containing  3, 4, 5 and 6 beans.
The two players move alternately. A move consists of taking  _either_
	a. one bean from a heap, provided at least two beans are left
		behind in that heap, or
	b. a complete heap of two or three beans.
The player who takes the last heap wins. To win the game, do you want to move 
first or second? Give a winning strategy.

B6.  For a positive real number  alpha, define
	S(alpha) = { [n alpha] : n = 1, 2, 3, ...}.
Prove that  {1, 2, 3, ...} cannot be expressed as the disoint union of three
sets  S(alpha), S(beta), and S(gamma).  (As usual, [x]  is the greatest
integer  <=  x . )

==============================================================================
II. Now the answers as I first posted them. There are some corrections and
comments in the next section; I'll flag them here.

From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Putnam spoilers -- first go-round
Date: 3 Dec 1995 06:25:17 GMT

Well, it's probably legal to post answers to the Putnam exam now. I didn't
quite finish problem  A-6, but I think I have reasonably complete (and
usually nice) answers to the other. I thought the exam was pretty fair this
year -- many of the questions seem like the kind of thing one might use
to challenge students within a particular course.

I await the usual corrections and slick improvements :-).
dave

[Added in a later post:
By the way, while I have the floor (screen?) let me acknowledge that some
of the  A-questions were the subject of conversation at lunch time, so
that the thoughts in the answers I wrote down may not be mine alone.
In particular, Yining Xia had some helpful comments on several problems.
dave
]

A1. Suppose not. Then there exist t1, t2 in  T  and  u1, u2  in  U  such
that  t1*t2  lies in  U   and  u1*u2   lies in T.  Thus we have by
assumption that  t1*t2*(u1*u2)  lies in  T, and yet also
u1*u2*(t1*t2) lies in U. The usual axioms of multiplication apply
in   R  so these products are equal, contradicting the assumption that
U and  T   are disjoint.

A2. This is the kind of problem undergraduates should learn to do
as soon as they begin to work with improper integrals: one learns to
estimate by finding the dominant terms.

If  a=b, the integral converges, otherwise not.

Indeed, the integrand is x^(1/4) times
sqrt(sqrt(1+a/x)-1) - sqrt(1-sqrt(1-b/x)). Using Taylor series, say,
one can show that for large  x, sqrt(1+a/x) = 1 + a/(2x) - a^2/(8x^2) * C,
where  C  approaches  1  as  x--> oo. Thus the first half of the integrand
is  sqrt(a/2x - a^2/(8x^2)*C) = sqrt(a/(2x))*sqrt(1-a/4x*C) =
sqrt(a/2x) -sqrt(a/2x)*(a/8x)*C'. Likewise, the second half of the integrand
is sqrt(b/2x) +sqrt(b/2x)*(b/8x)*C''.

So if  a=b, the leading terms drop out. What remains is a constant
multiple of  x^(-3/2), multiplied by a term which approaches  1  as x-->0.
In particular, we can find a constant  D  such that the entire integrand
is less than  D x^(-5/4)  for sufficiently large  x, making the
integral over [x1, x2] be less than  D(x1^(-1/4) - x2^(-1/4)); as
x2 --> oo, this converges.  (The integral over finite regions converges
by continuity of the integrand.)

On the other hand, if  a<>b, the integrand is now of the form
x^(-3/4)[sqrt(a/2)-sqrt(b/2)] plus a function as discussed in the previous
paragraph. While the integral of that function converges, the
integral of the first part is a non-zero constant multiple of
(x1^(1/4) - x2^(1/4) ), so that as  x2 --> oo, the integrals diverge.

A3. Let  d  be the number expressed by the digits  d1...d9, and likewise
e  and  f. Then we are given that for each  i, the number  
d + (e_i-d_i)*10^(9-i)  is a multiple of  7. Summing, we see
9d + (e-d) ==0  mod 7, i.e., d == -e. Since likewise each
e + (f_i-e_i)*10^(9-i)==0 and  e==-f, we add the congruences to see
(f_i-d_i)*10^(9-i) ==0. Since  10  is a unit mod 7, we divide and
conclude  f_i == d_i, as needed.

A4. Suppose this is not possible. Let us pick any starting point on
the necklace and either of the possible directions, and read off the
labels to get a sequence of integers  a_1, a_2,...  Note that
a_i=a_j  if  i=j mod n, and that by assumption the sum of any  n  consecutive
terms is less than  n.

If an appropriate cut in the necklace is not possible, then for any  i
there is a  j  such that  a_i+a_(i+1)+...+a_j  is at least equal to the
number of terms  (j-i+1); in other words, the average of this subset is
at least  1.

Very well, find the first such  j  which corresponds to i=1; call it  j_1.
Find the first such  j  corresponding to  i=j_1+1; call it j_2.
Proceed in this manner to find consecutive stretches within the
sequence whose average is at least  1.

Consider the collection of reductions of the  j_k  modulo  n -- there can
only be a finite number, so that at some point we will have  j_k = j_l
mod  n. Then it is true that the each of these sequences
	a_(j_k + 1), ..., a_(j_(k+1))
	a_(j_(k+1)+1),...,a_(j_(k+2))
	...
	a_(j_(l-1)+1),...,a_(j_l)
consists of terms with an average at least equal to  1. Consequently
the lot of them
	a_(j_k+1), ..., a_(j_l)
must also average at least  1.

On the other hand, since  j_k = j_l  mod  n, this sequence consists of
a number of repetitions of the whole sequence of labels taken around
the circle, hence their average is the same as the average of those
n  labels, which is less than one. This contradiction shows that at some
point the construction of the indices  j_k  must fail, i.e., that
from some starting point it is possible always to keep the averages
less than 1.

A5. Yes, the functions are necessarily linearly dependent.
The eigenvalue procedure used here should be familiar to those who
have taken a course in differential equations which covered linear
equations with constant coefficients.

We are given a matrix  A  of non-negative coefficients and functions
x=(x_1(t), ..., x_n(t))  with  Dx=Ax  and  x(t) --> 0; the question
asks if there is necessarily a linear combination of the  x_i  which
vanishes identically.

Rephrasing in a coordinate-free way, we have a function  x:R -> R^n
which tends to  0  in  R^n  and such that  Dx=Ax  for some linear map
A: R^n -> R^n; we ask if the image of  x  lies in some proper subspace
of  R^n. If  a  is a real eigenvalue of  A, we may choose a new basis
of  R^n  which begins with an eigenvector corresponding to this 
eigenvalue; then Dx_1=ax_1 means  x_1  is a multiple of  exp(a t).
Since  x(t) --> 0, either this multiple is zero (so that  x  does
lie in a subspace) or  a<0. Likewise if  a+bi is a complex eigenvalue,
then its complex conjugate  a-bi  is also so that in a suitable basis we
have  (x_1, x_2) = exp(a t)*(cos(bt), sin(bt)) up to a constant multiple.
So again, either the image of  x  lies in a subspace or the real part  a
of these eigenvalues is negative.

We conclude that the conditions  Dx=Ax, x(t)-->0, and  A  real  imply
that either the image of  x  lies in a subspace of  R^n  or else all
the eigenvalues have negative real part. In particular, this last
condition will mean the trace of  A  will be negative. This is impossible
if  A  has only non-negative entries.

A6. We have   n  vectors  (x_i, y_i, z_i)  consisting of permutations of
{1,2,3}. We are investigating the sum  (s, t, u) of these vectors. It
seems more helpful to let x'_i=x_i-2, y'_i=y_i-2, and z'_i=z_i-2 so that
x'_i+y'_i+z'_i=0, and thus  (x,t,u)=(2n, 2n, 2n)+(s', t', u'). These
new vectors can be thought of as random steps in the plane x+y+z=0,
each of length sqrt(2) but in directions 60 degrees apart (as may be
computed by noting that the cosine of the angle between any two is
a dot product (equal to  +-1 or +-2) divided by the lengths). So the
issue is to compare the probabilities that a random walk of this type
returns to the origin or to one of the six vectors neighboring the origin.
(Geometrically, this motion can be seen as a random walk on an
infinite Chinese-Checkers board.)

If we let  p_n(v)  be the probability the walker is at position  v
after  n  steps, then a standard treatement of conditional probability
shows  p_(n+1)(v)  is the average of the value of  p_n(w)  at the
six neighbors  w  of  v.

Clearly, over the long run, this averaging will make  p_n(v)  nearly
constant over short regions; in particular, p_n(0)  will roughly equal
the probability  p_n(v)  of landing at any one of the 6 neighbors of  0,
and is thus  1/6  of the probability of landing somewhere in that set
(for large  n). This will force  p_n(0) to be less than  1/4 of that
probability, of course.

Now, the function  p_n  is the  n-fold convolution of  p_1, which ought
to make it possible to evaluate  p_n(v)  precisely, but I'm sure there's
a way to estimate just a few values such as p_n(0)  without as much
work. Unfortunately I've just had to endure a few hours of a social function
and my brain is now blocked; someone else will have to provide details.


==============================================================================

B1. Let's try to see what partitions would look like which did _not_
have  pi(x)=pi(y)  and pi'(x)=pi'(y)  for any pair of  x  and y.

First note that there can not be any equivalence class under  pi  which
has four or more elements. If, say, {a, b, c, d} is contained in a
single equivalence class under  pi, then by assumption each of these
four lie in different equivalence classes under  pi'; indeed, they must
lie in classes of different cardinalities. This would force the sum of the
cardinalities of the equivalence classes under  pi'  to be at least
1+2+3+4=10, a contradiction.

Likewise,  pi  cannot have two or more equivalence classes of cardinality
three, nor of cardinality two; and it cannot have four or more classes of
cardinality  one.

So the sum of the sizes of the classes under  pi  is at most
3 x 1 + 1 x 2 + 1 x 3 = 8, which is insufficient.

An examination of the proof shows that  9  is the maximal cardinality of
the large set; indeed consider these partitions of {1, ..., 10}
	{{1, 2, 3, 4}, {5, 6, 7}, {8, 9}, {10}}
	{{1, 5, 8, 10}, {2, 6, 9}, {3, 7}, {4}}

B2. Let  b  be the larger of the two semi-axes.

The length of the arc is  integral sqrt( 1 + ((c/a) sin(x/a))^2 dx
for x in  [0, 2 pi  a]. Let  u= x/a; this is then the integral 
	integral sqrt( a^2 + (c sin u)^2 ) du, u in [0, 2 pi]

The length of the ellipse is twice the length of the curve
(x/a)^2 + (y/b)^2 = 1  above the x-axis. This is then
	2*integral sqrt(1 + ((b/a)^2 x/y)^2 ) dx,  x in  [-a, a] 
using implicit differentiation. Now, a variation of the trig parameterization
of an ellipse suggests the substitution  x = a sin(u), y = b cos(u) 
(with u  ranging over  [-pi/2, pi/2]) to give us
	2*integral sqrt(1 + ((b/a) sin(u)/cos(u) )^2 ) (a cos u) du
	=2*integral sqrt(a^2 cos^2 u + b^2 sin^2 u) du
	=2*integral sqrt( a^2 + (b^2-a^2) sin^2 u) du
Using the periodicity of the sine, this is the same as the integral 
	integral sqrt( a^2 + (b^2-a^2) sin^2 u) du,  u in [0, 2 pi]

If the ellipse rolls without slipping so that one revolution traverses
one period of the curve, then the two lengths must be equal. Clearly
c=+-sqrt(b^2-a^2)  will make that true, but it is clear geometrically
that the length of the sine curve increases with  |c|, so these can
be the only solutions.

B3. We need to find the sum 
	Sum det(A)
where  A  ranges over all  n x n  matrices with entries in {0, 1, ..., 9}
and with  A_{1, 1} <>0.

The key observation is that most of these determinants cancel. Excluding
the matrices with the bottom two rows equal, we can pair each matrix with
a unique other matrix by permuting the bottom two rows. These matrices
have determinants which are negatives of each other.

All the remaining matrices have determinant zero since they have two 
equal rows!

Grand total: zero.

The argument fails when  n=1 or 2. In the former case, we have simply
Sum (n, 1 <= n <=9 ) = 45. In the latter, we would have a pairwise
cancellation as before but for the lack of matrices with a  0  in
the upper left; thus the sum is the negative of  Sum det [[0,a],[b,c]]
which is clearly  Sum( -ab : a, b, c in {0, 1, ..., 9}). This in turn
equals -(Sum(a))*(Sum(b))*(Sum(1))  (the sums taken over  a, b, and c
respectively), so that the number we seek when  n=2  is  45^2*10=20250.

B4. The ellipsis is unclear, I suppose, but it presumably means that
if  x  is the continued fraction  2207-1/(...), then  x=2207-1/x.
Therefore, x^2-2207x+1=0. The number  y  we seek has  y^8=x, so that
y  is the solution to the equation  y^16-2207y^8+1 = 0.

The hint suggests that  y  satisfies a quadratic equation with integral
coefficients, so we try to factor the above polynomial. Starting with
a factor of the form  (y^8 + a y^4 +- 1)  we see  y^8 +-47 y^4 +1  are
indeed factors, one of which has no real roots. In turn we likewise try
factors of the form  (y^4 + a y^2 +- 1)  and deduce  y^4 +- 7y^2 + 1
are factors, again only one with a real root. Finally, we try to
factor this with (y^2 + a y +- 1)  and see  y  satisfies  y^2 - 3y + 1,
in other words,  y=(3 + sqrt(5))/2.

B5. Looks to me like a win for player one, but I don't really have an
elegant characterization of her strategy.

If at any time she can arrange it so after her turn there are just two
heaps with the same cardinality, then it suffices thereafter to simply
mirror in the one pile the moves of player one in the other pile. Likewise
if there are two pairs of heaps of equal sizes.

Also, if a player can force there to be a single pile with 4 or 6
beans, then the game is essentially a direct win for that player.

Combining these comments, a player can win if she can leave a pair of
equal heaps, together with a heap of  4  or  6.

Here's how to get to one of those states: Player one should change
(3, 4, 5, 6) to (2, 4, 5, 6). Then here's the response to plays by
player two:

(0, 4, 5, 6)? (0, 4, 5, 5)
(2, 3, 5, 6)? (2, 0, 5, 6) (not yet in good state; see below)
(2, 4, 4, 6)? (0, 4, 4, 6)
(2, 4, 5, 5)? (0, 4, 5, 5)

In the second case, player two can respond in several ways; follow with
(0, 0, 5, 6)? (0, 0, 5, 5)
(2, 0, 4, 6)? (0, 0, 4, 6)
(2, 0, 5, 5)? (0, 0, 5, 5)

[B6: There was an error in this solution; see below.]
B6. The first observation is that the union of the sets is to be {1, 2, ...},
meaning that  0  is not to occur; in particular, [alpha] <> 0 => alpha >=1.

Now just how many elements are in S(alpha)? More precisely, for any  N
let  N_alpha=|S(alpha) intersect (0,N)|. The intersection includes
[n alpha] iff  n alpha < N, which happens only for  n  less than  N/alpha,
i.e.,  N_alpha < N/alpha (with a difference at most  1.) But
since the union of the three sets is to be all of  {1, 2, ...}  we must
have  N_alpha + N_beta + N_gamma = N (recall the sets are to be
disjoint), i.e.
	N/alpha+N/beta+N/gamma > N
(with a difference at most  3).

Now on the one hand, taking  N --> oo shows  1/alpha + 1/beta + 1/gamma = 1.
On the other hand, this in turn means
	N/alpha + N/beta + N/gamma = N;
which contradicts the previous inequality.

==============================================================================

III. Comments and feedback. For the most part these are posts by other
people taken from sci.math postings.

First let me mention that Dan Bernstein posted a complete set of solutions
(in TeX) shortly after the exam. The answers seem to be essentially the
same as mine except that he carried A-6 and B-6 properly to completion.
I'll include those solutions below. The attribution is

From: djb@silverton.berkeley.edu (D. J. Bernstein)
Date: 4 Dec 1995 21:54:25 GMT
Newsgroups: sci.math
Subject: 00A07 1995 Putnam problems and unofficial solutions (TeX)

Posts from everybody are segregated by problem.

A2============================================================================

From: baloglou@panix.com (George Baloglou)
Newsgroups: sci.math
Subject: Re: Putnam spoilers -- first go-round (A2)
Date: 5 Dec 1995 03:51:38 -0500

When a = b, an obvious substitution (u = x+a) shows the integral to be
equal to  

 - INT[a 2a]{(x^.5 - (x-a)^.5)^.5} - lim INT[M M+a]{(x^.5 - (x - a)^.5)^.5}
                                     M-->+oo
Our integral is equal to the first (certainly finite) term: indeed, the
second term is equal to zero, as a limit of integrals of a zero-approaching 
function over a constant length interval that "drifts" toward infinity.
(This solution was shown to me by a colleague of mine.)

When a =/ b, let us first observe that  (x+a)^.5 + (x-b)^.5 - 2(x)^.5
is positive for a > b and negative for a < b (the proof is routine), while,
for large x,  1/(((x+a)^.5 - x^.5)^.5 + (x^.5 - (x-b)^.5)^.5)  > 1 ; that 
is (radical manipulation), for sufficiently large x the integrand is either 
(case a > b) greater than (positive)  (x+a)^.5 + (x-b)^.5 - 2(x)^.5  or
(case a < b) smaller than (negative)  (x+a)^.5 + (x-b)^.5 - 2(x)^.5 .

The antiderivative of  (x+a)^.5 + (x-b)^.5 - 2(x)^.5  can be written as
(2/3)*(((1+(a/x))^1.5 + (1-(b/x))^1.5 - 2)/(x^(-1.5))); l' Hopital's rule
shows that the limit of the second factor as x approaches +oo is equal to
the limit of  a*((x+a)^.5) - b*((x-b)^.5) , easily seen to be +oo for a > b
and -oo for a < b. Putting everything together, we can now conclude that
our integral diverges to +oo for a > b but diverges to -oo for a < b.

I tried hard to bound  -(((x+a)^.5 - x^.5)^.5 - (x^.5 - (x-a)^.5)^.5)  
by a converging integrand but did not succeed; that is, and save for the
power series approach, the substitution trick *seems* to be the only way
to handle the case a = b. A very fine Calculus problem, indeed!

A2============================================================================
Newsgroups: sci.math
From: rjchapma@exeter.ac.uk (R.J.Chapman)
Subject: Re: 1995 Putnam problems and unofficial solutions (TeX)
Date: Wed, 6 Dec 1995 09:51:01 GMT

A2: As x->infinity we have
	  sqrt(x+a) - sqrt(x)
	= sqrt(x)(-1+sqrt(1+a/x))
	= 1/(2a sqrt(x)) ( 1 + O(1/x))
and so
	sqrt(sqrt(x+a) - sqrt(x)) = x^(-1/4)/(sqrt(2a))(1 + O(1/x)).
Similiarly 
        sqrt(sqrt(x) - sqrt(x-b)) = x^(-1/4)/(sqrt(2b))(1 + O(1/x)).

and so the integrand equals c x^(-1/4) + O(x^(-5/4)), and the
integral converges iff c = 1/sqrt(2a) - 1/sqrt(2b) = 0 i.e., iff a = b.

A4=============================================================================

From: mvs@unlinfo.unl.edu (Mark V. Sapir)
Newsgroups: sci.math
Subject: Re: Putnam exam: list of questions
Date: 3 Dec 1995 18:41:06 GMT

By the way, problem A4 about necklace is the well known problem about cars
and gasoline stations which is at least 40 years old. I think that first 
time this problem was suggested on one of the Moscow olympiads in the fifties. 
One can find this problem in many collections of olympiad problems. 
A4============================================================================

From: fardila@athena.mit.edu (Federico Ardila)
Newsgroups: sci.math
Subject: Re: Putnam spoilers -- first go-round
Date: 4 Dec 1995 18:45:07 GMT

Here's my solution to A-4, I thought it was kinda neat.
It'll probably look gross here because I'll have to write it
in equations, but it's much nicer once you draw a picture, 
and it is pretty straightforward once we choose where to cut.

First, subtract one to each number on the beads. Then their
sum is now -1, and the condition that a_1+...+a_k<=k-1
now becomes a_1+...+a_k<=-1, i.e., this sum is negative.
Consider all the possible sums of the beads on substrings 
of the necklace of any size, i.e., all the possible sums of 
numbers in consecutive beads. 
Since there is a finite number of such sums, there must be
a largest sum. Let S be the largest substring of the necklace
which gives rise to this largest sum.
Now make the cut at one end of S, so the beads are numbered
a_1,...,a_k,a_(k+1),...,a_n, where a_(k+1),...,a_n are the
beads in S.
Let S(i,j)=a_i+a_(i+1)+...+a_j, where a_(n+1)=a_1, etc...
Then for j=1,2,...,k
S(1,j)=S(k+1,j)-S(k+1,n)
but the substring k+1,k+2,...,j is longer than the substring
k+1,k+2,...,n, so it does not give rise to the maximal sum.
Then S(k+1,j)<S(k+1,n) so S(1,j)<0
Also for j=k+1,...,n
S(1,j)=S(1,n)-S(j+1,n)=-1-S(j+1,n)
But S(j+1,n)=S(k+1,n)-S(k+1,j)>=0, so S(1,j)<=-1<0
Therefore this labelling satisfies the conditions of the problem.

A4============================================================================
That positive label is $M$, and the label immediately before it is $L$.)

We now construct a smaller necklace,
by merging $L$ and $M$ into $L+M-1$.
The new necklace has exactly $n-1$ beads.
The sum of its labels is exactly $n-2$.
Hence, by induction, there is a way to cut the smaller necklace
so that its labels $y_1,y_2,\ldots,y_{n-1}$
satisfy $\sum_{i=1}^k y_i\le k-1$ for each $k$.

Now the ``same'' cut of the original necklace will work.
In $y_1,y_2,\ldots,y_{n-1}$ we un-merge $L+M-1$ into $L$ and $M$
to obtain $x_1,x_2,\ldots,x_n$;
if the merged label $L+M-1$ appears at position $p$,
we have $x_i=y_i$ for $i<p$, $x_p=L$, $x_{p+1}=M$, and
$x_{i+1}=y_i$ for $i>p$.
We check the desired condition in several cases.
For $k<p$ we have 
$\sum_{i=1}^k x_i=\sum_{i=1}^k y_i\le k-1$.
For $k=p$ we have
$\sum_{i=1}^k x_i=L+\sum_{i=1}^{p-1} y_i\le L+p-2<p-1$
since $L<1$.
For $k\ge p+1$ we have
$\sum_{i=1}^k x_i=1+\sum_{i=1}^{k-1}y_i\le 1+(k-2)=k-1$.

A4 is well known in the following form:
a string of numbers with positive sum can be rotated
so that all its initial substrings have positive sum.
Is it really the purpose of the Putnam
to measure contestants
by the number of Halmos talks they have had the opportunity to attend?

Similarly, A4 did not make clear whether one is allowed to reverse
the orientation of the necklace;
a contestant who thinks of this possibility may waste lots of time
considering it.

A4============================================================================

From: jrr@atml.co.uk (John Rickard)
Newsgroups: sci.math
Subject: Putnam A4 (necklace), and comment on B5 (beans)
Date: 5 Dec 1995 13:33:30 GMT

I haven't seen anyone post the solution I thought of when I looked at
the questions last night, though it seems to me to be more
straightforward than any I have seen posted.

Let the labels be a_1, a_2, ..., a_n.

              k
Define b_k = Sum  (a_i - (n-1)/n),   k = 0, 1, ..., n
             i=1

Then b_0 = b_n, and a_i = b_i - b_(i-1) + (n-1)/n for all i (where the
subscripts can be taken as integers modulo n).

Let b_m be the largest of the b_i.

Cut between m and m+1, so x_i = a_(m+i).

       k           k
Then  Sum x_i  =  Sum a_(m+i)  =  k(n-1)/n + b_(m+k) - b_m
      i=1         i=1
                               <= k(n-1)/n

                               <  k

(1 <= k <= n, subscripts modulo n), so since the sum is an integer it
is <= k-1.

A4============================================================================
From: rjchapma@exeter.ac.uk (R.J.Chapman)
Date: Wed, 6 Dec 1995 09:51:01 GMT

A4: Replacing x_i by 1-x_i, the hypothesis becomes that the sum is
+1, and the desired conclusion is that all sums x_1+...+x_k are positive.
In this form this is EXACTLY the problem dicsussed in Section 7.5
of Graham/Kunth/Patashnik's Concrete Mathematics. They attribute the
argument to Raney (1959) and it can be used to give the formula
for the Catalan numbers. To prove it in this form extend the
sequence by periodicity and polt a graph of the partial sums. The
average slope of this graph is 1/n, and so take the highest line
of this slope meeting the graph. This shows where to cut the necklace.
(See GKP for a more lucid account!)

A5============================================================================
[Bernstein:]
Yes, 
$x_1,\ldots,x_n$ are linearly dependent.
Let $A$ be the matrix of coefficients in this system of
differential equations.
By assumption $A$ is a nonnegative matrix,
so it has a nonnegative real eigenvalue $\lambda$.
Let $(v_1,v_2,\ldots,v_n)\ne 0$ be a corresponding eigenvector.
Define $x=v_1x_1+\cdots+v_nx_n$.
Then
$x'=\lambda x$,
so $x$ is of the form $t\mapsto r e^{\lambda t}$
for some real number $r$.
But $x(t)\to 0$ as $t\to\infty$,
so $r$ must be $0$.
Hence $x=0$.

...
A5 should have stated $n\ge 1$---the result is false for $n=0$.
...
The theorem I used in A5---any nonnegative matrix has a
nonnegative eigenvalue (namely its spectral radius)---is
perhaps too heavy for the Putnam.
You can instead observe
that the matrix has nonnegative trace,
hence an eigenvalue with nonnegative real part.
You'll have to do a bit more work than I did if the eigenvalue is not real.


A6=============================================================================
Date: Mon, 4 Dec 1995 03:06:30 -0600 (CST)
From: Sandy Kutin <sakutin@midway.uchicago.edu>
To: rusin@washington.math.niu.edu
Subject: Putnam A6

Since you seem to be compiling Putnam solutions, and didn't have
a complete A6, I humbly offer my own.  (It can be phrased in the same
random walk terms you used--however, instead of worrying about whether
the ratio of the probabilities approaches 1/6, we do some (slightly)
more precise calculations.)

A6. To simplify discussion, we say that the numbers in each column are
-1, 0, and 1.  Let P_n be the probability that the 3xn matrix has
row sums 0, 0, 0, and let Q_n be the probability the sums are -1, 0, and 1
in some order.  We need to show that, for some n >= 1995, Q_n >= 4 P_n.

Let A_n be the probability the sums are (-2, 0, 2) in some order,
B_n the probability they're (2, -1, -1), and C_n the probability they're
(-2, 1, 1).  We note that we can express the probabilities for the 3x(n+1)
matrix recursively in terms of those for those for the 3xn matrix:
for the 3x(n+1) to come out to (0, 0, 0), the 3xn has to come out to
(-1, 0, 1), and the last column has to be placed correctly, so

P_{n+1} = 1/6 Q_n

To have the 3x(n+1) come out to (-1, 0, 1), the row sums for the 3xn must
be one of the five cases listed above (each row sum would have to have
abolute value at most 2).  If the 3xn row sums are (0, 0, 0), the 3x(n+1)
sums have to be (-1, 0, 1), while in the other cases we end up with
(-1, 0, 1) for 1 or 2 of the possible values of the last column:

Q_{n+1} = P_n + 1/3 Q_n + 1/6 A_n + 1/3 B_n + 1/3 C_n.

Also, if the row sums for the 3xn come out to (-1, 0, 1), any of the
five cases above can arise depending on the last column, and we get

A_{n+1}, B_{n+1}, C_{n+1} >= 1/6 Q_n = P_{n+1},

so (note that A_1 = B_1 = C_1 = P_1 = 0), for all n >= 1,

Q_{n+1} >= 1/3 Q_n + 11/6 P_n.

Thus, for any n >= 1, if Q_n < 4 P_n, then P_n > 1/4 Q_n, and

Q_{n+1} > 1/3 Q_n + 11/6 (1/4 Q_n) = 19/24 Q_n = 19/4 P_{n+1} > 4 P_{n+1}.

So, either Q_1995 >= 4 P_1995, or Q_1996 >= 4 P_1996, proving the proposition.

A6============================================================================
[Bernstein:]
Let $(x,y,z)$ be the original row sums.
Note that $x+y+z=6n$.

Now $a=b-1=c-2$ if and only if $(x-2n,y-2n,z-2n)$ is in $S$,
where
$S=\setof{(0,1,-1),(0,-1,1),(1,0,-1),(-1,0,1),(1,-1,0),(-1,1,0)}$;
and $a=b=c$ if and only if $(x-2n,y-2n,z-2n)=(0,0,0)$.

For any $(a,b,c)$, write $p_n(a,b,c)$ for the probability that
$(x,y,z)$ equals $(2n+a,2n+b,2n+c)$.
We are asked to show that
$4p_n(0,0,0)\le \sum_{s\in S} p_n(s)$
for some $n\ge 1995$.
In fact, this is true for $n=2001$ or $n=2002$.

Define 
$X=\setof{(1,1,-2),(-1,-1,2),(1,-2,1),(-1,2,-1),(-2,1,1),(2,-1,-1)}$,
$Y=\setof{(0,2,-2),(0,-2,2),(2,0,-2),(-2,0,2),(2,-2,0),(-2,2,0)}$,
and $C=\setof{(0,0,0)}$.

Define $S_n=\sum_{s\in S} p_n(s)$;
define $X_n$, $Y_n$, and $C_n$ similarly.

With some work one can verify that
$6C_{m+1}=S_m$;
$6S_{m+1}=6C_m+2S_m+2X_m+Y_m$;
$6X_{m+1}\ge 2S_m+2Y_m$; and
$6Y_{m+1}\ge S_m+2X_m$.
Hence $36C_{m+2}=6C_m+2S_m+2X_m+Y_m$
and $36S_{m+2}\ge 12C_m+15S_m+6X_m+6Y_m$.

If $4C_{m+1}>S_{m+1}$ then
$$4S_m>6C_m+2S_m+2X_m+Y_m$$
so $2S_m>6C_m+2X_m+Y_m$.
If also $4C_{m+2}>S_{m+2}$ then
$$24C_m+8S_m+8X_m+4Y_m>12C_m+15S_m+6X_m+6Y_m$$
so $12C_m+2X_m>7S_m+2Y_m\ge 4S_m>12C_m+4X_m+2Y_m$
so $0>2X_m+2Y_m$, contradiction.

In particular, for $m=2000$, we must have
$4C_{m+1}\le S_{m+1}$ or $4C_{m+2}\le S_{m+1}$
as claimed.

A6=======================================================================

From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Putnam spoilers [problem B6] (Also a reprise on  A6)
Date: 5 Dec 1995 03:08:49 GMT

While we're polishing off the Putnam problems, let me mention that
Sandy Kutin has mailed me the rest of the proof of  A-6  (the random
walk). I'm still sort of bothered by the fact that rather a lot of
information about the probability distributions seems to be required.
I was trying to formulate a different completion to the proof; maybe
someone can help me out here.

The goal is to determine accurately the probability distribution
p_n(v)  that the walker is at vertex  v  (in the lattice  Z[w],  where
w^2-w+1=0)  after  n  steps. We know  p_0, of course, and  p_1(v)=(1/6)
for the vectors  w^i  (and is zero otherwise). The distribution  p_n
is the n-fold convolution  p_1*p_1*...p_1, where  (f*g)  means
(f*g)(v) = Sum f(v-w)g(w). 

OK, well here's my question. Is there an obvious transform  f --> T(f)
rather like the Laplace transform (say) which will give 
T(f*g)  =  (T(f)).(T(g))  (the pointwise product)? Unlike the situation with
functions on the real line, we don't have the  exp  homomorphism to
change sums to products. Well, fine; then change the domain of the
transforms or something (there's no need to have   T(f)  also defined
on the lattice). Of course my goal is to find such a transform with
a workable inverse  T^(-1) (f); for then I need only write  
p_n = T^(-1) ( T (p_1*...*p_1) ) = T^(-1) ( T(p_1)^n ). If  T  is ever
calculable, surely  T(p_1)  will be, and I ought to be able to raise it
to a power. Then  T^(-1)  might be difficult to compute in general, but I 
only need to get the values of  T^(-1) (P_n) (v)  for  v=0  and  v=w, and
Bob's your uncle.

The ideal of a random walk on this lattice is such a natural and pretty
thing that I can't imagine it hasn't been studied before. Any
suggestions?

A6============================================================================

From: jrr@atml.co.uk (John Rickard)
Newsgroups: sci.math
Subject: Re: Putnam spoilers -- first go-round
Date: 5 Dec 1995 12:44:34 GMT

The 3-fold convolution is

         1   3   3   1
       3   6   6   6   3
     3   6  15  15   6   3
   1   6  15  12  15   6   1
     3   6  15  15   6   3
       3   6   6   6   3
         1   3   3   1

and already each number is at most 1/4 the sum of the surrounding 6
numbers; it follows that the conclusion holds for all n >= 3 (indeed,
the first n - 3 columns can be chosen however you like, and only the
last 3 need be random as specified).

(I suppose this would need fleshing out with some more explanation to
be an adequate solution.)

A6============================================================================       
From: Greg Lawler (duke)
Date: Tue, 5 Dec 95 08:30:44 EST
To: rusin@washington.math.niu.edu
Subject: Re: Putnam spoilers [problem B6] (Also a reprise on  A6)

Problem 6A is a direct consequence of a theorem in probability theory.
Instead of using 1,2,3 as the numbers use -1,0,1 (so the average is zero).
Consider the random walk (X_n,Y_n) where X_n denotes the sum of the
first row and Y_n denotes the sum of the second row (we have not rearranged
the rows yet).

Then the two probabilities that we have to compare are:

a)  the probability that after n steps we are at (0,0)

b) the probability that after n steps we are at (1,0), (1,-1), (0,1),
   (0,-1), (-1,0), (-1,-1).

By the local central limit theorem for two dimensionsal random walks,
 the probabilty
of a) is asymptotic to c/n where c is some constant depending only on
the (co)variance of the random walk.  The probability of b) is asymptotic to
6c/n for the same constant c.  Hence

   P(a)/P(b)

approaches 1/6 as n goes to infinity.

A6============================================================================

From: Greg Lawler <jose>
Newsgroups: sci.math
Subject: Re: Putnam spoilers [problem B6] (Also a reprise on  A6)
Date: 5 Dec 1995 16:33:20 GMT

For those who are interested: problem A-6 can be solved immediately 
uisng the local central limit theorem for two dimensional random walks 
(see Spitzer, Principles of Random Walk, for example).  Use -1,0,1
for the numbers rather than 1,2,3 (so that the average is 0) and
let X_n and Y_n denote the sum of the first two rows after n picks
(the rows have not been rearranged yet).  We need to compare the probability
that (X_n,Y_n) equals (0,0) to the probability that it equals one
of (1,0),(1,-1),(0,1),(0,-1),(-1,0), or (-1,1).  The local central limit
theorem implies that for large n all the relevant probabilities are asymptotic,
so asymptotically the probability of one of the six points is six times
as likely as the single point.  (One can also show that it is always less
than exactly six times.)  This certainly implies for all n sufficiently
large the probability of one of the six points is more than four times
the probability of (0,0).

A6============================================================================

From: djb@silverton.berkeley.edu (D. J. Bernstein)
Date: 5 Dec 1995 19:47:58 GMT
Newsgroups: sci.math
Subject: Re: Putnam spoilers [problem B6] (Also a reprise on  A6)

(x^1y^2z^3+x^2y^1z^3+x^1y^3z^2+x^3y^1z^2+x^2y^3z^1+x^3y^2z^1)^n is the
obvious generating function. It's possible to do the problem by
rewriting this as (xyz)^n ( (x+y)(x+z)(y+z) - 2xyz )^n and then
estimating various sums.

B1============================================================================

From: elkies@brauer.harvard.edu (Noam Elkies)
Newsgroups: sci.math
Subject: Putnam problem B1 (and B2) [Re: 00A07 1995 Putnam problems and unofficial solutions (TeX)]
Date: 5 Dec 1995 02:52:06 GMT

One way to see what's going on here is that if there was a
counterexample, the map taking x to the pair (pi(x),pi(y))
would be a bijection.  Its image is a subset S of {1,2,3,...}^2
such that, for each n, the number of points of S of the form (n,*)
is a multiple of n, as is the number of (*,n)'s.  Conversely, from
such an S we readily recover (at least one pair of) partitions pi,pi'.

In particular S contains some (m,n) such that neither (m+k,n)
nor (m,n+k) is in S for any positive k.  It follows that m=n
and that S contains (j,n) and (n,j) for all positive j<n.
Also, any other point of S must have both coordinates <n.

Thus |S| is at most n^2.  It is also at least 1+2+...+n=(n^2+n)/2,
because for j<=n the j-th column contains at least 1 point, thus
at least j of them.  In our case |S|=9 so it follows that n=3.
But this is impossible because then S={1,2,3}^2 and the second
row and column contain an odd number of points of S.

This should also let us figure out for which N can there be
two partitions pi,pi' such that pi(x)=pi(y) and pi'(x)=pi'(y)
implies x=y.  Unless I have made a silly error, the answer is
all N except 2,5,9.

This seems to be the trickiest B-1 problem in recent (~15 years) memory.

B2============================================================================
From: elkies@brauer.harvard.edu (Noam Elkies)
Newsgroups: sci.math
Subject: Putnam problem B1 (and B2) [Re: 00A07 1995 Putnam problems and unofficial solutions (TeX)]
Date: 5 Dec 1995 02:52:06 GMT

Did anybody check that the ellipse actually can roll on this curve,
i.e. that its radius of curvature never exceeds that of the sine curve?

B3============================================================================
[Bernstein:]
B3 should have stated $n\ge 1$.
B3============================================================================

From: rjchapma@exeter.ac.uk (R.J.Chapman)
Date: Wed, 6 Dec 1995 09:51:01 GMT

B3: The n = 2 computation can also be done by using the bilinearity
of the determinant in terms of its rows. Hence the sum of the determinant
is det M, where the first row of M is the sum of all admissible first
rows of the determinants we're considering, and similarly for the second row.

B4============================================================================
[Bernstein:]
Define $x_0=2207$;
define $x_{n+1}=2207-1/x_n$ for $n\ge 0$.

By induction $2206<x_{n+1}<x_n\le 2207$ for all $n\ge 0$.
(For $n=0$ we have $2206<2207-1/2207<2207$.
If $n\ge 1$ and $2206<x_n<x_{n-1}\le 2207$ then
$2206<2207-1/2206<2207-1/ x_n<2207-1/ x_{n-1}$
so $2206<x_{n+1}<x_n$.)

Hence the $x_n$'s converge.
Write $x=\lim x_n$.
Then $x=2207-1/x$ so $x^2-2207x+1=0$;
since $x\ge 2206>2207/2$ we must have $x=(2207+\sqrt{2207^2-4})/2$.
Note that $2207=47^2-2$ so $2207^2-4=2205\cdot 47^2=5\cdot 21^2\cdot 47^2$.
Thus $x=(2207+21\cdot 47\sqrt{5})/2$.

We are asked to evaluate $\root8\of x$.
The answer is $(3+1\sqrt{5})/2$.
Indeed, 
$((3+\sqrt{5})/2)^8
=((7+3\sqrt{5})/2)^4
=((47+21\sqrt{5})/2)^2
=(2207+21\cdot 47\sqrt{5})/2
=x$.
...
B4 should have said either (1) assume that the continued fraction
converges or (2) prove that the continued fraction converges;
a contestant who assumes (1) will lose points if the grader thinks (2),
and a contestant who assumes (2) will waste time if the grader thinks (1).

B4============================================================================

From: Edward D Lee <speed>
Newsgroups: sci.math
Subject: Stuff of Putnam problems B4 and B5
Date: 10 Dec 1995 06:15:04 GMT

Problem B4:  I think many people solved the quadratic equation for the
fraction, and took the positive sign in front of the square root because the
fraction looked pretty big, which I do not believe is obvious at all.  I think
that to get 10 points on it you would have to justify taking the plus sign
(which would amount to showing that the convergents to the continued fraction
indeed converged to the greater root).

B4============================================================================

From: rjchapma@exeter.ac.uk (R.J.Chapman)
Date: Wed, 6 Dec 1995 09:51:01 GMT

B4: If x is the unknown, then it is seen to satisfy
	x^16 - 2207x^8 + 1 = 0
or equivalently
	x^16 + 2x^8 + 1 = 2209 x^8 = 47^2 x^8.
Taking square roots (x is positive) gives
	x^8 + 1 = 47 x^4.
Repeating this gives
	x^4 + 1 = 7 x^2
and
	x^2 + 1 = 3 x.
Now solve this equation.

B5============================================================================

From: Brian David Rothbach <rothbach>
Newsgroups: sci.math
Subject: Re: Putnam spoilers -- Bean Problem
Date: 3 Dec 1995 17:46:23 GMT

You're right,  reducing the 3 bean pile to 2 beans wins.  The simple stategy is
just don't reduce any 4 bean piles to 3 beans.  Basically, the idea is that the
only way to affect the tempo of the game is how the 3 bean piles are taken.  If
all the possible 3 bean piles are taken as three beans, the game will last ten
moves, and you will lose.  If you reduce the first three bean pile by one, you
make the game last one move longer.  There are certainly enough beans to stall
until your opponent reduces any 4 bean pile to a 3 bean pile.  Then, just take
all three beans.

Every other strategy loses.  If you take all of the three bean pile, your
opponent just has to wait until you are forced to reduce 4 bean piles to three
bean piles, and takes those three beans at a time.

If you take a bean from the 5 or 6 bean pile, he just takes all of the 3 bean
pile, and transposes into the previous situation.

Most complicated is if you take 1 bean from the four bean piles.  Now, the two
remaining 3 bean piles can't be touched, because whoever takes one of them
allows his opponent to win.  However, the first player will be forced to reduce
a third pile to three beans. The second player can safely take all three beans
of this pile, because his opponent is stuck with two three bean piles again.
At the end of the game, two three bean piles will remain, but the first player
wil have to move, and lose.  The second player simply match whatever the first
player did on the other pile.

Of course, I miscalculated this last case on my test.

Brian Rothbach
B5============================================================================

From: hoey@pooh.tec.army.mil (Dan Hoey)
Newsgroups: sci.math
Subject: Re: Putnam spoilers -- Bean Problem
Date: 3 Dec 1995 22:48:11 GMT

This problem is completely uncomplicated if you apply Sprague-Grundy
theory, turning each pile of beans into a nim-heap:

    2-piles can move only to 0, so they act like nim-heaps of size 1;
    3-piles move to 2-piles (nim 1) or to 0, so they act like
        nim-heaps of size 2;
    4-piles can't move to any 0-heap, so they act like 0-heaps;
    5-piles move only to a 0-heap, so they act like 1-heaps; and
    n-piles, n>5 act like n-2-piles, or (n mod 2)-heaps.

The winning move from any position is to move so that there are an
even number of 2-heaps (3-piles) and an even number of 1-heaps
(2 or 5,7,9,... piles).  This is possible unless you already are in
such a position, in which case you have lost.

I'm surprised they didn't at least pose the game in its misere
variant, where some analysis of the special role of 3-piles seems to
be necessary.  I think then the strategy is to play the normal game as
long as there are at least two piles greater than 2, and thereafter to
move to positions with an odd number of 2-piles (and no others).

Dan
Hoey@AIC.NRL.Navy.MIl

B5============================================================================
[Bernstein:]
The first player wins by moving to 2456.

Easy proof:
The following table exhibits a winning strategy.
Each line begins with a position $p$ and pairs of positions $q,r$.
By inspection, (1) the $q$'s are all possible results of moves from $p$;
(2) the $r$'s are valid moves from $q$;
(3) each $r$ is either ``empty'' or another position $p$ in the table.
Hence, by induction, (1) whoever moves from a $q$ position will force
a win by moving to $r$; (2) whoever moves from a $p$ position
will be forced to lose.
In particular, whoever moves from 2456 will be forced to lose.

{\noindent\parskip 0pt
4: 3, empty.

6: 5, 4.

44: 34, 4.

46: 36, 6; 45, 44.

55: 45, 44.

256: 56, 55; 246, 46; 255, 55.

444: 344, 44.

446: 346, 46; 445, 444.

455: 355, 55; 445, 444.

2456: 456, 455; 2356, 256; 2446, 446; 2455, 455.
}

Hard proof:
By induction on the number of beans,
a position of the form $m_1,m_2,\ldots,m_r$, with all $m_i\ge 4$
and $\sum m_i$ even,
is a losing position.
Indeed, 
from a position of the form
$m_1,m_2,\ldots,m_r$, with all $m_i\ge 4$ and $\sum m_i$ even,
the player might either (1) decrement an $m_i=4$ down to $3$,
or (2) decrement an $m_i>4$.
In the first case, the other player can either win
or create a smaller losing position
by removing the $3$; the sum of the remaining $m_i$'s is even.
In the second case, since the number of beans is now odd,
the other player can find a pile with more than $4$ beans,
and remove a bean from it to create a smaller losing position.
By a similar induction on the total number of beans,
a position of the form $2,m_1,m_2,\ldots,m_r$, with all $m_i\ge 4$
and $\sum m_i$ odd,
is a losing position.
In particular, $2456$ is a losing position.

...

Did the B5 author realize that one can easily solve the problem
by enumerating a small portion of the game tree?

B5============================================================================
From: jrr@atml.co.uk (John Rickard)
Newsgroups: sci.math
Subject: Putnam A4 (necklace), and comment on B5 (beans)
Date: 5 Dec 1995 13:33:30 GMT

It occurred to me that the phrase "the last heap" could be interpreted
to mean the fourth heap (which starts with 6 beans), rather than the
final remaining heap, as I presume was intended.  Then the winner
would be the player who takes the final beans from the fourth heap.
As it happens, the first player can win with the same strategy
regardless of which interpretation is used!

B5============================================================================
From: Edward D Lee <speed>
Newsgroups: sci.math
Subject: Stuff of Putnam problems B4 and B5
Date: 10 Dec 1995 06:15:04 GMT

A's strategy is simple:
(1) Move to 2456 on the first move.
(2) Thereafter, always scoop any pile of 3; never give B a position with a pile
of 3.  This is possible because B does not have a pile of 3 on his first move,
and can create only one pile of 3 with one of his moves (which A immediately
scoops).

We note that 444, 44, 4 and 0 are losing positions for B, using rule (2), and
that any progression from 2456 to one of these positions takes an even number
of moves, so B will always be stuck with one of these losing positions.

B5============================================================================

From: rjchapma@exeter.ac.uk (R.J.Chapman)
Date: Wed, 6 Dec 1995 09:51:01 GMT

B5: This is very easy for anyone knowing the theory of nim-type games.
After moving to 2456 I would describe the winning strategy as follows.
Consider the game as the "sum" of three subgames 4, 6 and 25.
If opponent removes a bean from the 4-heap, remove the heap.
If they  removes a bean from the 6-heap, remove another, yielding
a 4-heap. As above this subgame can be one.
If opponent makes a move in the 25 subgame, it is either to remove the
2-heap, or reduce the 5-heap to 4; do the other of these moves and you
have reduced to a winnable 4-heap.

B6============================================================================

From: oerjan@lie.matstat.unit.no (Orjan Johansen)
Newsgroups: sci.math
Subject: Re: Putnam exam: list of questions
Date: 4 Dec 1995 16:21:13 GMT

>>Is it possible for S(alpha) and S(beta) to be disjoint,
>>alpha,beta>0?

In fact, any counterexample would have to have alpha, beta and
alpha/beta irrational:

If alpha/beta=p/q, then q*alpha=p*beta is in both S(alpha) and
S(beta).

If alpha=p/q, then p is in S(alpha); We can then find (by Euclid's
algorithm) m and n to make 0<=n*beta-m*p<1, so m*p is in both S(alpha)
and S(beta).

However, if all three quantities alpha, beta and alpha/beta are
irrational, it might be that whenever m*alpha and n*beta are close,
there is an integer between them; I have not found out how to disprove
this, or how to find an example.
B6============================================================================

From: savitt@unixg.ubc.ca (Savitt Steve)
Newsgroups: sci.math
Subject: Re: Putnam exam: (SPOILER)
Date: 4 Dec 1995 19:47:16 GMT

>>Is it possible for S(alpha) and S(beta) to be disjoint,
>>alpha,beta>0?

...
 In fact, this will work if 
and only if alpha and beta are positive, irrational and satisfy 
1/alpha+1/beta=1. (This last condition I'll leave unproved for now, as 
the method will surely be in a posted solution for B6 later.)

If a, b are rational, they would have to be of the form q/(q-p) and q/p, 
in which case q is in both S(a) and S(b), contradiction disjointess. Take 
a and b positive, irrational, and 1/a+1/b=1.

Now suppose N is not in S(a), say n*a<N, (n+1)*a>N+1. (The inequalities 
are strict by irrationality.) Then (N+1)/(n+1)<a<N/n, so 
n/N<1/a<(n+1)/(N+1), and using 1/a+1/b=1 we find (N-n)/N>1/b>(N-n)/(N+1), 
yielding N < b(N-n) < N+1 , so N is in S(b). Thus the union of S(a) 
and S(b) is the set of natural numbers. The only elements in S(a) that 
are smaller than or equal to N are the floors of a,...,n*a and in S(b) that 
are smaller than or equal to N are the floors of b,...,(N-n)*b. This 
accounts for exactly N elements of the natural numbers, so S(a) and S(b) 
must be disjoint. (Alternately, you could trace the above inequalities 
backwards to show that if N is in S(b) then N is not in S(a).)

B6============================================================================
\solution B6.
[Bernstein:]
Suppose that $\setof{1,2,3,\ldots}$ is the disjoint union of
$S(\alpha),S(\beta),S(\gamma)$.
Without loss of generality take $\alpha\le\beta\le\gamma$.

Let $t$ be an integer.
For $i\le \ceil{t/\alpha}-1$ we have
$i\alpha<t$ so $\floor{i\alpha}\le t-1$.
Thus there are at least $\ceil{t/\alpha}-1\ge t/\alpha-1$
multiples of $\alpha$ in $\setof{1,2,\ldots,t-1}$.
Similarly there are at least $t/\beta-1$ multiples of $\beta$
and $t/\gamma-1$ multiples of $\gamma$.
Hence $t/\alpha-1+t/\beta-1+t/\gamma-1\le t-1$;
in other words $1/\alpha+1/\beta+1/\gamma\le 1+2/t$.
This is true for arbitrarily large $t$,
so $1/\alpha+1/\beta+1/\gamma\le 1$.

If $\alpha\ge 2$ then
$\floor{i\alpha},\floor{i\beta},\floor{i\gamma}\ge 2$,
contradiction.
Thus $\alpha<2$.

Write $n=\floor{\gamma}$.
Let $k$ be the number of multiples of $\beta$ in $\setof{1,2,\ldots,n-1}$.
Then $\alpha$ has exactly $n-k$ multiples in $\setof{1,2,\ldots,n-1}$,
so $\floor{(n-k)\alpha}\le n-1$
and $\floor{(n-k+1)\alpha}\ge n$.
On the other hand $\floor{(n-k+1)\alpha}$ cannot equal $\floor{\gamma}=n$,
so $\floor{(n-k+1)\alpha}\ge n+1$.
Thus
$$(n-k)\alpha=(n-k+1)\alpha-\alpha\ge\floor{(n-k+1)\alpha}-\alpha\ge n+1-2=n-1.$$
So $\floor{(n-k)\alpha}=n-1$.
Next $\floor{k\beta}\le n-1$, but $\floor{k\beta}$ cannot equal
$\floor{(n-k)\alpha}=n-1$,
so $\floor{k\beta}\le n-2$.

We have $(n-k)\alpha<n$ so $1/\alpha>(n-k)/n$;
$k\beta<n-1$ so $1/\beta>k/(n-1)$;
and $\gamma<n+1$ so $1/\gamma>1/(n+1)$.
Add: $1\ge 1/\alpha+1/\beta+1/\gamma>(n-k)/n+k/(n-1)+1/(n+1)$.
Clear denominators:
$n(n-1)(n+1)\ge (n-1)(n+1)(n-k)+n(n+1)k+n(n-1)
=n^3+(k-2)n+n^2+k$.
Hence $0\ge n^2+(k-1)n+k$.
Since $n\ge 1$ and $k\ge 1$, this is absurd.

B6============================================================================
From: heuser04@umanitoba.ca
Newsgroups: sci.math
Subject: Re: Putnam spoilers [problem B6]
Date: Mon, 4 Dec 1995 22:34:45 GMT
Reply-To: wolk@ccm.UManitoba.CA (Barry Wolk)


>have  N_alpha + N_beta + N_gamma = N (recall the sets are to be
                  ***error***: this ^ should be N-1

If this proof were valid, it would also show that {1, 2, 3, ...} cannot be 
expressed as the disjoint union of two sets,  S(alpha) and S(beta). However,
this last result is false --  as others have posted, take alpha and beta to
be any positive irrationals satisfying 1/alpha + 1/beta = 1.

B6============================================================================

From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Putnam spoilers [problem B6] (Also a reprise on  A6)
Date: 5 Dec 1995 03:08:49 GMT

Indeed. I noticed this error this morning and tried to patch it. I now
see Dan Bernstein has posted an argument which appears to do this more
carefully and successfully.

In response to some questions about these sets  S(alpha)  I was trying
an alternative proof, but couldn't complete it. I wonder if anyone could
prove the missing link. As several posters have noted we have

Theorem: If  alpha  and  beta are irrational and  1/alpha + 1/beta=1,
then  S(alpha) and S(beta) are disjoint and have union  {1, 2, 3, ...}

Corollary: If  alpha  and  beta  are irrational and there are integers
m  and  n  such that  m/alpha + n/beta =1, then  S(alpha) and S(beta)
are disjoint. (Proof: They're subsets of  S(alpha/m)  and  S(beta/n)
respectively, which partition {1, 2, ...} by the Theorem.)

Well, OK, is the converse (or something like it perhaps) true?

Conjecture: If  S(alpha) and  S(beta)  are disjoint, then  alpha  and
beta  are irrational and there are integers  m  and  n  such that
m/alpha + n/beta = 1.

(Of course if the purported equation holds and one of  alpha  and  beta
is rational, so is the other, so that there will be an integer in common
in  S(alpha) and  S(beta), contradiction. Thus what's really being con-
jectured is not the irrationality but the existence of  m  and  n, that
is, the proof that  alpha = m*beta/(beta-n)  for some  m  and  n.)

This would suffice to prove the Putnam problem. For if both  S(beta)
and  S(gamma)  were disjoint from  S(alpha), then there would have to be
integers  m, n, r, s  such that  alpha=m*beta/(beta-n)  and 
gamma=r*alpha/(alpha-s) = (r*m)*beta/((m - s)*beta + s*n). If in addition
S(beta) and S(gamma) were disjoint from each other, then we would
similarly have  gamma = p*beta/(beta-q)  for some  p  and  q, which gives
(r*m-p*(m-s))(beta)= s*n*p + r*m*q. The right side is positive, not zero,
so the left side isn't zero either; dividing shows  beta is rational,
making alpha (and gamma) rational, violating disjointness.

This would be a different (better!) proof of the Putnam problem because
it would relax the hypothesis that the union of the three sets be _all_
of the natural numbers, and yet would still draw a contradiction.

[THE FOLLOIWNG PORTION NOT POSTED]

Theorem 1. If  1/alpha + 1/beta = 1 then  S(alpha) and S(beta) have a
disjoint union equal to  {1, 2, ...}  iff  alpha (and thus beta) is irrational.

Proof. If alpha = m/n, then  m = n*alpha =(m-n)*beta  shows the sets are
not disjoint. So assume the numbers irrational.

If, say, alpha is larger than beta, the assumed equation forces 
beta < 2 < alpha; let us write  beta = 1 + 1/e  for some  e>1. We then
compute  a = 1+e.

It's easy to see that  S(beta)  is already most of the set of natural
numbers, especially if  e  is large. Indeed, we have  [n beta] =[n + n/e]
=n + [n/e]  is usually only larger by one than  [(n-1) beta] = n-1 + [(n-1)/e].
Indeed, the only time there is a "jump" is when  n  crosses a multiple of  e.
If  n = [me] = me - epsilon, (0 < epsilon < 1) then  [n beta] = n + [m-eps / e]
=n+m-1  and  [(n+1) beta] = n+1 + [m + (1-eps)/e] = n+1+m, so that  n+m  is 
skipped. Therefore,  S(beta)  is precisely the set of all natural numbers
except those of the form  { [me] + m }  for some integer  m. But this set
is precisely the set 
	{ [m*(1+e)] } = S(1+e) = S(alpha). //

B6============================================================================

From: hwatheod@leland.Stanford.EDU (theodore hwa)
Newsgroups: sci.math
Subject: Re: Putnam exam: list of questions
Date: 5 Dec 1995 04:24:21 GMT

Orjan Johansen (oerjan@lie.matstat.unit.no) wrote:
: Is it possible for S(alpha) and S(beta) to be disjoint,
: alpha,beta>0?

Yes.  Beatty's Theorem: If alpha,beta are irrational and 1/alpha + 1/beta
is equal to 1, then S(alpha) and S(beta) are disjoint, and their union
is {1,2,3,...}.

B6============================================================================

Date: Mon, 4 Dec 1995 22:25:12 -0800 (PST)
From: theodore hwa <hwatheod@leland.Stanford.EDU>
To: Dave Rusin <rusin@math.niu.edu>
Subject: Re: Putnam exam: list of questions

On Tue, 5 Dec 1995, Dave Rusin wrote:
> Have you got a reference? (I was interested in a converse: if S(alpha) and
> S(beta) are disjoint, is it true that for some integers m and n  we have
> m/alpha+n/beta=1 ?)

The converse was something I thought about during the exam, though I still
don't know if it is true.  As for the original result, I don't know of a
reference that discusses it in detail although I can provide a proof if
that's all you're looking for.  Suppose a,b are irrational with 1/a + 1/b
= 1.  First we show that [ma] and [nb] are disjoint (m,n positive
integers.) Suppose otherwise, so that for some positive integer d,
[ma]=[nb]=d.  Then d< ma < d+1 and d< nb < d+1. Or, d/m < a < (d+1)/m and
d/n < b < (d+1)/n.  Reciprocating both inequalities and adding, (m+n)/d >
1 > (m+n) / (d+1), or 1/d > 1/(m+n) > 1/(d+1), contradiction since d,m,n
are all positive integers. 

Now suppose some integer d is not of the form [ma] or [nb].  Then
for some m,n, ma < d < d+1 < (m+1)a and nb < d < d+1 < (n+1)b.
Now ma < d and nb < d ==> a < d/m, b < d/n, or 1 > (m+n)/d, or d > m+n,
while d+1 < (m+1) a and d+1 < (n+1) b ==> (d+1)/(m+1) < a, (d+1)/(n+1) < b,
or (m+n+2) / (d+1) > 1, or m+n > d-1.  Contradiction.

B6============================================================================

From: jrr@atml.co.uk (John Rickard)
Newsgroups: sci.math
Subject: Re: Putnam spoilers [problem B6] (Also a reprise on  A6)
Date: 5 Dec 1995 13:00:09 GMT

The solution I found to B6, which I think is simpler than any I've
seen posted, does indeed show that S(alpha), S(beta), and S(gamma)
cannot be disjoint.

The idea is simply that one can find a multiple of each of alpha,
beta, gamma so that the three multiples are close to each other; then
they can have at most two distinct integer parts.

This can be shown easily using the pigeonhole principle.  Let N be an
integer larger than all of alpha, beta, gamma.  Consider the vectors
({i/alpha}, {i/beta}, {i/gamma}), i = 0, 1, ..., N^3, where
{x} = x - [x] is the fractional part of x.  There are N^3 + 1 of them,
so if the unit cube is divided into N^3 subcubes of side 1/N then two
of the vectors must be in the same subcube.  Say
({i/alpha}, {i/beta}, {i/gamma}) and ({j/alpha}, {j/beta}, {j/gamma})
are in the same subcube.  Let k = | i - j |.  Then k/alpha, k/beta,
k/gamma are each within 1/N of an integer -- say a, b, c respectively.
So a alpha, b beta, c gamma are each distant less than 1 from k (since
N > alpha, beta, gamma), and so [a alpha], [b beta], [c gamma] are
each either k-1 or k, so two of them are equal.

B6============================================================================

Date: Tue, 5 Dec 95 11:43:31 CST
From: rusin (Dave Rusin)
To: rusin
Subject: completion of B6 argument [not posted]

Here's the correct conclusion to the argument, based on Dan Bernstein's solution.

Suppose we find an initial string consisting only of  k  integers
[m alpha]   and  n  integers  [m beta], all distinct and thus covering
the set {1, 2, ..., n+k}. If, say, [k alpha] is larger than  [n beta],
then we have  k alpha < n+k+1  and  n beta < n+k. In particular,
1/alpha > k/(n+k+1)  and  1/beta > n/(n+k). Adding we see
	1/alpha + 1/beta > ( (n+k)^2 + n)/((n+k)(n+k+1))=1 - k/((n+k)(n+k+1))

Next, if this initial string is the longest involving only multiples of
alpha and beta, then the very next integer  n+k+1  must be  [1*gamma],
so that  gamma < n+k+2, and
	1/alpha+1/beta+1/gamma >
		> 1 + [1/(n+k+2) - k/((n+k)(n+k+1))]
		=  1 + (n^2+n+(n-1)k)/((n+k)(n+k+1)(n+k+2))  >  1,
which is a contradiction.

B6============================================================================

From: dsavitt@unixg.ubc.ca (David Savitt)
Newsgroups: sci.math
Subject: Re: Putnam spoilers [problem B6]
Date: 5 Dec 1995 21:37:34 GMT

Here's how I finished it off: for a suitable rearrangement of alpha, 
beta, and gamma, we have N_alpha*alpha < N, N_beta*beta < N-1, and 
N_gamma*gamma < N-2 by disjointness. Dividing these inequalities by 
alpha, beta, and gamma respectively and summing, we find 

 N_alpha+N_beta+N_gamma<(N-1)(1/alpha+1/beta+1/gamma)+1/alpha-1/gamma

    N-1 < N-1 + 1/alpha-1/gamma    => gamma > alpha

In particular, now, suppose gamma<beta<alpha, and choose N such that N-1 
is in S(gamma). The above shows either gamma > alpha or gamma > beta, a 
contradiction.

******************************************************************************