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

Conference rusure::math

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

1970.0. "Big E Math Contest" by POLAR::WALSHM () Thu Apr 27 1995 12:58

    From the University of Waterloo's 1994 "Big E" undergrad math
    contest...
    
1. For any positive integer n we define the positive integer s(n) to be the 
smallest positive integer for which
			    1   1          1
			1 + - + - + ... + ---  >= n
			    2   3         s(n)
Evaluate
		             s(n+1)
		        lim  ------
		       n->oo  s(n)

2. Prove that the famous four colour map theorem does not work on a Moebius 
band: divide the Moebius band into five regions so that any two of them have a 
common boundary.  (In dividing and colouring the Moebius band remember that it 
has no thickness.)

3. For any n = 1,2,... let M be the n x n matrix of positive integers whose 
(j,k)th entry is the greatest common divisor of j and k.  Evaluate the 
determinant of M.

4. Let x^y denote the smaller of the numbers x and y.  For what values of L>0 
does the equation
			/1
			| (x^y)f(y)dy = Lf(x)
			/0
have continuous solutions f which do not vanish identically on (0,1).  Find 
these solutions.

5. Suppose h is a bounded strictly decreasing real valued function with h(t*)=0 
for some t* in R.  For n >= 0 define
			             1
			t    = t  + ---h(t )
			 n+1    n   n+1   n
Show that for any choice of t  in R we have  lim t  = t*.
			     0		    n->oo n
    
    Enjoy,
    
    Matt
T.RTitleUserPersonal
Name
DateLines
1970.1Answer to #2FLOYD::YODERMFYThu Apr 27 1995 14:5218
Color the band (before twisting) this way:

  ---------------------
  |         |         |
  |  1      |     2   |
  |     ---------     |
  |     |       |     |
  |     |       |     |
  |-----|   3   |-----|
  |     |       |     |
  |     |       |     |
  |     ---------     |
  |  4      |     5   |
  |         |         |
  ---------------------

The only disconnected pairs are (1,5) and (2,4).  But making a half-twist and
joining the sides will join these pairs also.
1970.2Answer to #1FLOYD::YODERMFYThu Apr 27 1995 15:3815
Let H(n) denote the harmonic sum.  It is clear that the difference between
H(s(n)) and n is less than 1/s(n).  Also, we know that H(n) = ln n + K + o(1)
where K is Euler's constant.  So,

  H(s(n)) = n + o(1)

  ln s(n) + K + o(1) = n + o(1)

  ln s(n) = n - K + o(1)

  s(n) = exp(n-K)*exp(o(1))

  s(n+1)/s(n) = e*exp(o(1))

  so s(n+1)/s(n) -> e.
1970.3Answer to #4FLOYD::YODERMFYThu Apr 27 1995 17:2134
Let us use S(a,b) to denote an integral from a to b.  We want

  S(0,1)min(x,y)f(y)dy = Lf(x), or

  S(0,x)yf(y)dy + xS(x,1)f(y)dy = Lf(x).  (*)

The LHS here is differentiable; therefore the RHS is also, and so is f.  So

  xf(x) + S(x,1)f(y)dy + x(-f(x)) = Lf'(x), or

  S(x,1)f(y)dy = Lf'(x).  (**)

Also, (*) gives us (loosely speaking) that f(0)=0; more precisely, if
lim(x->0)f(x) exists, it is 0.

Again, the LHS of (**) is differentiable, so f' is, and we get

  -f(x) = Lf''(x)  (***)

and also, from (**) we get (loosely speaking as before) that f'(1)=0.

Now (***) is (all in chorus) a Linear Homogeneous Differential Equation of the
Second Degree, and so its solutions are a space of dimension 2 spanned by any
two convenient linearly independent solutions.  For my purposes it is most
convenient to write that we know

  f(x) = k1 sin(x/sqrt(L)) + k2 cos(x/sqrt(L))

f is well-behaved, so from "f(0)=0" (loosely speaking) we get k2=0.  Similarly,
from "f(1)=0" (loosely speaking) we get (since k1 /= 0) that sin(1/sqrt(L))=0,
which implies 1/sqrt(L) = pi*n for n an integer > 0.

Putting it all together, we get that we must have L = 1/sqr(pi*n) for n a
positive integer; and f(x) = k sin(x/sqrt(L)) = k sin(n*pi*x) for k /= 0.
1970.4Answer(??) to #5FLOYD::YODERMFYThu Apr 27 1995 18:1218
I think the problem as stated is wrong.  I wish to show that we can arrange
(with suitable h) that
             n
  t(n) = (-1) (n+1), so that t(n) does not approach a limit.

                              n+1
This happens if h(t(n)) = (-1)   (n+1)(2n+3), which is easy to arrange since
the t(n) are distinct.  We have
                             n            n+1             n+1
  t(n) + h(t(n))/(1+n) = (-1) (n+1) + (-1)   (2n+3) = (-1)   (n+2) = t(n+1).

It is easy to see that h is strictly decreasing for the defined values (by
considering odd and even n separately), and so we can linearly interpolate to
define h everywhere and satisfy the initial requirements.  (Or, we can define
h(0)=0 and then linearly interpolate.)

Is there a missing condition in the problem statement?  Or can someone find an
error in what I've written?
1970.5POLAR::WALSHMThu Apr 27 1995 18:308
    Re .4:
    
    I've checked what I typed in with the original contest sheet, and
    they're the same.
    
    Can you prove your h function to be bounded?
    
    Matt
1970.6My errorFLOYD::YODERMFYThu Apr 27 1995 19:171
Aargh!  No, my h isn't bounded.  I overlooked that condition, or forgot it.
1970.7This time for sure... (answer to #5)FLOYD::YODERMFYThu Apr 27 1995 20:0325
WLOG t*=0; this will simplify terminology.  Since h is strictly decreasing, h(t)
is positive for t<0 and negative for t>0.

If any t(n)=0, then t(N)=0 for all N>n, and the limit holds.  So assume all
t(n)/=0. If there are infinitely many positive t(n), we can show that for any
e>0, there is some point N beyond which t(n) > -e for n>N.  This is by
induction: choose N so that (1) A/N < e where A is an upper bound on abs(h), and
(2) t(N)>0.  Then by induction t(n)>-e for all n>N (t(n)<0 implies t(n+1)>t(n);
t(n)>0 implies t(n+1) > -A/N > -e).

So, if there are both infinitely many positive t(n) and infinitely many negative
t(n), it is easy to see that lim(t(n))=0.  So assume that, for some point on,
all t(n) are negative (the other case is argued similarly).

We must have, from that point on, that t(n) is strictly increasing.  Since the
t(n) are negative, they must approach a limit L<=0.  Suppose this limit is <0;
let h(L)=M.  Then M>0, since h is decreasing.  But

  t(n+1)-t(n) = h(t(n))/(n+1) >= h(L)/(n+1); summing this for n in 1..k-1,
  t(n+k)-t(n) >= h(L)(H(n+k) - H(n)) where H(n) is the harmonic series.

Thus t(n+k)-t(n) diverges (for fixed n and increasing k), which is a
contradiction: it must approach L-t(n).

So in any case t(n)->0 QED.
1970.8Conjecture for #3, and suggested approachFLOYD::YODERMFYFri Apr 28 1995 13:4933
I'm not going to have time to work on these for perhaps another week, so I
thought I'd offer what I have now.  I believe the answer is

            ___        [n/p]
  D(n) = n! | | (1-1/p)

where [] is the floor function, and the product is over all primes.  (The
product can be infinite because the terms are 1 for p>n.)

This holds for n=1, and so will hold by induction if

                  ___
  D(n)/D(n-1) = n | | (1-1/p)
                  p|n

since [n/p] differs from [(n-1)/p], by 1, iff p|n.

I know that this ratio holds when n is a power of a prime.  I believe you can
prove it in general as follows: consider what happens to the matrix if you add
and subtract rows from the last row.  In particular, for each prime p|n,
subtract row n/p from row n; then for each pair of distinct primes p,q dividing
n, add row n/pq; subtract rows of the form n/pqr, etc., until you add (-1)^k
times row n/p1...pk where p1...pk are all primes dividing n.  I believe that you
can use the principle of inclusion and exclusion to prove that the result of
this will be a row with all zeros except for the last element, which will be
exactly the value indicated above for D(n)/D(n-1).  This will demonstrate the
result.

If someone wishes to fill in the details to make the above work (or demonstrate
that it doesn't), I would appreciate it.  I suspect that there may be a simpler
and more elegant way to derive the result, however, and I hope someone can think
of one.  If the problem is still unfinished by the middle of next week or so
I'll try to mop up myself.
1970.9Conclusion of #3FLOYD::YODERMFYFri Apr 28 1995 16:3821
Aha!  I realized during lunch that I don't need any fancy machinery to get the
result I want.  After subtracting all the rows as described in .8, the entry in
column m is the sum over all sets S of primes dividing n of

      |S|
  (-1)   gcd(m,n/P(S))  where P(S) is the product of S's elements.

If m<n, there is some prime q dividing n for which the power of q that divides m
is less than that dividing n (the power might be zero).  For this q, if S is a
set not containing q, the terms in the above sum which correspond to S and to
S+{q} are equal in magnitude but opposite in sign (the gcds are identical); so
the entire sum cancels.  This shows that all entries other than the last become
0.

If m=n, the gcds are equal to n/P(S), and it is easy to see that the sum equals

    ___
  n | | (1-1/p)
    p|n

which gives the desired result.