home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 17059 < prev    next >
Encoding:
Internet Message Format  |  1992-12-16  |  1.3 KB
  1. Path: sparky!uunet!cs.utexas.edu!wupost!waikato.ac.nz!canterbury.ac.nz!math!wft
  2. Newsgroups: sci.math
  3. Subject: Re: Interesting Discrete Math Question
  4. Message-ID: <BzDIzv.5px@cantua.canterbury.ac.nz>
  5. From: wft@math.canterbury.ac.nz (Bill Taylor)
  6. Date: Wed, 16 Dec 1992 22:40:42 GMT
  7. References: <3548@carroll1.cc.edu>
  8. Organization: Department of Mathematics, University of Canterbury
  9. Nntp-Posting-Host: sss330.canterbury.ac.nz
  10. Lines: 32
  11.  
  12. [Draw integers randomly from 1 to 100. We want to get a pair differing by 3.]
  13.  
  14. Several people have already observed that 51 draws is insufficent to
  15. guarantee a pair three apart.
  16.  
  17. e.g.   1 2 3, 7 8 9, 13 14 15, .....   91 92 93,  97 98 99  might be drawn.
  18.  
  19. It has not actually been proved that 52 draws is certain to give the desired
  20. result.
  21.  
  22. Here is the proof. (Pigeonhole principle).
  23. ~~~~~~~~~~~~~~~~~
  24. Partition the integers into 51 subsets:
  25.  
  26. {1,4}   {2,5}   {3,6}
  27. {7,10}  {8,11}  {9,12}
  28. .....
  29. {91,94} {92,95} {93,96}
  30. {97,100}
  31. {98}
  32. {99}
  33.  
  34. Now when 52 numbers are drawn, at least 2 must come from one subset, and thus
  35. be 3 apart.
  36.  
  37. --------------------------------------------
  38. Bill Taylor.       wft@math.canterbury.ac.nz 
  39. Bill Trylor. que  rwft@maih.casterkury.aa.n! 
  40. Tiel Tryloco quer rwst@maihuc sterkery.ga.n!
  41. Thelworyd co quer rwsi@mvihus strikesy.gain!
  42. The world conqueror sig-virus strikes again!
  43. --------------------------------------------
  44.