Conference rusure::math

    Guaranteed 2*(N-1):
    	One spy acts as a router.  He meets with each of the others
    and collects all the packets.  He meets with them each again, handing
    out the packets.
    
    Expected 3*(N-1)/2:
    	Assuming the order of meeting is independent of the destinations.
    Same as above, except if the router happens to have aa packet for
    a spy when they meet for the first time, he delivers it and saves
    the second meeting.  It seems, though I haven't proved it, that
    on average, this should save half the second meetings.
    
    				Jeff
    

>    Guaranteed 2*(N-1):
>    	One spy acts as a router.  He meets with each of the others
>    and collects all the packets.  He meets with them each again, handing
>    out the packets.

    Nice.  Can do better.
    
    John

>    Expected 3*(N-1)/2:
>    	Assuming the order of meeting is independent of the destinations.
>    Same as above, except if the router happens to have aa packet for
>    a spy when they meet for the first time, he delivers it and saves
>    the second meeting.  It seems, though I haven't proved it, that
>    on average, this should save half the second meetings.
    
    I meant to set up a system of meetings which would work for any
    number of packets, including the case of every-spy-to-every-other-spy.
    
    So I don't think that your saving will exist.
    
    John

    Take my first solution, the one where one spy collects all the packets,
    and hands them out again.  He meets with each of the N-1 other spies,
    and collects their packets.  He then meets with each of them again,
    handing out the packets, for a total of 2*(N-1) meetings.
    
    One meeting can be optimized out.  The master spy can combine the
    last collection meeting with the first handing-out meeting, by
    collecting the last set of packets, and immediately giving that
    spy all the packets that are addressed to him.  This gives 2*(N-1)-1,
    or 2*N-3, instead of 2*N-2.
    
    				Jeff
    

    2*N - 3 can be improved.
    
    John

    Is it true that the spies _don't_ know who the envelopes are for
    until they meet?  Or would I (a spy) know that the guy in the Green
    Fedora has the envelope for me?  Or doesn't it matter?
    
      John

    John:
    
    I don't think it matters.  They do have to know enough to be able
    to do things like Jeff's ideas.  For example, with five spies and
    seven meetings -- AB,AC,AD,AE,AB,AC,AD -- if C has a packet for
    B, then he has to give it to A at their first meeting.
    
    John

    I asked John for a hint.  He sent back the following 4-meeting
    solution for N=4.

		AB, CD, AC, BD

    He also mentioned that he originally saw the problem for N=5.

    Let M(N) be the maximum number of meetings needed for N spies to
    end up with correct packets.  Clearly M(2) = 1.

    Suppose each spy has a number from 1..N
    
    On Boston Common, whoever has an envelope for Spy #1 goes to the
    Richard Nixon memorial and waits.  Spy #1 shows up and they exchange
    envelopes.  Spy #1 then vanishes into the shadows, never to be seen again.
    
    We now have had 1 meeting and are left with N-1 spy/envelope pairs.
    Thus, M(N-1) = M(N) + 1
    
    Proceeding inductively, we can continue with spy #2 meeting with
    whoever has a packet for spy #2, etc., until spies N-1 and N are left.
    
    Hence M(N) = N - 1
    
      John

    But that's a nice answer to a different problem!  In .0, the assumption
    is that each spy may have several envelopes -- possibly one for each of
    the other spies.

    Thank you for stating the problem more clearly.
    
      John

    Anyone familiar with sorting networks (c.f., Knuth's Volume 3)
    will recognize the problem.

    Re .1:
    
    Peter:
    
    We have 2*N-4 (.8).  Can that be beaten?
    
    John

    There is another possible strategy, which I divined from Gilbert's
    hint.  
    
    Divide the spies into two nearly equal groups.
    Each group gives its packets that belong to the other group to a
    member of the other group.  This can be done by having each member
    of the larger group meet with a member of the smaller group and
    exchange packets.  If all spies are involved in this, then we will
    have two separate groups of spies.  Now solve the problem for the
    two smaller groups.
    
    The swap phase takes [n/2] meetings, where [x] is ceiling(x).
    Therefore, 
    MEETINGS(n) = [n/2] + MEETINGS([n/2]) + MEETINGS(n - [n/2])
    
    If MEETINGS(1) = 0, and MEETINGS(2) = 1, the following table from
    this strategy can be derived:
    
    		n	MEETINGS(n)
    
    		1	0
    		2	1
    		3	3
    		4	4
    		5	7
    		6	9
    		.	.
    		.	.
    		.	.
    
    Up to n=5, I think this is optimal.  I haven't found any way of
    doing 5 in less than 7 meetings.
    
    Up to n=10, MEETINGS(n) differs from 2*N-3 only at 4 and 8, where
    it is 2*N-4.  After n=10, it is larger than 2*N-3.
    
    So, as far as I can tell, the optimal answer is min(MEETINGS(n),2*N-3).
    That's mighty gross and I hope it isn't so.  Can anyone provide
    a counterexample?? (Please??)
    
    				Jeff
    

    Four spies:  Meetings(4) = AB, CD, AC, BD
    Five spies:  Meetings(5) = EA, Meetings(4), EA
    Six spies:   Meetings(6) = FA, Meetings(5), FA
    	etc.
    
    John

    1) Can it be proven that 2*N-4 is optimal?
    
    2) What is the solution for the same problem when groups of M spies
    	are allowed to meet and swap packets?
    
    				Jeff
    

Newsgroups: rec.puzzles,sci.math
Path: decwrl!hplabs!hp-sdd!ncr-sd!ncrcae!ece-csc!uvacs!dsr
Subject: Number of 'phone calls (A well-solved problem)
Posted: 28 Sep 87 18:09:25 GMT
Organization: U.Va. CS dept.  Charlottesville, VA
Xref: decwrl rec.puzzles:591 sci.math:2130
 
This is known as the Gossip Problem, and it made the rounds about 18 years ago.
 
It is has long been known that 2n-4 calls are necessary and sufficient (n>3).
 
It is also well-solved for the (limited) conference call case.
 
If the calls are limited to pairs connected by an edge of an undirected graph,
then, if the graph is connected, 2n-3 are always enough.
To do it in 2n-4 calls it is necessary and sufficient that a 4-cycle exits.
 
There are many papers on gossiping; perhaps the best is:
  Kleitman & Shearer, Disc. Math. 30(1980)151-156.
 
dana