### 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 hidden to avoid spoilers.

## Follow Braingle!