Tuesday, March 07, 2006
Gossip heard round the world
There are six busybodies in town who like to share information. Whenever one of them calls another, by the end of the call they both know evertything that the other one knew beforehand. One day, each of the six picks up a juicy piece of gossip. What is the minimum number of phone calss required before all six of them know all six of these tidbits?
Subscribe to:
Post Comments (Atom)
The minimum number of calss required is 8. The formula for such a problem is 2n-4 where n is the number of busybodies.
ReplyDeleteBut for this problem, let's label each of the callers as A, B, C, D, E and F. Divide the six into two groups so that A, B, and C are in group 1. Then start calling:
1) A-B
2) A-C (A and C now know all there is in group 1)
3) D-E
4) D-F (D and F now know all there is in group 2)
5) A-D (A and D now know everything)
6) C-F (C and F now know everything)
7) B-A (B knows everything)
8) E-F (E knows everything)