home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 17054 < prev    next >
Encoding:
Text File  |  1992-12-16  |  2.0 KB  |  59 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!spool.mu.edu!yale.edu!ira.uka.de!math.fu-berlin.de!unidui!rrz.uni-koeln.de!Germany.EU.net!news.uni-bielefeld.de!math25!sillke
  3. From: sillke@math25.mathematik.uni-bielefeld.de (Torsten Sillke)
  4. Subject: discrete optimization (fixpoints of polynomials)
  5. Sender: news@hermes.hrz.uni-bielefeld.de (News Administrator)
  6. Message-ID: <BzDDqo.568@hermes.hrz.uni-bielefeld.de>
  7. Date: Wed, 16 Dec 1992 20:47:12 GMT
  8. Nntp-Posting-Host: math25.mathematik.uni-bielefeld.de
  9. Organization: Math MadHouse Bielefeld, Germany
  10. Keywords: discrete optimization, polynomial fixpoints
  11. Lines: 46
  12.  
  13. Discrete Optimization:
  14.  
  15.   Find Polynomials
  16.  
  17.              n
  18.             ---
  19.             \           i       n-i
  20.    P  (x) =  >     a   x   (1-x)      
  21.     n       /       i 
  22.             ---
  23.             i=0
  24.  
  25.    with integer coefficients 0 <= a  <= Binomial[n,i]
  26.                                    i
  27.  
  28.    such that P_n(x) is not the identity and has as many as
  29.    possible fixpoints in closed interval [0,1].
  30.  
  31.  
  32.    For n = 1..5 you can get n different fixpoints in the interval [0,1].
  33.       p_1 :  [1,0] = [a0, a1]
  34.       p_2 :  [0,0,1] = [a0, a1, a2]
  35.       p_3 :  [0,3,0,1]
  36.       p_4 :  [0,0,6,2,1]
  37.       p_5 :  [0,2,0,10,3,1]
  38.  
  39.    The case n=6 is the first time, where you can get only n-1 different
  40.    fixpoints in [0,1].
  41.  
  42.    For n=20 I managed to get 17 fixpoints. Can you beat this? 
  43.    What are optimalization procedures in this case?
  44.    (Simulated Annealing with the neightbourhood 'change one coefficient
  45.    a little bit' is no good idea, as almost all fixpoints will be
  46.    complex typically.)
  47.  
  48.    You can construct polynomials with 0.2*n fixpoints. Can you find
  49.    a better lower bound?
  50.  
  51. This was a exercise in a 2nd year math course. We recieved one 
  52. solution. Three students constructed (4 pages) a polynomial with
  53. fix points at k/(n-1). Then they showed that the coefficients
  54. are integers and in the allowed range. So they constructed
  55. at least n different fixpoints. But they missed that they had
  56. found the identity. They started their induction for n=3. 
  57.  
  58. Torsten Sillke
  59.