home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / math / research / 656 < prev    next >
Encoding:
Internet Message Format  |  1993-01-24  |  2.1 KB
  1. Path: sparky!uunet!portal!lll-winken!uwm.edu!cs.utexas.edu!zaphod.mps.ohio-state.edu!moe.ksu.ksu.edu!ux1.cso.uiuc.edu!news.cso.uiuc.edu!dan
  2. From: rinkus@park.bu.edu (Gerard J. Rinkus)
  3. Newsgroups: sci.math.research
  4. Subject: combinatorics or coding theory question
  5. Message-ID: <RINKUS.93Jan24142753@park.bu.edu>
  6. Date: 24 Jan 93 19:27:53 GMT
  7. Sender: Daniel Grayson <dan@math.uiuc.edu>
  8. Organization: Boston University Center for Adaptive Systems
  9. Lines: 47
  10. Approved: Daniel Grayson <dan@math.uiuc.edu>
  11. Originator: dan@symcom.math.uiuc.edu
  12. X-Submissions-To: sci-math-research@uiuc.edu
  13. X-Administrivia-To: sci-math-research-request@uiuc.edu
  14.  
  15.  
  16.  
  17.  
  18. Hi,
  19.  
  20. I have a combinatorics question that I have been unable to solve.
  21. I have asked a number of mathematics professors, and otherwise
  22. mathematically sophisticated people as well and no one has
  23. been able to show me the general solution to the following
  24. problem.  This question arose to me in connection with a 
  25. neural net model of spatio-temporal memory that I'm working on.
  26.  
  27. Suppose you have N groups of cells.  Each group contains K cells.
  28. Now suppose you make choices consisting of one cell chosen from
  29. each of the N groups.  Let each such choice be called a vector.
  30. Clearly there are K^N unique vectors.
  31.  
  32. My question is:  what is the largest set of vectors you can pick
  33. such that no two of the vectors overlap (i.e. have the same cell)
  34. at more than Q of the groups (where Q < N)?
  35.  
  36. The answer for the special case of Q = N-1 is K^N.  This follows
  37. immediately from the fact that if there are K^N unique vectors
  38. then each vector must be different from any other vector in at
  39. least one group (and therefore no two vectors (in the entire space
  40. of K^N vectors) can overlap at more than N-1 groups).
  41.  
  42. I've also found for various small special case, that the answer is
  43. K^(Q+1).  
  44.  
  45. But I haven't been able to figure out the general solution, or
  46. prove that it is K^(Q+1) if in fact it is.
  47.  
  48. Thanks in advance for any help on this.
  49.  
  50. Rod Rinkus
  51. Dept. of Cognitive and Neural Systems
  52. Boston University
  53. Boston, MA 02215
  54. email: rinkus@park.bu.edu
  55.  
  56.  
  57. --
  58. Gerard J. Rinkus
  59. Dept. of Cognitive and Neural Systems
  60. Boston Univ.
  61. rinkus@cns.bu.edu
  62.