| | Ivars Peterson's MathTrek |
March 17, 1997
This curious result arises out of the following mathematical problem: A group of friends love sharing their gossip. Each gossiper initially knows something that no one else in the group knows. Each day, some of the gossipers phone each other and exchange all the news they have collected so far. On a given day, however, each gossiper can participate in only one phone call, and no conference calls are allowed.
What is the minimum number of days required for all gossipers in the group to learn all the news?
Clearly, if the group consists of only one member, the minimum number of days is zero; for two people, only one call is required to share two pieces of gossip. A group of three people needs three days to get everyone up to speed, and a group of four people takes only two days.
Here's the table that C. Kenneth Fan of Harvard University, Bjorn Poonen of Princeton University, and George Poonen of Renaissance Solutions in Lincoln, Mass., produced:
| Number of gossipers: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| Minimum number of days: | 0 | 1 | 3 | 2 | 4 | 3 | 4 | 3 |
Suppose a group has an even number of gossipers. On the first day, one can divide the group in half. Each of these subgroups will learn all the gossip within the subgroup in a certain number of days. Gossipers in one subgroup can then be paired with gossipers in the other subgroup so that, in another day, all the gossipers know all the gossip.
It turns out that if the number of gossipers, n, is 2^D, then the minimum number of days required to spread the rumors to everyone in the group is D. Thus, four (2^2) participants would take two days; and eight (2^3) gossipers would require three days.
Now, consider a group of seven gossipers: Alice, Bob, Carol, Daniel, Eric, Fred, and Greta. One way to spread the rumors is to divide the group into two subgroups, one consisting of four members (Alice, Bob, Carol, and Daniel) and the other of three (Eric, Fred, and Greta). On the first day, Alice phones Eric, Bob phones Fred, and Carol phones Greta, while Daniel takes a break. At this point, Alice, Bob, Carol, and Daniel collectively have all the information available, and it takes them two days to share it among themselves. Then, Alice calls back Eric, Bob calls Fred, and Carol calls Greta to complete the information transfer. Total time: four days.
Illustration of how rumors can spread in four days among seven gossipers. The numbers indicate the day on which the connected couple communicates .
It turns out that four days is the best that a group of seven can do no matter what the strategy. In an article in Mathematics Magazine, Fan, Poonen, and Poonen prove that, in general, the minimum number of days for an even number of participants to share information is given by the exponent of the power of two exactly representing the number of gossipers or by the exponent of the next higher power of two. Thus, four (2^2) gossipers would need two days, six would need three days (the next higher power of two is 2^3), eight would need three days, and 10 would need four days (because 10 is greater than eight but smaller than 16, or 2^4). For an odd number of participants, just add one day to the number of days required by the next higher even number of gossipers.
Fan, Poonen, and Poonen readily concede that their mathematical model of rumormongering may be somewhat unrealistic. "Admittedly, one day is a bit much for the time it takes for even the most loquacious of rumormongers to communicate with a friend!" they comment. "Perhaps one hour or even one minute would have been more realistic."
Interestingly, the problem can also be interpreted in terms of communication between computers operating in parallel. "The result can be useful, for instance, when multiple copies of a database are distributed to several locations and replication is needed to keep the databases synchronized," the mathematicians say. "In fact, this is the situation in which our problem originally arose."
Illustration created using Mathematica 3.0 ( http://www.wolfram.com).
Comments are welcome. Please send messages to Ivars Peterson at. ipeterson@maa.org