This curious result arises out of the following situation: 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?
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, Bjorn Poonen, and George Poonen produced to illustrate these results:
The minimum number of days doesn't increase steadily as the number of participants grows. From the pattern, you can see that it would probably be helpful to consider odd and even numbers of participants separately.
Suppose a group has an even number of gossipers. On the first day, the group can be divided in half. Each of the two 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 2D, then the minimum number of days required to spread the rumors to everyone in the group is D. Thus, four (22) participants would take two days; and eight (23) 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 members (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.
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 members (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.
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 (22) gossipers would need two days, six would need three days (the next higher power of two is 23), eight would need three days, and 10 would need four days (because 10 is greater than eight but smaller than 16, or 24)
.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 (22) gossipers would need two days, six would need three days (the next higher power of two is 23), eight would need three days, and 10 would need four days (because 10 is greater than eight but smaller than 16, or 24)
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 rumor mongering may be somewhat unrealistic. "Admittedly, one day is a bit much for the time it takes for even the most loquacious of rumor mongers to communicate with a friend!" they commented. "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 said. "In fact, this is the situation in which our problem originally arose."
Originally posted March 17, 1997
No comments:
Post a Comment