8. Suppose that there are n people in a group, each of whom is aware of...

Transcribed Image Text:

8. Suppose that there are n people in a group, each of whom is aware of a scandal that noone else in the group knows about. These people communicate by telephone; when two people in the group talk, they share information about all of the scandals that they know about. For example, on the first call, two people share information, so after this call they each know about two scandals. The gossip number G(n) is the minimum number of telephone calls needed for all of the people to know about all of the scandals. (a) Show that G(1) = 0, G(2) = 1, G(3) = 3 and find G(4). (b) Use mathematical induction to prove that G(n) 2n4 for n 4. (Hint. For the inductive step, have a new person call a particular person at the start and at the end.) In case you are wondering, it is true that G(n) = 2n 4 for n 4, but this is quite hard to prove! 8. Suppose that there are n people in a group, each of whom is aware of a scandal that noone else in the group knows about. These people communicate by telephone; when two people in the group talk, they share information about all of the scandals that they know about. For example, on the first call, two people share information, so after this call they each know about two scandals. The gossip number G(n) is the minimum number of telephone calls needed for all of the people to know about all of the scandals. (a) Show that G(1) = 0, G(2) = 1, G(3) = 3 and find G(4). (b) Use mathematical induction to prove that G(n) 2n4 for n 4. (Hint. For the inductive step, have a new person call a particular person at the start and at the end.) In case you are wondering, it is true that G(n) = 2n 4 for n 4, but this is quite hard to prove!

Answer rating: 100% (QA)

a The problem youve presented is a classic example of a mathematical problem that can be solved using combinatorics and induction Lets tackle it step ... View the full answer