home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 17113 < prev    next >
Encoding:
Internet Message Format  |  1992-12-18  |  1.4 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!saimiri.primate.wisc.edu!ames!agate!biosci!parc!xerox!feuerman
  2. From: feuerman@parc.xerox.com (Ken Feuerman)
  3. Newsgroups: sci.math
  4. Subject: Re: Interesting Discrete Math Question
  5. Message-ID: <1992Dec17.205217.2719@parc.xerox.com>
  6. Date: 17 Dec 92 20:52:17 GMT
  7. References: <3548@carroll1.cc.edu> <BzDIzv.5px@cantua.canterbury.ac.nz>
  8. Sender: news@parc.xerox.com
  9. Organization: Xerox PARC
  10. Lines: 35
  11.  
  12. [munch...]
  13. > Here is the proof. (Pigeonhole principle).
  14. > ~~~~~~~~~~~~~~~~~
  15. > Partition the integers into 51 subsets:
  16. > 
  17. > {1,4}   {2,5}   {3,6}
  18. > {7,10}  {8,11}  {9,12}
  19. > .....
  20. > {91,94} {92,95} {93,96}
  21. > {97,100}
  22. > {98}
  23. > {99}
  24. > 
  25. > Now when 52 numbers are drawn, at least 2 must come from one subset, and thus
  26. > be 3 apart.
  27. [more munch...]
  28.  
  29. This is all well and fine, except, how do you know you've found the best partition
  30. of those integers?  That is, how do you know there isn't some other partition Q = 
  31. {q_1, q_2, ... q_n} of the numbers 1-100 such that
  32.  
  33. (i) for all i, j, and for all a in q_i, b in q_j, |a - b| != 3; and
  34. (ii) n > 51?
  35.  
  36. I bring this up since someone else answered 51, having found a way to choose 50
  37. elements before guaranteeing that two would be 3 apart.  At first blush that
  38. seemed plausible, until others got a little more clever.  Is
  39.  
  40. 1 2 3, 7 8 9, ....., 97 98 99
  41.  
  42. as clever as we need to be?
  43.  
  44. For the record, I believe so (QED :-)).
  45.  
  46. --Ken.
  47.