There is a group of n people and each of these people has a secret. Each time tw

Question

There is a group of n people and each of these people has a secret. Each time two people have a phone conversation, they share all of the secrets they know with each other. For example, on the first call, the two people share secrets; so after the call both of those people know two secrets. In this problem we are interested in how many phone calls are necessary before all n people know all n secrets. We will call the minimum number of calls necessary C(n) (a) What are C(1), C(2), C(3), C(4)? (b) Prove that for all n4, C(n)2n-4 [Hint: have one person make the first and last call]

Explanation / Answer

(a) C(1) = 0 (no calls needed for one person)

C(2) = 1 (case described in the question itself)

C(3) = 3 (without loss of generality person 1 calls person 2, then person 1 calls person 3, then either person 1 or 3 calls person 2)

C(4) = 5 the calls, expressed in unordered pairs are (1,2),(2,3),(3,4),(4,1),(1 or 3 or 4,2)

It is easy to see that these are the minimum number of calls required

(b) Divide the N people into two groups. If N is odd, one group will contain one extra person.
Consider first group: person 1 will call up person 2, person 2 will call up person 3 and so on. Similarly in second group, person 1 will call up person 2, person 2 will call up person 3 and so on. After (N - 2) calls, two people in each the group will know anything that anyone knew in his group, say they are Y1 & Y2 from group 1 and Z1 & Z2 from group 2.Now, Y1 will call up Z1 and Y2 will call up Z2. Hence, in next two calls total of 4 people will know everything.Now (N - 4) telephone calls are required for remaining (N - 4) people.Total telephone calls require are= (N - 2) + 2 + (N - 4)= 2N - 4.

Now you just need to show that you cannot do better than this.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.