Earlier today I set you the following problem, suggested by maths influencer Bobby Seagull:
Four friends each have a different piece of gossip. They are all in separate locations, and can communicate only via their phones.
1) What is the smallest number of text messages that they need to send between each other to guarantee that everyone knows all the gossip? (In other words, what’s the most efficient texting strategy to make sure each person has every piece of gossip? A text message goes from one person to one person, i.e. if you send one message to two recipients that would count as two messages.)
6 texts. The quickest way is for one of the friends to become the gossip hub. The three others text that person their pieces of gossip. Once that person has all the information, he/she texts each of them back. The hub receives three texts, and sends three texts, totalling 6 texts.
You’re only going to get this answer via trial and error – trying out different strategies, and coming to the conclusion about which is the most efficient.
2) What is the smallest number of phone calls they need to make between each other to guarantee that everyone knows all the gossip? In a phone call between two friends, each friend can share what they know with the other.
4 calls. Let the friends be A, B, C and D. The best way now is for, say, A to call B and C to call D, as illustrated in (i) below. Once they have shared their gossip, if A calls C and B calls D, as illustrated in (ii), everyone will have all the facts.
Again, getting the answer requires testing different strategies.
The group now has eight friends. Again, each has a different piece of gossip.
3) What’s the smallest number of text messages that they need to send between each other to guarantee that all eight know all the gossip?
14 texts. Again, there is no better way than nominating a hub. The hub will receive seven texts, one from each friend, and then send out seven texts, totalling 14 texts.
4) What’s the smallest number of phone calls that they need to make between each other to guarantee that all eight know all the gossip?
12 calls. Here’s the clever bit. We know that with four friends all the information is shared in four calls. With eight friends, A, B, C, D, E, F, G and H, the quickest way to share the information is to nominate a hub of four friends, say A, B, C and D.
Step 1: E, F, G and H each call someone in the hub (four calls) to share their information.
Step 2: The hub shares their info in four calls.
Step 3: A member of the hub calls each of E, F, G and H. (four calls)
Total: 12 calls.
Can you general this for n friends? What is quite surprising about the results?
You may have spotted the pattern by now. With text messages (1-way sharing), you are never going to be able to improve the strategy of nominating a single person as a hub, everyone texting the hub, and the hub texting everyone back. So, with n people, the total is 2(n –1), or 2n –2.
Likewise, with phone calls (2-way sharing), the best strategy win n is bigger than 4 is to use (as above) a hub of four people. Everyone not in the hub calls someone in the hub (n –4 calls), the hub shares the info (4 calls) and then someone in the hub calls everyone back (n –4 calls). The total is 2n – 4.
What is surprising is that you might have expected 2-way sharing to be a much more efficient way to spread gossip than 1-way sharing. In fact, it only reduces the number of calls by two, which when n is large is insignificant. In other words, information can spread almost as fast via text as it can via 2-way phone conversations.
If you want a rigorous proof that 2n –4 is the smallest number of phone calls that guarantees the gossip is known by all you can read it here on the excellent Mind Your Decisions. Be warned, it is quite technical.
I hope you enjoyed today’s puzzle. I’ll be back in two weeks.
I set a puzzle here every two weeks on a Monday. I’m always on the look-out for great puzzles. If you would like to suggest one, email me.
Thanks to Bobby Seagull for suggesting today’s puzzle. His book is The Life-Changing Magic of Numbers: How Maths Shapes Everyday Life. His podcast is Maths Appeal, and his new BBC Two series, Monkman & Seagull’s Genius Guide to the Age of Invention, is out in the autumn.