Puzzle:
There are N secret agents each know a different piece of secret information. They can telephone each other and exchange all the information they know. After the telephone call, they both know anything that either of them knew before the call. What are the minimum number of telephone calls needed so that all of the them know everything?
Solution:
(2N - 3) telephone calls, for N = 2,3
(2N - 4) telephone calls, for N > 3
Divide the N secret agents into two groups. If N is odd, one group will contain one extra agent.
Consider first group: agent 1 will call up agent 2, agent 2 will call up agent 3 and so on. Similarly in second group, agent 1 will call up agent 2, agent 2 will call up agent 3 and so on. After (N - 2) calls, two agents in each the group will know anything that anyone knew in his group, say they are Y1 & Y2 from group 1 and Z1 & Z2 from group 2.
Now, Y1 will call up Z1 and Y2 will call up Z2. Hence, in next two calls total of 4 agents will know everything.
Now (N - 4) telephone calls are required for remaining (N - 4) secret agents.
Total telephone calls require are
= (N - 2) + 2 + (N - 4)
= 2N - 4
For Solution SCROLL DOWN...
Solution:
(2N - 3) telephone calls, for N = 2,3
(2N - 4) telephone calls, for N > 3
Divide the N secret agents into two groups. If N is odd, one group will contain one extra agent.
Consider first group: agent 1 will call up agent 2, agent 2 will call up agent 3 and so on. Similarly in second group, agent 1 will call up agent 2, agent 2 will call up agent 3 and so on. After (N - 2) calls, two agents in each the group will know anything that anyone knew in his group, say they are Y1 & Y2 from group 1 and Z1 & Z2 from group 2.
Now, Y1 will call up Z1 and Y2 will call up Z2. Hence, in next two calls total of 4 agents will know everything.
Now (N - 4) telephone calls are required for remaining (N - 4) secret agents.
Total telephone calls require are
= (N - 2) + 2 + (N - 4)
= 2N - 4
13 comments:
for N>=4, 2N-4 is doable, can someone do better than that?
Yup...Agree with Probe ;)...
2*(n-2)
And it cannot be bettered...
I had inferred incorrectly before (2n-3), but the logic used is still the same...
Start off with clustering to obtain minimal spanning tree...Don't remember if that was Prim's or Kruskal's algo :D...Neways, thats irrelevant...
That is, form mutually exclusive clusters, which dont have any members in common, to avoid duplication...
So we end up with two clusters (lets say Cluster C and M) with either n/2 members each, or n/2 and n/2+1, assuming rounding off..
At this stage, i.e., after n/2 - 1
calls in each of the clusters, i.e., total n - 2 calls, we have two members in each cluster who know all about their own cluster...Lets call them C1, C2 and M1, M2.
All we need is two calls for these guys (cluster centers) to know everything...
So in n calls these 4 guys know everything...
So now all that has to be done is disperse the information to the remaining members , ie, n-4 calls
so a total of n + n - 4 = 2(n-2) calls is what it takes...
Now, can we do better than this? i.e., can we disperse the info to the n - 4 guys in less than n - 4 calls ? No, atleast 1 call is required to pass on the information to each, since neither of them have all the info...So n-4 is the min. calls that have to be made to bring them to light...
2n-3 for n=2,3
2n -4 for n>3
for n>2
if n is odd..ans: (2n-3)
if n is even...ans: (2n-4)
if n=2..ans: 2n-3
I think 2N-3 calls are sufficient for all possible values of N.
Jayant said about clusters ,thats ok ,but he missed one call that will take place between two members of each cluster(one from C and one from M) .
If N is larger then actually we can think of it as a tree structure.Make group of 2 peoples to talk.And as the level increases each group will send a leader of group to next level.And at last 2 ppl will have all the information.They will sequentially inform their respective groups.Pictorial representation for 8 ppl would be as follows:
1-2 3-4 5-6 7-8
1 - 3 5 - 7
1 - 5
- REPRESENTS CALL.
similarly for 9 ppl :
1-2 3-4 5-6 7-8 9
1 - 3 5 - 7
1 - 5
1 - 9
All calls except two final persons(1-5 for 8 ppl ,1-9 for 9 ppl) will be repeated to send information back.
can't they have just one conference call??? :)
its 2N-3 for all values of N...
Very good this information and didn't know anything about it, it's good to talk about this issue so we can upgrade!
we can get 2N-3 as a general answer which is not optimized. suppose we have A,B,C,D,E (5 people). Simply A calls B, then B calls C..., in 4 calls D & E know everything. Now E->A -> B -> C are 3 more calls. Done in 7 calls which is 5*2 -3 .
I shall call this a linear method because it doesn't uses mind at all. Please message me if this method is wong or doesn't take 2N-3 steps.
Now the real essence would be to do this in better than 2N-3 step, that would be 2N-4 steps. for that, refer to admin's post. I am worried if this can be solved even better than that, some logarithmic method or something?
Well btw, it clearly requires more than N-1 steps, you know, because there are N-1 data with different people, which a (& every) person has to get.
yeezys
converse shoes
jordan shoes
adidas stan smith shoes
golden goose
coach outlet
jordan shoes
yeezy
yeezys
yeezy boost 700
click here for more louis vuitton replica my response buy replica bags click replica designer bags wholesale
Post a Comment