16. Dec. 1992, Bielefeld
Discrete Optimization:

  Find Polynomials

             n
            ---
            \           i       n-i
   P  (x) =  >     a   x   (1-x)      
    n       /       i 
            ---
            i=0

   with integer coefficients 0 <= a  <= Binomial[n,i]
                                   i

   such that P_n(x) is not the identity and has as many as
   possible fixpoints in closed interval [0,1].


   For n = 1..5 you can get n different fixpoints in the interval [0,1].
      p_1 :  [1,0] = [a0, a1]
      p_2 :  [0,0,1] = [a0, a1, a2]
      p_3 :  [0,3,0,1]
      p_4 :  [0,0,6,2,1]
      p_5 :  [0,2,0,10,3,1]

   The case n=6 is the first time, where you can get only n-1 different
   fixpoints in [0,1].

   For n=20 I managed to get 17 fixpoints. Can you beat this? 
   What are optimalization procedures in this case?
   (Simulated Annealing with the neightbourhood 'change one coefficient
   a little bit' is no good idea, as almost all fixpoints will be
   complex typically.)

   You can construct polynomials with 0.2*n fixpoints. Can you find
   a better lower bound?

This was a exercise in a 2nd year math course. We recieved one 
solution. Three students constructed (4 pages) a polynomial with
fix points at k/(n-1). Then they showed that the coefficients
are integers and in the allowed range. So they constructed
at least n different fixpoints. But they missed that they had
found the identity. They started their induction for n=3. 

Torsten Sillke
             
-------------------------------------------------------------------------
When is P_n the identity?

             n
            ---
            \           i       n-i
   P  (x) =  >     a   x   (1-x)      =  x
    n       /       n,i 
            ---
            i=0

             n
            ---
            \                   i                 n
             >     a   (x/(1-x))      =  x / (1-x)
            /       n,i 
            ---
            i=0

   substitute z = x/(1-x) which is x = z/(1+z)

             n
            ---
            \           i               n-1
             >     a   z      =  z (z+1)
            /       n,i 
            ---
            i=0

   this gives you:

     a    = Binomial[ n-1, i-1 ]
      n,i

     in particular a    = 0
                    n,0


-------------------------------------------------------------------------
It is equivalent:

A) the number of different Fixpoint in [0,1] of the polynomial:

             n
            ---
            \           i       n-i
   P  (x) =  >     p   x   (1-x)      
    n       /       n,i
            ---
            i=0

   with integer coefficients: 0 <= p    <= Binomial[n,i]
                                    n,i

B) the number of different positive zeroes (0 <= z <= +inf) of the polynomial:

             n
            ---
            \           i
   Q  (z) =  >     q   z 
    n       /       n,i
            ---
            i=0

   (if q(n,n)=0 you count a zero at +inf.)

   with integer coefficients: -Binomial[n-1,i-1] <= q    <= Binomial[n-1,i]
                                                     n,i

The transformation is:

   p    = q    + Binomial[n-1,i-1]
    n,i    n,i

   and the roots z transform to the fixpoints x as:

   x = z/(z+1).


Example: n=20

R20(x) = ((x-1)(x-2)(2x-1)(x^4-8x^3+15x^2-8x+1)
             (x x-3x+1)(x x-4x +1)(x^4-7x^3+13x^2-7x+1))

Q20(x) = x x (x+1) R20(x)

---------------------------------------------------------------
Torsten Sillke