wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Journalist information exchange
        
(Message started by: Grimbal on Feb 2nd, 2005, 5:31am)
Title: Journalist information exchange
Post by Grimbal on Feb 2nd, 2005, 5:31am
Here is a problem I stole from www.puzzleup.com.

I entered the best solution I found and it seems to be the accepted as the right one.  I haven't been able to find a better solution (even with a non-exhaustive computer search) but I couldn't prove my solution to be optimal.
What troubles me is that the solution I found does not feel optimal.  My solution for 32 people works for 33 and there seem to be "unused bandwith" that could be put to work.

I'd like to know what you think.

---
There are 32 journalists working on the same project. Each journalist has at least one piece of information that is not known to the others. At the end of the project they plan to phone each other to bring together all the information that has been collected. These calls are conference calls which include three people. In each of the calls the three journalists pass on to each other all the information that they have learnt up to that moment. At least, how many conference calls are required so that all the information is obtained by all the journalists?
Title: Re: Journalist information exchange
Post by Barukh on Feb 3rd, 2005, 6:02am
Just to let it go…

In the aforementioned forum, only members can submit solutions. Is it also true that only members can view the solutions? So, I apologize if what I say is far from being optimal.

[smiley=square.gif][hide]
The idea I used is very simple: choose a candidate that will gather all the information as soon as possible (1st stage), and then distribute it among others (2nd stage). Overall, I’ve got 31 calls:

Stage 1: (1,2,3) (1,4,5) (1,6,7) … (1,30,31) (1,2,32) – 16 calls
Stage 2: (1,3,4) (1,5,6) … (1,31) – 15 calls
[/hide][smiley=square.gif]

:-/
Title: Re: Journalist information exchange
Post by towr on Feb 3rd, 2005, 8:15am
That's also the best I could come up with so far.
It must be possible to do better though, cause this seems to easy..

[e]Well, 30 is better.. So there..
Doubtfull that's optimal though[/e]
Title: Re: Journalist information exchange
Post by JocK on Feb 3rd, 2005, 2:12pm

on 02/03/05 at 08:15:03, towr wrote:
[e]Well, 30 is better.. So there..
Doubtfull that's optimal though[/e]


Why 30...? Is this the (assumed optimal) solution Grimbal obtained?



I would be tempted to conjecture that for N journalists, the number of conference calls required is at least N-3.

This lower bound is obtained when the number of journalists is a power of three. A few examples should clarify the strategy and also that there is basically no 'wastage' (or 'unused bandwith' as Grimbal calls it) in case the strategy is applied to a group of people numbering a power of three:

N=9
(1,2,3) (4,5,6) (7,8,9)
(1,4,7) (2,5,8) (3,6,9)
A total of 3 + 3 = 6 conference calls.

N=27
(1,2,3) (4,5,6) (7,8,9) .. (25,26,27)
(1,4,7) (10,13,16) (19,22,25)
(1,10,19) (4,13,22) (7,16,25)
(1,2,3) (4,5,6) (7,8,9) .. (25,26,27)
A total of 9 + 3  + 3 + 9 = 24 conference calls.

In general, for N=3k one obtains a total of 2(3k-1 + 3k-2 + .. + 3) = 3k-3 = N - 3 conference calls.
Title: Re: Journalist information exchange
Post by towr on Feb 3rd, 2005, 3:38pm

on 02/03/05 at 14:12:35, JocK wrote:
Why 30...? Is this the (assumed optimal) solution Grimbal obtained?
30 because that's a solution I found, and it's better than 31, which Barukh posted.
Title: Re: Journalist information exchange
Post by JocK on Feb 3rd, 2005, 3:49pm

on 02/03/05 at 15:38:14, towr wrote:
30 because that's a solution I found, and it's better than 31, which Barukh posted.


OK, but you said in reaction to Barukh's solution leading to 31 calls "That's also the best I could come up with so far"...  

If your solution is different, would you mind posting it here?
Title: Re: Journalist information exchange
Post by towr on Feb 4th, 2005, 12:54am

on 02/03/05 at 15:49:19, JocK wrote:
OK, but you said in reaction to Barukh's solution leading to 31 calls "That's also the best I could come up with so far"...  
And then I found a better solution and edited my post accordingly..
ah well..


Quote:
If your solution is different, would you mind posting it here?
As it works neatly for all n=4k with k>1 I'll do it for n=8 (because 32 is too much work :P)

(1,  2,3) -> 1,2,3 = 10000000 | 01000000 | 00100000 = 11100000  
(8,  6,7) -> 6,7,8 = 00000100 | 00000010 | 00000001 = 00000111
(1,  4,5) -> 1,4,5 = 11100000 | 00011000 = 11111000
(8,  4,5) -> 4,5,8 = 11111000 | 00000111 = 11111111
(1,  6,7) -> 1,6,7 = 11111000 | 00000111 = 11111111
(8,  2,3) -> 2,3,8 = 11100000 | 11111111 = 11111111
Title: Re: Journalist information exchange
Post by Barukh on Feb 4th, 2005, 5:16am
I still need to understand towr’s solution…  :-/

JocK, I’ve found your solution for power-of-3 very nice! I hope you won’t mind explaining here my understanding of it. For N=9, instead of naturally looking

(1,2,3) (4,5,6) (7,8,9)  
(1,4,7)
(1,2,3) (4,5,6) (7,8,9)

you use the fact that after the first 3 calls there are 3 trios of journalists with all the information, and so they can act independently. This is nicely generalized to higher powers of 3, where the advantage is taken at the level right before the first unification of “all the information”.

It seems that your solution for N=27 may be extended to N=33 to require 30 calls: Extend every group of 9 by two more journalists; every such group will need 2 more calls (one to gather the information from the new ones; another to distribute all the information to them) – totally, 6 more calls.

So, this gives another solution with 30 calls, which will work also for 33 journalists – as Grimbal mentioned in his first post.
Title: Re: Journalist information exchange
Post by asterix on Feb 4th, 2005, 7:03am
Doesn't tower's solution work for all even N's greater than 4? It just alternates calls by 1 going up the list and N going down the list. Everyone else will get info on everyone below them from 1 and everybody above them from N.
Title: Re: Journalist information exchange
Post by JocK on Feb 4th, 2005, 1:24pm

on 02/04/05 at 00:54:40, towr wrote:
And then I found a better solution and edited my post accordingly..
ah well..


Ic... so the tags [e] .. [/e] mean later edit..?
Sorry... didn't know that!

Good to know - as I often make errors that need later correction - ...  
Title: Re: Journalist information exchange
Post by JocK on Feb 4th, 2005, 2:00pm

on 02/04/05 at 05:16:58, Barukh wrote:
JocK, I’ve found your solution for power-of-3 very nice! I hope you won’t mind explaining here my understanding of it. For N=9, instead of naturally looking

(1,2,3) (4,5,6) (7,8,9)  
(1,4,7)
(1,2,3) (4,5,6) (7,8,9)

you use the fact that after the first 3 calls there are 3 trios of journalists with all the information, and so they can act independently. This is nicely generalized to higher powers of 3, where the advantage is taken at the level right before the first unification of “all the information”.


Another way of looking at it is to imagine the 3k journalists sitting in cells in a 3x3x..x3 (hyper)cubical office.

You 'sweep up' all information by first collecting information along row directions (scanning all rows in the k-dimensional hypercube). Then you sweep a k-dimensional 'face' in orthogonal direction. Then a (k-1)-dimensional 'edge' of the 'face', again in an orthogonal direction. Etc... Until you arrive at a 2-dimensional sub-space that gets sweeped. You then distribute the information by scanning the same 2-dimensional sub-space in the orthogonal direction. Subsequently you distribute the information in 3-dimensional and higher dimensional sub-spaces until you have distributed all information over the whole hypercube (the reverse of the sweeping process).

In this geometrical representation, your solution for 33 journalists is obtained by extending the 3x3x3 office with a conservatory of 3x2 cells connected to the cells in the office that are part of the 3x3 sweep... :)
Title: Re: Journalist information exchange
Post by JocK on Feb 5th, 2005, 5:46am
Of course, Barukh's extension of the 'power-of-three algorithm' leads to N-3 conference calls for any number N of journalists that can be split into nine groups of an odd number. I.e. it works for all odd number N of journalists if N is at least 9.

It seems that for a large enough number N of journalists, the number of calls required is N-3 for odd N and N-2 for even N.
Title: Re: Journalist information exchange
Post by towr on Feb 5th, 2005, 9:37am

on 02/04/05 at 07:03:58, asterix wrote:
Doesn't tower's solution work for all even N's greater than 4? It just alternates calls by 1 going up the list and N going down the list. Everyone else will get info on everyone below them from 1 and everybody above them from N.
You're right, it does work for all even N's above 4.
I got confused from the way I drew out the problem on paper.
Title: Re: Journalist information exchange
Post by Barukh on Feb 5th, 2005, 10:28am

on 02/04/05 at 07:03:58, asterix wrote:
Doesn't tower's solution work for all even N's greater than 4? It just alternates calls by 1 going up the list and N going down the list. Everyone else will get info on everyone below them from 1 and everybody above them from N.

Ah, now I see! Very nice, towr!
Title: Re: Journalist information exchange
Post by Aryabhatta on Feb 6th, 2005, 1:14pm
This is known as the gossip problem!

If f(n,k) is the minimum number of calls with which the gossiping can be done, with k-way conferencing available, it has been shown that

f(n,k) = [(n-2)/(k-1)] + [(n-1)/k] + 1 if n [le] k2
and
f(n,k) = 2[(n-2)/(k-1)] for n > k2

where [x] is integer part of x.

Reference: http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/gossip.

Search for "Further Gossip Problems".
Title: Re: Journalist information exchange
Post by Grimbal on Feb 6th, 2005, 5:42pm
Well, my solution was simpler.

I found the solution with 9 people in 6 calls.  Then, from a solution, you can add 2 people and 2 calls by
1. have anyone call the 2 extra people
2. apply the known solution
3. have anyone call the 2 extra people

This applied 12 times brings 6+24=30 calls for 9+24 = 33 people.

The "wasted bandwidth" comes from the fact that
1. the 2 extra people call each other twice, but the solution works even if they ignore what the other one says during these calls,
2. if A gathers the information from the 2 extra people and another person B informs them at the end, then they could inform B of what A knows, so the "known solution" is sufficient even if it doesn't let B learn A's fact.
3. We could go a little further: We could add 4 people at a time: c, d, e, f, and call A1,A2,B1,B2 4 people from the existing solution.  With the calls: (A1,c,d) (A2,e,f) (apply old solution) (B1,c,e) (B2,d,f) we have that c,d,e,f's information spreads to everybody and they later get everybody's information, but as an "extra bandwidth", they can carry information from A1 and A2 to B1 and B2, so that the "old solution" can tolerate a few gaps.

In short, the fact that the problem was given with 32 people and not 33 and the fact that there seem to be room for improvement made me wonder whether there was a way to organize these calls in a clever way.

About puzzleup, They don't show the solutions, even when registered.  But I have the maximum number of points so far, so my solution (30) must right, or at least the one they expected.
Title: Re: Journalist information exchange
Post by Nigel_Parsons on Feb 6th, 2005, 5:43pm
I apologise in advance if I haven't understood some of the above, but...
A) For 33 journos, 11 conference calls will concentrate all inf in 11 persons (one from each call)
B) For 9 of those eleven journos 3 conference calls will concentrate the info into 3 persons (one from each call)
C) From those three persons, 1 call will make each aware of the information previously held by 27 persons.
D) Any one of the persons in the call in 'C' now has a conference call with two of the persons left out between steps 'A' & 'B'. This gives each of those three full info.

O.K. I realise what I miss-read, all the journos need the full info. I've got all the info together in 22 calls. (and held by 3 persons) Re-dissemination would take a further 14 (11+3) calls assuming total ignorance by each of the remaining 27 journos.

However, my missreading gives a good upper bound of 36 calls using easy routes.
Title: Re: Journalist information exchange
Post by rmsgrey on Feb 6th, 2005, 6:27pm

on 02/06/05 at 17:43:01, Nigel_Parsons wrote:
I apologise in advance if I haven't understood some of the above, but...
A) For 33 journos, 11 conference calls will concentrate all inf in 11 persons (one from each call)
B) For 9 of those eleven journos 3 conference calls will concentrate the info into 3 persons (one from each call)
C) From those three persons, 1 call will make each aware of the information previously held by 27 persons.
D) Any one of the persons in the call in 'C' now has a conference call with two of the persons left out between steps 'A' & 'B'. This gives each of those three full info.

O.K. I realise what I miss-read, all the journos need the full info. I've got all the info together in 22 calls. (and held by 3 persons) Re-dissemination would take a further 14 (11+3) calls assuming total ignorance by each of the remaining 27 journos.

However, my missreading gives a good upper bound of 36 calls using easy routes.


Maybe I'm missing something, but I make A+B+C+D=11+3+1+1=16 calls to get 3 people fully in the know, then 15 calls to bring the other 30 up to date (each call gives 2 people full info) giving a bound of 31 calls. You can save one call by spotting that the 2 people dropped in step B are actually triplets, so you can repeat step D with one from each of those cells and the cell from step C, meaning 2 additional calls give 9 people fully in the know - which would have taken 3 additional calls to achieve if you assumed everyone else knew nothing.
Note that knowing any information from the two dropped cells is now equivalent to knowing everything, and you can then treat those who don't know everything as knowing nothing.

This gives a 30 call solution.
Title: Re: Journalist information exchange
Post by Barukh on Feb 11th, 2005, 4:26am

on 02/06/05 at 13:14:58, Aryabhatta wrote:
This is known as the gossip problem!

If f(n,k) is the minimum number of calls with which the gossiping can be done, with k-way conferencing available, it has been shown that

f(n,k) = [(n-2)/(k-1)] + [(n-1)/k] + 1 if n [le] k2
and
f(n,k) = 2[(n-2)/(k-1)] for n > k2

where [x] is integer part of x.

I visited the library the other day and found the article of  Kenneth Lebensold from 1973 where this is proved. The author gives a lengthy (albeit quite elementary) proof of this lower bound (this is given in the form of 29 lemmas!). Then, it takes him half a page to show the actual construction – quite similar to Grimbal’s solution.

By the way, this is the only paper I’ve seen that discusses this variation of the gossip problem.
Title: Re: Journalist information exchange
Post by Aryabhatta on Feb 11th, 2005, 9:12am

on 02/11/05 at 04:26:00, Barukh wrote:
I visited the library the other day and found the article of  Kenneth Lebensold from 1973 where this is proved. The author gives a lengthy (albeit quite elementary) proof of this lower bound (this is given in the form of 29 lemmas!). Then, it takes him half a paper to show the actual construction – quite similar to Grimbal’s solution.

By the way, this is the only paper I’ve seen that discusses this variation of the gossip problem.


Wow! 29 lemmas is a lot! Seems like the author had a lot of time on his hands  ;D

But it is a nice result which solves the problem and leaves no open ends.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board