Continuing the thread of Math-E-Magic puzzles (I'm slowing down for various reasons, but let's continue anyway), I came across this puzzler which has taken me a while to solve. In fact, I couldn't find the best solution, and had to consult the answers (yes, so sue me!).
The puzzle goes like this (and it has various forms):
There are six busybodies in town who like to share information. Whenever one of them calls another, by the end of the conversation they both know everything that the other one knew beforehand. One day, each of the six picks up a juicy piece of gossip. What is the minimum number of phone calls required before all six of them know all six of these tidbits?
I pondered and sketched for a few days, before checking the answer. The best I could achieve was nine, but the answer page starts, "The answer is eight." So I went back to my diagrams and tables, but still couldn't get it down to eight - which was unfortunate, because I was most of the way there. Here, then, is the official answer, and I'll point out what I missed and how I needed an extra phone call.
The puzzle goes like this (and it has various forms):
There are six busybodies in town who like to share information. Whenever one of them calls another, by the end of the conversation they both know everything that the other one knew beforehand. One day, each of the six picks up a juicy piece of gossip. What is the minimum number of phone calls required before all six of them know all six of these tidbits?
I pondered and sketched for a few days, before checking the answer. The best I could achieve was nine, but the answer page starts, "The answer is eight." So I went back to my diagrams and tables, but still couldn't get it down to eight - which was unfortunate, because I was most of the way there. Here, then, is the official answer, and I'll point out what I missed and how I needed an extra phone call.
Firstly, label the six gossips A,B,C, D,E and F. Then divide them into two groups - A-B and D-F. (I did this after a few stalled trials of my own). A talks to B and then C; D talks to E and then F. These are conversations 1,2 and 3,4 shown below.
At this point, C and A both know A, B and . Similarly, F and D both know D,E and F. One conversation between C and F will mean that those two gossips will know everything, and be ready to pass this back to the rest of their teams. What I missed is that A and D both know everything, and one conversation will complete their knowledge. So, since I only used C and F's knowledge, it took me two further conversations (each), so the total went from five up to nine (C-B, C-A; F-E and F-D). It's much more efficient to have A and D speak directly.
Conversations 7 and 8 are C-B (bringing B to completion) and F-E (bringing E to completion).
In general terms, for a puzzle like this (according to the answers), if you have n busybodies, then you will require 2n-4 conversations to have everybody share all the information.
No comments:
Post a Comment