Conference rusure::math

        Partial "spoilers".  Don't look at these hints if you
        want to work on these yourself.
        
        You're looking! :-)
        
        You'll love the solution to A-1.  Once you have an
        answer, proving it by induction is easy.  But getting to
        that point was rather involved.  A-2 is yes.  A-3 reduces
        by Pick's [?] theorem to showing the figure must contain
        at least one interior lattice point.  I haven't worked on
        that part yet.  A-4 is continuum many.  A-5 is no, I have
        a counter-example with 4x4 matrices.  A-6 I've only done
        for n=0,1, and 2 (the problem asks for the result when
        n=10).  B-1 has two rather simple solutions.  I haven't
        done any of the others yet.
        
        Dan
        

    re .0 .1,
    
    Dan,
    
    I haven't looked at the rest of the problem set, but the answer to 
    A_4 is at most countably many.  You just need to place the paper
    punch at the points with rational coordinates...
    
    Proof:  Let (x, y) be a point on the plane.  If x and y are both
    rational, then paper punch centered at (x+1, y+1) works.  If only one of
    the two are rational, say x is rational, then the paper punch centered
    at (x, 0) works.  
    
    Suppose x and y are both irrational and the distance between (x, y) and
    any rational points are rational.  Then sqrt(x^2 + y^2) must be
    rational, hence equal to p/q where p, q are in Z.  So we have
    x^2 + y^2 = p^2/q^2.  Now the distance between (x, y) and (1, 0) must
    also be rational, so sqrt((x-1)^2 + y^2) = a/b where a, b are in Z
    ==> p^2/q^2 - 2x + 1 = a^2/b^2.  Since a, b, p, q are all in Z (the
    integers), this implies x is rational.  This contradicts the assumption
    that x and y are both irrational.  Q.E.D

    As a matter of fact, I believe you may only need finite many punches.  
    That is yet to be proven, but if you look at case three, you will find
    that after making a punch at (0,0) and (0,1), you have already removed 
    all the points both coordinates irrational.
    
    Eugene
                        

    
    	A-5 :
    		Here's a simple 3x3 counter-example.
    
    		A = 1  0  0	B = 0  0  1
    		    0  0  1	    1  0  0
    		    0  0  1	    0  0  0
    
    		AB = 0  0  1    ABAB = [0]
    		     0  0  0
    		     0  0  0
    
    		BA = 0  0  1    BABA = 0  0  0
    		     1  0  0           0  0  1
    		     0  0  0           0  0  0,  
    
    		hence the proof.
    		     
    
    
    	A-3:
    
    	This seems intuitive geometrically, given the following :
    	a) We can have the orgin as one of the vertices,
    	b) Given any convex pentagon, we can find one equal to or lesser
    	   in area by reducing one of the obtuse angles to 90 deg.,
    	c) Given the above 2 plus the fact that the vertices have
    	   integral coordinates, the smallest such pentagon that
    	   can be constructed has area of 5/2, and with coordinate
    	   pairs for the 5 vertices being {(0,0), (1,0), (0,1), (2,1) &
           (1,2)} or {(0,0), (1,0), (0,1), (2,2) and (2,1)} or
    	   {(0,0), (0,1), (1,0), (2,2) and (1,2)}.
    		
    
    	A-1's got me in knots so far ....
    
    
    	/Venu

        re .2,
        
        Reviewing my notes, I see that on my first pass I blew
        away everything except for circles with rational radius
        centered at the origin.  Then I inverted the sense of the
        paper punch and only removed points a rational distance
        away from any later punch centers.  Oops.  :-)  Each
        "reversed" punch couldn't do very much as it could only
        get rid of at most the countably many points
        "quadratically" related to its coordinates.
        
        I was suspicious since my "proof" used the axiom of
        choice (more specifically, the countable AC, to show that
        a countable union of countable sets is countable) but I
        still didn't catch the error.
        
        Dan

        re .2, .4, A-4
        
        Two points is insufficient.  Three points is sufficient.
        
        Select any two distinct points in the plane as punch
        centers.  If the distance between the two points is
        rational, neither was removed by either punch.  But that
        is irrelevant.  Let the distance between the two points
        be t.  Let q be a rational between 0 and t.  Call the
        points A and B.  Consider the circle of radius q around
        A.  Consider the line containing A and B, it intersects
        the circle at distances t-q and t+q from B.  As you
        continuously travel along the circle between those two
        intersection points, the distance from B continuously
        varies, taking on every value between t-q and t+q.  Some
        of those values are rational, and any such point is also
        the rational distance q away from A.
        
        Use the three punch centers (0,0), (1,0), and (a,0),
        where a is any real that is not quadratic over the
        rationals (for example, e, or the cube root of two).
        
        Dan

        A-1.

        T(0) = 2, T(1) = 3, T(2) = 6, and for n >= 3,
        T(n) = (n+4)T(n-1) - 4nT(n-2) + (4n-8)T(n-3)
        T(n) = A(n) + B(n), a sum of two "well-known sequences".

        First I figured I would try some interesting sequences
        like the Fibonacci numbers or powers of two.  And in fact
        subtracting the Fibonacci sequence 1,1,2,3,5,...
        (starting with 0,1,1,2,3,... didn't yield anything) gives
        1,2,4, (is it? is it?) 11, (no), ....

        So I set out to solve it using generating functions.  For
        example, take the Fibonacci sequence F(0)=0,F(1)=1,for
        n>=2 F(n)=F(n-1)+F(n-2).  Let f(x) = sum(n=0,...,oo) F(n)x^n
        Then xf(x) is a sum of terms like F(n-1)x^n and x^2 f(x)
        is a sum of terms like F(n-2)x^n.  Since F(n)=F(n-1)+F(n-2)
        we have f(x) = xf(x) + x^2 f(x) + stuff, where stuff
        accounts for the "edge effects" of the lower order terms
        (we were breaking from the relation F(n)=F(n-1)+F(n-2) by
        implicitly setting F(-1)=F(-2)=F(-3)=...=0).  The result
        is (1 - x - x^2)f(x) = a + bx.  Solve 1 - x - x^2 = 0 to
        get roots r and s, making 1 - x - x^2 = (1-rx)(1-sx). 
        Divide by that and use partial fractions to rewrite it as
        f(x) = c/(1-rx) + d/(1-sx).  Since 1/(1-rx) = 1 + rx + r^2x^2
        + ... + r^n x^n, and since f(x) is the sum of F(n) x^n,
        we get F(n) = c r^n + d s^n.  This process will be a
        little harder for T(n) because the coefficients of the
        lagged terms are not constants (they depend on n), but
        let's try it and see what happens.

        First set f(x) = sum(n=0,...,oo) T(n)x^n.  Note that the
        coefficient of x^n for xf, x^2 f, x^3 f, etc. are
        respectively T(n-1), T(n-2), T(n-3), etc.  To get an "n"
        term, differentiate xf.  The coefficient of x^n in (xf)'
        becomes (n+1)T(n).  Multiplying by x shows that x(xf)' is
        associated with nT(n-1).  Likewise x(x^2 f)' with nT(n-2)
        and x(x^3 f)' with nT(n-3).  Putting this all together
        and keeping careful track of the low order terms yields

        x(xf)' + 4xf - 4x(x^2 f)' + 4x(x^3 f)' - 8x^3 f
        	= f - 2 + 11x - 4x^2

        Regrouping,

        (x^2 - 4x^3 + 4x^4)f' - (1 - 5x + 8x^2 - 4x^3)f
        	= -(2 - 11x + 4x^2)

        Factoring and isolating f' yields

                1-x       2 - 11x + 4x^2
        f' + (- ---)f = - --------------
                x^2	  x^2 (1 - 2x)^2

        Noting that 1/(1-2x) = 1+2x+4x^2+8x^3+... suggests trying
        2^n, but earlier I had shown T - Fibo ==> 1,2,4, then 11.

        Now, what we have above is an easily solved differential
        equation in f.  Solve it for f, express that as a Taylor
        series in x and voila!  To solve it you first find a
        solution for the homogeneous equation

        	f' + (- (1-x)/x^2 )f = 0

        The solution to f' + P(x)f = 0 is f = exp(integral(-P(x)dx))
        which yields f(x) = exp(integral( (1/x^2 - 1/x)dx )) or
        f(x) = exp( -1/x + ln x) or f(x) = (1/x)exp(-1/x).

        Oh, no.  As a series that gives a series in 1/x instead of
        a series in x.  I actually used this solution to try to
        solve the full equation with the non-homogeneous term
        (lots of partial fractions!).  Don't bother.  I didn't
        get anything I could use.

        Sigh.  I was actually looking at this in the form

        	f' = (1-x)/x^2 f

        Eventually that x^2 term moved itself out of the
        denominator and I was staring at

        	x^2 f' = (1-x)f

        Something clicked ... those look like the kind of terms I
        used to convert the difference equation in T to a
        differential equation in f.  Since I can't get a power
        series for this f, why not convert this back to a
        difference equation?  This simplified equation (I dropped
        out the inhomogeneous term) can correspond to a new
        sequence S related to T.  Let's see now, f corresponds to
        S(n), f' to (n+1)S(n+1), xf' to nS(n), and x^2 f' to
        (n-1)S(n-1). (1-x)f = f - xf corresponds to S(n) - S(n-1).
        So (n-1)S(n-1) = S(n) - S(n-1), or nS(n-1) = S(n).  What??
        S(n) = nS(n-1) ... I recognize that!!

        I think you can finish from here.  Solve for S, see if T
        = S + something interesting, it does, so take that
        formula for T(n) and use induction to prove it.

        Dan

        In .6, when solving difference equations using generating
        functions you usually consider yourself to be doing
        formal manipulations without regard to questions of
        convergence and the like.  When you get an "answer", you
        prove it by induction, thus sweeping any problems with
        the method of getting the answer under the proverbial
        rug. As it happens, the series T(0) + T(1)x + T(2)x^2 +
        ... has coefficients that grow so fast that the radius of
        convergence of the series is zero.  I wonder if that is
        related to not being able to get a useful form for f(x).
        
        Dan

A-6

Suppose |S| and |T| are known.  How many ordered pairs are there?

Let a=|S| and b=|T|.  So S contains a elements of {1..n} s.t. each > b.
There are C(n-b,a) ways of doing this, where C is `choose', i.e., the binomial
coefficient.  Similarly, there are C(n-a,b) ways to choose the elements of T.
So given a and b, there are C(n-b,a)C(n-a,b) ordered pairs.
The above holds if a+b <= n; if a+b < n, then there are no ordered pairs.
BTW, note that C(n-b,a) = C(n-a,b).

The answer to A-6 is then

			 2			      2
	  Sum	 C(n-b,a) ,  or	      Sum       C(c,a)
	a+b < n			0 <= a < c <= n
	0 <= a,b

How does this simplify?

For A-1, I noticed that 363392 ~ 9*40576, and 40576 ~ 8*40576, etc, so 
a factorial was indicated.  Trying T_n = n! + U_n suggested U_n = 2^n.
T_n = n! + 2^n fit the recurrence, and the first 3 values fit, so QED.

B-2 yields to an inductive argument similiar to A-1. Just combine the
first two terms, note the simplifications, add the third term, note the
simplification, generalize by induction, and show (based on the fact that
there is some N such that j>N implies x^j < min((z-1)/2,1/z^2)) that the
simplified form goes to zero.

A solution for B-4:

Assume for convenience that a != b and a != b^-1. (G is cyclic and the
proposition is trivially true in these cases.)

Consider the directed graph D whose vertices are the elements of G and whose
edges are all the (directed) lines running from any element g in G to ga or to
gb.

We assert that G is strongly connected (ie any vertex is reachable from any
other).

For consider the set of R elements reachable from the identity. This is the set
of elements of G can be expressed as a product a^i1.b^i2.a^i3...b^ik for some
suitable choice of positive integer exponents {i}. 

Since G is finite of order n, we know a^n = e, the identity, and hence
a^n-1 = a^-1. So a^-1 is in R and similarly b^-1 is in R. This means that each
of a^-1 and b^-1 is expressible as a product of positive powers of a and b.

But any element of G is expressible as a product of (possibly negative) powers
of a and b, and by substituting the positive power expressions for a^-1 and
b^-1 where necessary, we can express any element of G as a product of positive
powers. Hence, R is the whole of G.

Thus any vertex of D is reachable from the identity, Also, the identiity is
reachable in D from any vertex. To reach the identity from vertex g, express
g^-1 as a product of positive powers of a and b and follow that path through
the graph.

Hence (by transitivity, if you want to be picky) we have shown that D is
strongly connected.

It is obvious that the out-degree of each vertex is 2, one edge to ga and one
(distinct) edge to gb. The in-degree of each vertex is also 2, since the only
possible incident edges arise from g.a^-1 and g.b^-1, (uniqueness by group
cancellation law) and each of these does exist.

So D is a strongly connected directed graph with the in-degree of each vertex
equal to its out-degree. This is a necessary and sufficient condition for D to
have an Eulerian trail (closed directed spanning circuit which cvers every
edge.)

List the vertices on one such trail. The list has the property that: each
vertex is visited exactly twice, and the label of the successor on each vertex
is obtained by postmultiplying the label of that vertex by a or b. These are
the conditions of the proposition, which is therefore proved true.

As an added bonus, the BEST theorem even tells us how may such sequences there
are.

Andy.
    
                                                   

A solution for B-5:

	Given a0,...,a_n, we take a_(n+1) spectacularly teeny with respect to
all the a_j already defined.   This can ensure that in p_(n+1)(x), the n
roots of p_n(x) are perturbed by at most |a_(n+1)| in the limit.   That keeps 
us with n distinct roots.   Now, the (n+1)th root must be real, since complex
roots of real-valued polys come in pairs, and we already have n real ones.

	p_(n+1)(x) can only have a repeated root if z = x^(n+1)*p_(n+1)(1/x)
has a repeated root.   A poly has a repeated root if gcd(z, dx/dx) is
not a constant.   By tweaking a_(n+1) if we were unlucky enough to have 
a value which caused the (n+1)th to coincide with one of the ones we already
had, we can avoid a problem.

Regards,
Andrew.

>A-6
>
>Suppose |S| and |T| are known.  How many ordered pairs are there?
>
>Let a=|S| and b=|T|.  So S contains a elements of {1..n} s.t. each > b.
>There are C(n-b,a) ways of doing this, where C is `choose', i.e., the binomial
>coefficient.  Similarly, there are C(n-a,b) ways to choose the elements of T.
>So given a and b, there are C(n-b,a)C(n-a,b) ordered pairs.
>The above holds if a+b <= n; if a+b < n, then there are no ordered pairs.

	Yes.

>BTW, note that C(n-b,a) = C(n-a,b).

	No:	C(2-1,0) = 1 <> 2 = C(2-0,1)

	I still can't simplify the sum of all these chaps though.   A thought:
does Mr Putnam mean us to use *arithmetic* (byeuch!) to get the answer for
n=10?

	The only other approach which I can think of is an inductive one,
based on classifying any admissible pair by the cardinality of the two sets
as above, and at the same time by the min of each set.   Then induce over n.

Regards,
Andrew.

>The answer to A-6 is then
>
>                         2                            2
>          Sum    C(n-b,a) ,  or       Sum       C(c,a)
>        a+b < n                 0 <= a < c <= n
>        0 <= a,b
>
>How does this simplify?

Rewriting this as 

                                                2
           Sum        (       Sum         C(c,a)   )
        c = 1 to n        a = 0 to c-1

that inner sum reduces to C(2*c,c)-1.

Having patted myself on the back for finding this I then discovered that this
was a result known to the Chinese in the early 1300's. I'm always the last to
know.

The outer sum looks as if it ought to simplify, but it's beyond me.

Dick

>> Problem A-6
>> If X is a finite set, let |X| denote the number of elements in X. Call
>> an ordered pair (S,T) of subsets of {1,2,...,n} admissible if s > |T|
>> for each s \in S, and t > |S| for each t \in T. How many admissible
>> ordered pairs of subsets of {1,2,...,10} are there? Prove your answer.
        
        17711.
        
        Dan

        n # admissible pairs
        - ------------------
        1	    3
        2	    8
        3	   21
        4	   55
        5	  144
        6	  377
        7	  987
        8	 2584
        9	 6765
        10	17711
        
        If you define the n-th Fibonacci number so that Fibo(0) = 0
        Fibo(1) = 1, then the number of admissible pairs of
        subsets of {1,...,n} is Fibo(2n+2).
        
        Dan

	Congrats to Dan for the key insight that the pattern is alternate 
Fibonacci.   After that, the problem just solves itself...


	We want an analytic expression for:

	f(n) = sum (a+b =< n) C(n-a,b) * C(n-b,a)

where n, a & b are natural numbers.   In fact, if we define C(x,y) = 0
when y < 0, or when y > x, then we can imagine that the sum is over all
integers a & b such that they sum to the natural n.

	Moreover, the key identity:

C(n,x) = C(n-1,x) + C(n-1,x-1) 

is then valid for all integers n and x *except* for the case n=x=0, since
C(0,0) = 1.

	f(n) = sum (a+b =< n) C(n-a,b) * C(n-b,a)

	     = sum (a+b =< n) C(n-a,b) * [C(n-b-1,a) + C(n-b-1,a-1)]
	     + C(n-0,n) * C(n-n,0)

	     = sum (a+b =< n) C(n-a,b) * C(n-b-1,a)
	     + sum ((a-1)+b =< (n-1)) C((n-1)-(a-1),b) * C((n-1)-b,a-1)
	     + 1

	     = sum (a+b =< n) C(n-a,b) * C(n-b-1,a)
	     + f(n-1)
	     + 1

	So, let's define g(n),
	     = 1 + sum (a+b =< n) C(n-a,b) * C(n-b-1,a)
 
	Thus f(n) = f(n-1) + g(n).

	g(n) = 1 + sum (a+b =< n) C(n-a,b) * C(n-b-1,a)

	     =  1 + sum (a+b =< n) [C(n-a-1,b-1) + C(n-a-1,b)] * C(n-b-1,a) 
		+ C(n-n,0) * C(n-0-1,n)

	     =  1 
	     + sum (a+b =< n) C(n-a-1,b-1) * C(n-b-1,a) 
	     + sum (a+b =< n) C(n-a-1,b) * C(n-b-1,a) 
	     + 0

	     =  1 
	     + sum (a+(b-1) =< (n-1)) C((n-1)-a,b-1) * C((n-2)-(b-1),a) 
	     + sum (a+b =< (n-1)) C((n-1)-a,b) * C((n-1)-b,a) 
	     + sum (a+b = n) C((n-1)-a,b) * C((n-1)-b,a) 
	     
	     = g(n-1)
	     + f(n-1)
	     + 0.

	Thus, if we put f(n) = F(2n+2), and g(n) = F(2n+1), we find that
f & g satisfy F(m)+F(m+1)=F(m+2).   All it remains to do is to examine
F(2) = f(0) = 1, and F(3) = g(1) = 2, to confirm that what we have in F is the
Fibonnacci series, and that f(10) = F(22).

Regards,
Andrew.

>> .17
>>	Congrats to Dan for the key insight that the pattern is alternate 
>> Fibonacci.   After that, the problem just solves itself...
        
        That's what I thought ... state the induction hypothesis,
        then sit back and wait for the problem to solve itself. 
        And it did! :-)
        
        As for the "key insight", the table in .16 was generated
        backwards.  I used LISP and had a list of the 1024
        subsets of {1,...,10}, and I counted how many of the
        1,048,576 pairs were admissible.  That's all that was
        needed for the numerical answer to A-6.
        
        Only as an afterthought did I take the subsets with a 10
        out of the list and count up the answer for n=9; then
        take out the subsets with a 9 and count up the answer for
        n=8; etc.  So I caught the Fibonacci sequence from the
        generated answers 144 (square, Fibo), 55 (yeah, that's a
        Fibo too, isn't it?), 21 (that clinches it, they must all
        be Fibo's). [I'm so trusting. :-)]  The final 8 and 3
        weren't surprises, but it was obvious some Fibonacci
        numbers were missing, so I generated a list of them to
        see that the way the missing ones were skipped was
        regular.
        
        But that raises the question ... how did they expect the
        problem to be solved?  From the pattern 3-8-21 for
        n=1,2,3?  There are already 64 total pairs of subsets for
        n=3 (that increases as a factor of four as n is
        incremented).  This is a pencil and paper test with three
        hours for each six-question part.
        
        So what is the insight going from n to n+1 that they
        expected people to get?
        
        Dan