Rumor Spreading by Phone
Five students-Priya, Quinn, Ravi, Sofia, and Tomas-want to spread a piece of news to everyone in their group. They communicate only by phone calls. Each phone call lasts exactly 1 minute, and during a call the two people share all the news they know. A person can be in only one call at a time; conference calls are not allowed. Initially, only Priya knows the news. The others know nothing. They want to minimize the total time until all five students know the news. They are considering different calling plans. A simple plan is for Priya to call each of the other four one by one, which takes 4 minutes. But they wonder if they can do better by having people make calls in parallel after they learn the news. What is the minimum time needed for all five to know? Provide a schedule that achieves this minimum. Then, if there were six students instead of five, what would be the minimum time? Explain your reasoning.
1. What is the minimum time needed for all five students to know the news? Provide a schedule that achieves it.
Read the worked answer
The minimum time is 3 minutes. Schedule: Minute 1: Priya calls Quinn. After this call, Priya and Quinn both know. Minute 2: Priya calls Ravi, and simultaneously Quinn calls Sofia. After minute 2, Priya, Quinn, Ravi, and Sofia all know. Minute 3: Priya calls Tomas. Now Tomas knows, and all five know. So 3 minutes suffices. Could it be done in 2 minutes? In 2 minutes, the maximum number of people who can know is: starting with 1, after minute 1 at most 2 know (Priya+1). In minute 2, each of those 2 can call one new person, so at most 2 new people learn, giving at most 4 people total. So 2 minutes cannot reach 5. Therefore 3 is minimal.
2. Explain why 2 minutes is impossible for five students.
Read the worked answer
We can count the maximum number of informed students after each minute. After 1 minute, at most 2 students know (the caller and the receiver). During the second minute, only the students who already know can make calls, and each such student can be in only one call. So the two informed students can each call one uninformed student, at most adding 2 new informed students. That gives at most 2+2=4 informed students after 2 minutes. Since 4 < 5, 2 minutes is not enough. This 'doubling' argument shows the minimum time must be at least 3 minutes. Our 3-minute schedule achieves 5, so 3 is optimal.
3. If there were six students instead of five, what would be the minimum time? Justify.
Read the worked answer
For six students, the minimum time is still 3 minutes. After 2 minutes at most 4 know. In minute 3, each of the 4 informed students can call one uninformed student, so up to 4 new people can learn, but only 2 uninformed remain (since 6-4=2). So 2 of the informed can call the 2 uninformed, and all 6 know by end of minute 3. Schedule: Minute 1: Priya calls Quinn (2 know). Minute 2: Priya calls Ravi, Quinn calls Sofia (4 know: Priya, Quinn, Ravi, Sofia). Minute 3: Priya calls Tomas, Quinn calls Uma (or any two informed call the two uninformed). Now all 6 know. So 3 minutes suffices. Could it be 2? No, because max after 2 is 4 < 6. So minimum is 3 minutes.