Conference rusure::math

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.

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.

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.

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?

    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

Aargh!  No, my h isn't bounded.  I overlooked that condition, or forgot it.

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.

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.

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.