Author |
Topic: Journalist information exchange (Read 1001 times) |
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
 |
Journalist information exchange
« on: Feb 2nd, 2005, 5:31am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Journalist information exchange
« Reply #1 on: Feb 3rd, 2005, 6:02am » |
Quote Modify
|
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]
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
[smiley=square.gif]
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Journalist information exchange
« Reply #2 on: Feb 3rd, 2005, 8:15am » |
Quote Modify
|
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]
|
| « Last Edit: Feb 3rd, 2005, 8:27am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Journalist information exchange
« Reply #3 on: Feb 3rd, 2005, 2:12pm » |
Quote Modify
|
on Feb 3rd, 2005, 8:15am, 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.
|
| « Last Edit: Feb 3rd, 2005, 3:40pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Journalist information exchange
« Reply #4 on: Feb 3rd, 2005, 3:38pm » |
Quote Modify
|
on Feb 3rd, 2005, 2:12pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Journalist information exchange
« Reply #5 on: Feb 3rd, 2005, 3:49pm » |
Quote Modify
|
on Feb 3rd, 2005, 3:38pm, 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?
|
| « Last Edit: Feb 3rd, 2005, 4:04pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Journalist information exchange
« Reply #6 on: Feb 4th, 2005, 12:54am » |
Quote Modify
|
on Feb 3rd, 2005, 3:49pm, 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
|
| « Last Edit: Feb 4th, 2005, 12:56am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Journalist information exchange
« Reply #7 on: Feb 4th, 2005, 5:16am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
asterix
Guest
|
|
Re: Journalist information exchange
« Reply #8 on: Feb 4th, 2005, 7:03am » |
Quote Modify
 Remove
|
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.
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Journalist information exchange
« Reply #9 on: Feb 4th, 2005, 1:24pm » |
Quote Modify
|
on Feb 4th, 2005, 12:54am, 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 - ...
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Journalist information exchange
« Reply #10 on: Feb 4th, 2005, 2:00pm » |
Quote Modify
|
on Feb 4th, 2005, 5:16am, 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... 
|
| « Last Edit: Feb 4th, 2005, 2:07pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Journalist information exchange
« Reply #11 on: Feb 5th, 2005, 5:46am » |
Quote Modify
|
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.
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Journalist information exchange
« Reply #12 on: Feb 5th, 2005, 9:37am » |
Quote Modify
|
on Feb 4th, 2005, 7:03am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Journalist information exchange
« Reply #13 on: Feb 5th, 2005, 10:28am » |
Quote Modify
|
on Feb 4th, 2005, 7:03am, 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!
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Journalist information exchange
« Reply #14 on: Feb 6th, 2005, 1:14pm » |
Quote Modify
|
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".
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Journalist information exchange
« Reply #15 on: Feb 6th, 2005, 5:42pm » |
Quote Modify
|
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.
|
| « Last Edit: Feb 6th, 2005, 5:49pm by Grimbal » |
IP Logged |
|
|
|
Nigel_Parsons
Junior Member
Gender:
Posts: 63
|
|
Re: Journalist information exchange
« Reply #16 on: Feb 6th, 2005, 5:43pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Journalist information exchange
« Reply #17 on: Feb 6th, 2005, 6:27pm » |
Quote Modify
|
on Feb 6th, 2005, 5:43pm, 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.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Journalist information exchange
« Reply #18 on: Feb 11th, 2005, 4:26am » |
Quote Modify
|
on Feb 6th, 2005, 1:14pm, 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.
|
| « Last Edit: Feb 11th, 2005, 11:59am by Barukh » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Journalist information exchange
« Reply #19 on: Feb 11th, 2005, 9:12am » |
Quote Modify
|
on Feb 11th, 2005, 4:26am, 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 
But it is a nice result which solves the problem and leaves no open ends.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print