Conference rusure::math

>    (1) Prove that for sufficiently large n there is one and only one series
>        of positive integers a1,a2,...,an in which ai is equal to the number of
>        values of r such that ar = i.

    A//:

    Please explain this further.  It seems that there are multiple such
    series, e.g.:
    
    	1,2,2,3,3,4,4,4,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8,9,...
    
    or
    
    	2,1,1,3,4,4,4,5,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8,8,9,...
    
    I don't understand the importance of "sufficiently large n".
    
    John

    n is finite. Sorry, I thought I had made this clear by the notation
    a1,a2,...,an    as opposed to    a1,a2,...
    
    More formally: prove there exists a positive integer N such that
    for each integer n > N there exists one and only one sequence of
    n integers a1,a2,...,an in which each ai is equal to the number
    of values of r such that ar = i.
    
    Hope that clarifies it.
    
    A//

					I

>    (1) Prove that for sufficiently large n there is one and only one series
>        of positive integers a1,a2,...,an in which ai is equal to the number of
>        values of r such that ar = i.

					II

>    n is finite. Sorry, I thought I had made this clear by the notation
>    a1,a2,...,an    as opposed to    a1,a2,...
>    
>    More formally: prove there exists a positive integer N such that
>    for each integer n > N there exists one and only one sequence of
>    n integers a1,a2,...,an in which each ai is equal to the number
>    of values of r such that ar = i.
    
A//:

More help, please.  Are the {ai} positive, as in (I)?  Or nonnegative?  If
nonnegative, I can't get anything but {1,0,0,0,...,0}:

	Given {a1,a2,a3,...,an}, there are

		a1 of the {ai} with value 1
		a2 of the {ai} with value 2
		a3 of the {ai} with value 3
		.
		.
		an of the {ai} with value n

	and a total of (a1+a2+a3+...+an) nonzero ai's.

	So (# of nonzero ai's) = sum [i = 1 to n] of (ai)
			       = sum [i such that ai > 0] of (ai)

	But (# of nonzero ai's) = sum [i such that ai > 0] of (1)

	And then, by subtracting,

		sum [i such that ai > 0] of (ai - 1) = 0

	And then all {ai} are either 1 or 0

	Then, by definition, ai = 0 for i > 1

John

>    (4) Let Q be a string of 0's and 1's. Define Q1 to be the string of 0's
>        and 1's formed by taking the differences (mod 2) of successive terms of
>        Q; Q2 = (Q1)1; etc.
>
>        [eg Q  = 11100101010011
>            Q1 = 0010111111010
>            Q2 = 011100000111
> 	     Q3 = 10010000100
> 	     etc.]
>
>        For which infinite, periodic strings Q will we have Qn = ...0000...
>        (an infinite string of zeros) for some n?

    Don't know, but here's one that doesn't work:
    
    	Q0 = ... 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 ...
	Q1 =  ... 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 ...
    	Q2 =   ... 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 ... = Q0
    
    John    

>    (4) Let Q be a string of 0's and 1's. Define Q1 to be the string of 0's
>        and 1's formed by taking the differences (mod 2) of successive terms of
>        Q; Q2 = (Q1)1; etc.
>        For which infinite, periodic strings Q will we have Qn = ...0000...
>        (an infinite string of zeros) for some n?

    Let Q[i,j] be the j-th character in the i-th string.

    Now Q[i+1,j] = Q[i,j] @ Q[i,j+1], where the '@' is addition mod 2.

    We prove that Q[i+2^m,j] = Q[i,j] @ Q[i,j+2^m] by induction on m.
    It's true for m=0.  Assume it's true for m.  Then

	Q[i+2^(m+1),j] = Q[(i+2^m)+2^m,j]
		= Q[(i+2^m),j] @ Q[(i+2^m),j+2^m]
		= Q[i,j] @ Q[i,j+2^m] @ Q[i,j+2^m] @ Q[i,j+2^m+2^m]
		= Q[i,j] @ Q[i,j+2^(m+1)].

    Suppose Q[n] = 0...0000....  This can be true iff Q[n-2^m] was a periodic
    string, having a period of 2^m.  For which infinite, periodic strings will
    we have Qn = ...0000...?  Those with period 2^m.

Re .3: Well done John, an excellent solution to the problem as stated.
       Pretty boring, though. What I *meant* to say was a0,a1,...,an .
       The values of the ai are, as you suggested, non-negative.

       Sorry about that ...

Re .5: Neat work.

A//

     So we can use (for n = 2)
     
           a0 a1 a2
     
            2  1  2
     
     There are a1 = 1 one's and a2 = 2 two's, and we don't
     care that a0 is not the number of zero's.
     
     Dan

re .-1
	Well, it's not my problem, but I'd like a0 = the number of zeroes.

	Here's an example:

	a0 a1 a2 a3 a4 a5 a6 a7 a8
	 5  2  1  0  0  1  0  0  0

     Re .-2, .-1:
     
     Yes, your version is much better.  I was still thinking
     "positive" instead of "non-negative" [digression: is
     there or isn't there a "-" in "non-negative"?] integers.

     And I thought it wouldn't work if a0 had to be the number of
     zero's, but your example may some day cause me to perhaps
     reconsider if that is indeed the case. :-)
     
     Dan 

(1) For n >= 6, the following general solution exists:

	a0 = (n-3)
	a1 = 2
	a2 = 1
	a(n-3) = 1
	otherwise ai = 0

Now for uniqueness:

Let I(X) be the indicator function: 1 if X is true, 0 if X is false.
All sums are from 0 to n.

	ai = sumj(I(aj=i))

=>	sumi(f(i)*ai) = sumi(f(i)*sumj(I(aj=i)))
		      =	sumj(sumi(f(i)*I(aj=i)))
		      = sumj(f(aj)).

and we can choose any f(i).

f(i) = 1 yields:
	sumi(ai) = n+1
[ f(i) = i would yield:
	sumi(i*ai) = sumj(aj) = n+1]

The easiest way to see the answer is to set ao = x.   Then there are x values of
i such that ai = 0.   That leaves n-x values of i such that ai > 0, and these
values must sum to n-x+1.   i.e. one of them is 2, all the others are 1.

Thus in some order, the ai are x,0(x times),1(n-x-1 times),2.
Possibilities:
x=0: contradictory
x=1: (& n=3, see below)
x=2: (& n=3 or 4, see below)
Or x > 2, and n-x-1=2 (i.e x=n-3, yielding the general solution above).

In practice, iteration is a good way to find solutions to this kind of problem:
just start with some random bi(t) and set bi(t+1) = sumj(I(bj(t)=i)).   But
one needs some kind of structural insight to talk about uniqueness.

To finish off, what are the solutions when n < 6?

n=0: none.
n=1: none.
n=2: none.
n=3:  2 0 2 0
      1 2 1 0
n=4:  2 1 2 0 0
n=5: none. 

(4) Gilbert's already put that one to bed, I see, but I want to put in a 
comment or two:

Sequence length power of two:

Necessary, because the parent of any string will either have the same period
or double the period, and string with odd prime factor of the period cannot
therefore evolve to period 1.

Sufficient, because the image of any bit in a string spreads into its
descendents in a binomial manner (like Pascal's triangle).   In the 2^m-th
generation, mod 2, only the two extremal bits are 1. (Prove it). If the length
of the period is 2^m, then these two bits have *just* met "on the far side", 
and cancel out.   All bits do this, so the result's zero.

In a way as interesting as the powers of two, are the other sequences, the ones
which don't collapse.   Another puzzle:

*******************************************************************************
*                                                                             *
*		What are the stable strings?				      *
*									      *
*   i.e. the strings that under the transformation we've been discussing      *
*   remain 'unchanged'.   (Rotated, or reversed)                                                         *
*									      *
*   e.g. 0 -> 0,    110 -> 110						      *
*									      *
*******************************************************************************

I think I've solved it.

Build a binary tree from the ingredients:

	a		b		c
        |	        |	        |
     c--+--b	     c--+--a	     a--+--b

and starting with root = c:

                              		c
                                        |
                        a---------------+---------------b
                        |                               |
                c-------+-------b               c-------+-------a
                |               |               |               |
            a---+---b       c---+---a       a---+---b       c---+---b
	    |       |       |       |       |       |       |       |
	  c-+-b   c-+-a   a-+-b   c-+-b   c-+-b   c-+-a   a-+-b   c-+-a
          |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
	                                .
                                        .
                                        .

Read from the tree like a book (top line L-to-R, second line, etc.), skipping
the root node:

	abcbcaabcaabcbcbcaabcbcbcaabca...

Convert a's into 1's and bc's into 2's:

	12211211222112221121...

Those are the S1 differences.

John