home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / math / 13163 < prev    next >
Encoding:
Text File  |  1992-10-14  |  1.9 KB  |  57 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!darwin.sura.net!jvnc.net!princeton!fish.Princeton.EDU!lhjensen
  3. From: lhjensen@fish.Princeton.EDU (Leif Jensen)
  4. Subject: Re: Another chocolate fish problem.
  5. Message-ID: <1992Oct14.111439.17556@Princeton.EDU>
  6. Originator: news@nimaster
  7. Sender: news@Princeton.EDU (USENET News System)
  8. Nntp-Posting-Host: fish.princeton.edu
  9. Organization: Princeton University
  10. References: <Bw3E8p.FEn@cantua.canterbury.ac.nz>
  11. Date: Wed, 14 Oct 1992 11:14:39 GMT
  12. Lines: 43
  13.  
  14. The notation below should be obvious after the statement of the problem
  15. has been read. 
  16.  
  17. If a and b are ordered partitions of n and m, respectively, then ab
  18. denotes the ordered partition of n+m in the obvious way.
  19.  
  20. fu(n) and fv(n) are sets of ordered partitions of n defined below.
  21. o(S) is the order of the set S, often |S|.
  22.  
  23. fu(1) = { 1 }
  24. fu(2) = { 11, 2 }
  25. fu(n) = { 2x for x in fu(n-2) } union { 1x for x in fu(n-1) }
  26.  
  27. It is clear that the two sets in the third line are disjoint.  It is
  28. equally clear that all possible ordered partitions of n into sets of 1
  29. or 2 are in fu(n) since any partition begins with a 1 or a 2 and all
  30. possible ordered partitions of n-1 into sets of 1 or 2 are in fu(n-1)
  31. and fu(n-2).  (Forgive this reverse induction proof.)
  32.  
  33. We notice that u(n) = o(fu(n)) and further that
  34.  
  35. u(n) = o(fu(n)) = o(fu(n-1) union fu(n-2)) = u(n-1) + u(n-2).
  36.  
  37. Define x+ of a partition x = abcd...,  for a,b,c,d... integers > 1,
  38. as (a+1)bcd...
  39.  
  40. fv(2) = { 2 }
  41. fv(3) = { 3 }
  42. fv(n) = { x+ for x in fv(n-1) } union { 2x for x in fv(n-2) }
  43.  
  44. It is clear that the two sets in the third line are disjoint.  It is
  45. equally clear that all possible ordered partitions of n into sets of 2 or
  46. more are in fv(n) using an argument similar to the one used above.
  47.  
  48. We notice that v(n) = o(fv(n)) and further that
  49.  
  50. v(n) = o(fv(n)) = o(fv(n-1) union fv(n-2)) = v(n-1) + v(n-2)
  51.  
  52. Since u(1) = v(3) and u(2) = v(4) we have u(n) = v(n+2) for n >= 1.
  53.  
  54. --
  55. Leif Jensen
  56. lhjensen@phoenix.princeton.edu
  57.