home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / math / 13290 < prev    next >
Encoding:
Internet Message Format  |  1992-10-15  |  2.6 KB
  1. Path: sparky!uunet!ogicse!uwm.edu!linac!att!princeton!fish.Princeton.EDU!lhjensen
  2. From: lhjensen@fish.Princeton.EDU (Leif Jensen)
  3. Newsgroups: sci.math
  4. Subject: Re: Another chocolate fish problem.
  5. Message-ID: <1992Oct16.053009.24883@Princeton.EDU>
  6. Date: 16 Oct 92 05:30:09 GMT
  7. Article-I.D.: Princeto.1992Oct16.053009.24883
  8. References: <Bw3E8p.FEn@cantua.canterbury.ac.nz>
  9. Sender: news@Princeton.EDU (USENET News System)
  10. Organization: Princeton University
  11. Lines: 52
  12. Originator: news@nimaster
  13. Nntp-Posting-Host: fish.princeton.edu
  14.  
  15. OK, since my last proof was so popular, here is another.  First a rehash
  16. of the problem.
  17.  
  18. u(n) is the number of distinct ordered partitions of a set of n elements
  19. into sets of one or two elements. v(n) is the number of distinct ordered
  20. partitions of a set of n elements into sets of two elements or more.
  21. Prove that u(n) = v(n+2) for integers n >= 1.
  22.  
  23. We denote ordered partitions by a sequence of integers abcd... in which
  24. the first digit represents the order of the first set of the partition,
  25. the second the order of the second set of the partition, etc.
  26.  
  27. We define an algorithm to convert ordered partitions of n into ordered
  28. partitions of n+2 and an algorithm to convert the other way.  Each
  29. builds up a partition by saying "output x".  These xi's are to be collected
  30. and when set in order x1x2x3... represent the resulting partition.
  31.  
  32. Algorithm 1: operates on ordered partitions into sets of 1 or 2.
  33.  
  34. 1) Remove the leftmost group of n 1's followed by a 2 from the input
  35. partition and output n+2.
  36. 2) Goto 1.
  37. 3) At this point only n 1's remain in the input.  Output n+2.
  38.  
  39. It is easy to see that this algorithm maps every ordered partition of n
  40. into sets of 1 or 2 to a unique ordered partition of n+2 into sets of
  41. 2 or more.  Thus we have u(n) <= v(n+2).
  42.  
  43. Algorithm 2: operates on ordered partitions into sets of 2 or more.
  44.  
  45. 1) If the input partition has only one element n, repeatedly output 1
  46. (n-2) times and stop execution of the algorithm.
  47. 2) Remove the leftmost element n from the input partition, then
  48. repeatedly output 1 (n-2) times, and then output 2
  49. 3) Goto 1
  50.  
  51. It is easy to see that this algorithm maps every ordered partition of n
  52. into sets of 2 or more to a unique ordered partition of n-2 into sets of
  53. 1 or 2.  Thus we have v(n) <= u(n-2)
  54.  
  55. We can now conclude that u(n) = v(n+2) for all n >= 1.
  56.  
  57. OK, so which proof do you prefer?  Are they both correct? This second
  58. one gives absolutely no insight into the problem.  Is that good or
  59. bad?  Do you like defining algorithms as here in proof 2 to solve
  60. math problems or does it remind you too much of Computer Science?
  61.  
  62. All comments are welcome.
  63.  
  64. --
  65. Leif Jensen
  66. lhjensen@phoenix.princeton.edu
  67.