Go back to previous page
Forum URL: http://www.cut-the-knot.org/cgi-bin/dcforum/forumctk.cgi
Forum Name: This and that
Topic ID: 137
Message ID: 14
#14, RE: Exchanging information between n persons
Posted by R. Bumby (Guest) on Aug-22-01 at 03:47 PM
In response to message #8
Your method for trying to build big networks from small ones seems very complicated, which may have led to the bad count of 11 calls for 8 people that I saw in sci.math. It is better to lock in the easy steps: it is always possible to add one person and two calls to an existing network (the newcomer calls someone to start the process and is called back when the person he calls knows everything); 1 call suffices for 2 people (now you know that 2n-3 calls always work for n people); 4 calls work for 4 people (arrange in a square; make two horizontal calls; then two
vertical calls). The hard part is to show that there are no more
efficient schedules of calls. This is done by starting with a
sequence of calls that pools the information and using it to split the population into two subsets (with sizes determined by the sequence of calls). My paper appears as "A problem with telephones" in SIAM J. Alg. Disc. Meth. vol. 2, no. 1, March 1981, 13--18. My solution was obtained much earlier, but not published then because several others were published first and I didn't think I had anything to add. Then I learned that my approach was able to answer a related open question, which gave a new reason for publication.

From time to time, one sees new variations on this problem, and
extensive lists of references have been published. Unfortunately, I don't have any of them handy right now.