home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / rec / puzzles / 8085 < prev    next >
Encoding:
Internet Message Format  |  1992-12-22  |  2.1 KB
  1. Xref: sparky rec.puzzles:8085 sci.math:17283
  2. Path: sparky!uunet!pipex!bnr.co.uk!uknet!comlab.ox.ac.uk!oxuniv!peake
  3. From: peake@vax.oxford.ac.uk
  4. Newsgroups: rec.puzzles,sci.math
  5. Subject: Re: Circular graph problem
  6. Message-ID: <1992Dec21.172803.10940@vax.oxford.ac.uk>
  7. Date: 21 Dec 92 17:28:03 GMT
  8. References: <1992Dec16.113500.1157@client24.comlab.ox.ac.uk>
  9. Organization: Oxford University VAX 6620
  10. Lines: 42
  11.  
  12. In article <1992Dec16.113500.1157@client24.comlab.ox.ac.uk>, mnewman@comlab.ox.ac.uk (Matthew Newman) writes:
  13. > Consider circular graphs with N nodes, such that there is an integer
  14. > at each node. Consider those integers K such that for some graph G
  15. > each integer in [1..k] is the sum of integers at the nodes of some
  16. > connected sub-graph G. For example with N=4 I can get K=11 with the
  17. > following graph :     (1)--(2)
  18. >                        |    | 
  19. >                       (3)--(5) 
  20. > 
  21. > and I can do better than this and get the maximum possible k=13 like
  22. > this :     (1)--(2)    and like this:   (1)--(3)
  23. >             |    |                       |    |
  24. >            (4)--(6)                     (2)--(7)
  25. > 
  26. > and for N=8 I can get K=53 with 1-4-22-7-3-6-2-12- (where notationally
  27. > the above graphs are 1-2-5-3- ; 1-2-6-4- ; 1-3-2-7- i.e. read round
  28. > clockwise) which again is maximal.
  29. > 
  30. > The question is, what is the largest K I can get for a given N ?
  31.  
  32. Clearly, an upper bound for the best K is K= N^2-N+1, as that is the number
  33. of different sums you can get.  For example,
  34. N  |  Solution
  35. ---+-----------------
  36. 4  |  1,3,2,7
  37.    |  1,2,6,4
  38. 5  |  1,3,10,2,5
  39. 6  |  1,7,3,2,4,14
  40.    |  1,3,6,2,5,14
  41.    |  1,3,2,7,8,10
  42.    |  1,2,5,4,6,13
  43.    |  1,2,7,4,12,5
  44. 7  |  No solution for K=43
  45.  
  46. Someone solved this problem in the 1930s, but as I have forgotten the journal,
  47. author and year, that is not much help :-)  It was a friend of Paul Erdos,
  48. (Yep, it's name-dropping time, folks) not Erdos himself, who wrote it.  I 
  49. looked it up five years ago, and all I can remember is that 7 doesn't give
  50. you K=43 because 2*7+1 is the product of two different primes.  Or something.
  51.  
  52. Cheers,
  53. Michael
  54.