Answered

In a network of weather stations, each station is required to know how many hours of daylight there were at each of the others. Unfortunately their email system has been infected by a virus and they can only communicate via phone calls. For three stations, show that three separate calls are required so that all three sets of results are known at all three stations. For five stations show that at least six separate calls are required what is the minimum number of calls if there are seven stations? extend your reasoning for n stations.

Answer :

MathPhys

Answer:

10

2n − 4

Step-by-step explanation:

This is also known as the "gossip problem".

Let's start with three stations, A, B, and C.  Station A knows information A, B knows information B, and C knows information C.

First, A calls B, and they share information.  So now both have information AB.

Next, B calls C.  They share information, and now both have information ABC.  Finally, A calls either B or C.  Now all three stations know all three pieces of information.  It took 3 calls.

[tex]\left\begin{array}{cccc}0&A&B&C\\1&AB&AB&C\\2&AB&ABC&ABC&3&ABC&ABC&ABC\end{array}\right[/tex]

Let's repeat with 4 stations: A, B, C, and D.

First, A calls B and C calls D.  Then, A calls C and B calls D.  It takes 4 calls.

[tex]\left\begin{array}{ccccc}0&A&B&C&D\\1&AB&AB&C&D\\2&AB&AB&CD&CD\\3&ABCD&AB&ABCD&CD\\4&ABCD&ABCD&ABCD&ABCD\end{array}\right[/tex]

Let's try 5 stations.  But this time, let's put the first 4 stations in a group.  The fifth station E, calls someone in the group.  The group takes 4 calls to circulate information.  Then, someone in the group calls E.  It takes a total of 6 calls.

[tex]\left\begin{array}{cccccc}0&A&B&C&D&E\\1&AE&B&C&D&AE\\2&ABE&ABE&C&D&AE\\3&ABE&ABE&CD&CD&AE\\4&ABCDE&ABE&ABCDE&CD&AE\\5&ABCDE&ABCDE&ABCDE&ABCDE&AE\\6&ABCDE&ABCDE&ABCDE&ABCDE&ABCDE\end{array}\right[/tex]

As long as n ≥ 4, it follows the same pattern.  One group of 4 forms a "hub".  Every person outside of the hub calls someone in the hub (n − 4 calls).  The hub circulates among themselves (4 calls).  Then, every one in the hub calls someone outside of the hub to relay the information back (n − 4 calls).  The total is (n − 4) + 4 + (n − 4) = 2n − 4.

So for 7 stations, it takes a minimum of 10 calls.

Other Questions