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
them know everything?
20 comments:
S(1) = 0
S(2) = 1
Solution:
(2*S((N-mod(N,2))/2))+((N-mod(N,2))/2)+((N-mod(N,2))*2)
Well... that's quiet interessting but frankly i have a hard time figuring it... wonder how others think about this..
It will be N-1 as every person has to be contacted atleast once...
i dun really understand what André Meneses's equation is..
but i think answer is 2n-1...?
My answer is a series...
mod(x,y) is the remainder of the division x/y
at the end of the equation if s(1) equals 0 and s(2) equals 1...
n-1 is the answer
i think 2n-2 because everyone calls one person and shares their info (n-1) phone calls, then that person calls everyone back with all the info (n-1) phone calls, so (n-1)+(n-1)= 2n-2. I don't know if there's a more efficient way, but I'm not sure how everyone can have all the info with just n-1 phone calls
the answer is n.
to Audrey,
it should be 2n-1, because the last person who called the first person will already share everything.. hence the first person need not call the last person again..
The worst case of the calls to connect each other is n-1.
All of the persons except lastone should recieve calls twice to know all secrets.
So Total calls = 2(n-1) - 1 = 2n-3.
Also the sharing of the secret can be minimised for the first 4 persons.
To share a secret for 4 persons (say a,b,c,d), only 4 calls are sufficient.
(a,b) (c,d) (a,c) (b,d).
2(4) - 3 = 5.
(actually 4 calls are sufficent for first 4 persons)
One call can be optimized there.
So total calls = (2n-3) - 1 = 2n-4.
Trinadh, what would the calls look like for n = 5? Can you find a way where than make no more than n-1 calls?
I need at least 7.
(a,b) (c,d) (a,e) (c,e) (a,d) (b,c) (e,anyone)
the answer is (n!)
To start with, let us say how many calls does one take in case of 4 folks::
1 2 3 4
=== ===
Group1 Group2
Now 1 and 2 talk, 3 and 4 talk
As such,
1-> knows (1 and 2)
2 -> 12
3-> 34
4-> 34
Now say 1 from Group1 and 4 from Group2 talk.
Now the case is
1> 12 +34 = 1234
4-> 12 + 34 = 1234
Now let 2 and 3 talk,
After this again
3-> 34 + 12 = 1234
4-> 34 + 12 = 1234
So in a group of 4 only 4 converstaions need to be done to let everybody know of the other 3 folks' secret.
Now take the case of 5,
1234 5
Group1 Group2
Suppose 4 talks to 5 and gets his secret. Now let the group of 4 ( Group 1) talk among themselves.So 4 convs need to be made to let 1,2,3,4 know -> 1234 + 5'secret.
Now 4 goes and talks to 5 . Now everybody knows everybody's secret.
Total convos = 1 + 4 + 1 = 6
This can be best visualised like this ::
------
| 1234 | --> 5
<--
------
4 convos + 2 convos
For 6
------
| 1234 | --> 5 --> 6
<-- <--
------
4 + 2 + 2
In case of 6, let 6 talk to 5, then 5 talks to 4 , now let the group of 4 talk to each other. After these 6 calls, 1234 know - > 123456 . After that 4 ( from 1234) talks to 5 ( here 5 knows -> 123456 ).
And then 5 talks to 6 (or 4 to 6) (after this 6 too knows 123456 )
Hence it is like
4 - > 4 == ( 2*4 - 4)
5 -> 6 = 2*5 -4
6-> 8 = 2*6 -4
The magic is 4 . For 3 , it takes 3 convos ( not 2 ) for each to know of the others' secret. ( 2*3 - 3)
For 2 -> 1 ( 2*2 - 3 )
so for 2 and 3, it is (2n -3)
And for any no >=4 it is (2n -4)
The grouping of 4 is the key.
i think the answer would be..
2n-3..
for minimum nos of calls all of the agents must call to a particular agent so total nos of calls to that agent will be (n-1)..nd now this agent nd the agent calling last has full information...now the other left out agents (n-2) must again phone to him nd gather the full information....so
total nos of calls= (n-1)+(n-2)=2n-3
feddas it doesnt say that there are 5 people it says n...
if its a,b,c,d,e that means that the amount of secret agents are given in the question but its not
2n-3
Solution:
a
1 Agent = 0 Calls
a b
a = b
2 Agent= 1 Calls
a b c
a = b c
b = c
3 Agent = 3 Calls
a b c d
a = b c d
b = c d
c = d
4 Agent = 6 Calls
a b c d e
a = b c d e
b = c d e
c = d e
d = e
5 Agent = 10 Calls
a b c d e f
a = b c d e f
b = c d e f
c = d e f
d = e f
e = f
6 Agent = 15 Calls
((n^2 + n) / 2 ) - n = No. of calls
"Anonymous" of April 18 is correct.
4 agents clearly only require 4 conversations, not 6:
1) 1<>2 (1 knows 1,2 | 2 knows 1,2)
2) 3<>4 (3 knows 3,4 | 4 knows 3,4)
3) 1<>3 (1 knows 1,2,3,4 | 3 knows 1,2,3,4)
4) 2<>4 (2 knows 1,2,3,4 | 4 knows 1,2,3,4)
Thereafter, each time you add an agent to the previous group of agents, two extra conversations are required - one at the start between the last added agent and a member of the previously established group, and one at the end between the last added agent and the group.
Therefore 4 agents require 4 conversations, 5 req 6, 6 req 8, 7 req 10, etc.
So, for 4 or more agents, 2n-4 conversations will suffice.
should be (n-1)!
Post a Comment