Brain Teasers
Gossiping
n people each know a different piece of gossip. They can telephone each other and exchange all the information they know (so that after the call they both know anything that either of them knew before the call). What is the smallest number of calls needed so that everyone knows everything?
Answer
1 for n=23 for n=3
2n-4 for n>=4
This can be achieved as follows: choose four people (A, B, C, and D) as the "core group". Each person outside the core group phones a member of the core group (it doesn't matter which); this takes n-4 calls. Now the core group makes 4 calls: A-B, C-D, A-C, and B-D. At this point, each member of the core group knows everything. Now, each person outside the core group calls anybody who knows everything; this again requires n-4 calls, for a total of 2n-4.
Hide Answer Show Answer
What Next?
View a Similar Brain Teaser...
If you become a registered user you can vote on this brain teaser, keep track of which ones you have seen, and even make your own.
Solve a Puzzle
Comments
I dont get it. Why cant it be n!(factorial) ?
2n-4 is much smaller than n! This is a very cleverly constructed solution. It is surprising that 4 is the optimum group size.
Very good solution. I liked the idea of having a core group.
Sep 16, 2009
I guess it is a normal set coverage case... the answer should be n-1
just check it.. with n-1 paths i can connect all nodes.. so all info flowed to everyone
just check it.. with n-1 paths i can connect all nodes.. so all info flowed to everyone
The deleted user is right. If person A had at least n-1 phones, then he could phone each person with n-1 calls and get all of their information. Then person A could give all the information to everyone.
To post a comment, please create an account and sign in.
Follow Braingle!