Question

In: Advanced Math

Suppose that there are n people in a group, each aware of a different secret no...

Suppose that there are n people in a group, each aware of a different secret no one else in the group knows about. These people communicate by phone; when two people in the group talk, they share information about all secretes each knows about. For example, on the first call, two people share information, so by the end of the call, each of them knows about two secretes. The gossip problem asks for the number of phone calls that are needed for all n people to learn about all the secrets.

(a) Find the smallest number of telephone calls when there are 3 and 4 people respectively. [2 marks]

(b) Prove by induction that the total number of phone calls for all n people to learn about all secretes is not more than 2n−4 for any n ≥ 4.

Solutions

Expert Solution

Please feel free to ask any doubts regarding the solution and please rate positively.

Kind Regards.


Related Solutions

Suppose that the birthdays of different people in a group of n people are independent, each...
Suppose that the birthdays of different people in a group of n people are independent, each equally likely to be on the 365 possible days. (Pretend there's no such thing as a leap day.) What's the smallest n so that it's more likely than not that someone among the n people has the same birthday as you? (You're not part of this group.)
PROBLEM 6. Suppose that the birthdays of different people in a group of n people are...
PROBLEM 6. Suppose that the birthdays of different people in a group of n people are independent, each equally likely to be on the 365 possible days. (Pretend there's no such thing as a leap day.)What's the smallest n so that it's more likely than not that someone among the n people has the same birthday as you? (You're not part of this group.)
Consider n people and suppose that each of them has a birthday that is equally likely...
Consider n people and suppose that each of them has a birthday that is equally likely to be any of the 365 days of the year. Furthermore, assume that their birthdays are independent, and let A be the event that no two of them share the same birthday. Define a “trial” for each of the ?n? pairs of people and say that 2 trial (i, j ), I ̸= j, is a success if persons i and j have the...
BACKGROUND: Given a group of 'n' people, the odds that at least two people have the...
BACKGROUND: Given a group of 'n' people, the odds that at least two people have the same birthday are much higher than you would think. PLEASE WRITE CODE IN C++ The program takes no input. Assumptions: 1. There is an equal chance of birthday landing on any day of the year. 2. We are not considering a leap year (only 365 days) The simulation will be run in the following manner: 1. For a group size 2, assign a random...
Suppose that 8 Secret Agents are gathered together in a secret room and that 2 of...
Suppose that 8 Secret Agents are gathered together in a secret room and that 2 of the agents are "double-agents" (they also work for another spy agency). If 4 agents are selected for a special, top-secret mission, what is the probability that a double-agent (at least one) is selected for the mission?
A group of n people get on an elevator at Floor 0. There are m floors...
A group of n people get on an elevator at Floor 0. There are m floors besides Floor 0. Each person uniformly randomly chooses one of those m floors to stop at. (All choices are independent, and no one gets on the elevator after Floor 0.) The elevator stops at a floor if at least one person has chosen to stop there. Let X be the number of stops that the elevator makes after Floor 0. (a) What is E[X]?...
A team of size m has to be chosen from a group of n people (m...
A team of size m has to be chosen from a group of n people (m < n) and a captain chosen for the team. (a) How many ways can the captained team be chosen if the captain is chosen first then the remainder of the team chosen. (b) How many ways can the captained team be chosen if the team is chosen first then the captain chosen from the team? This should give the same number as a) but...
Implement Hot Potato game A group of people, numbered 1 to N, are sitting in a...
Implement Hot Potato game A group of people, numbered 1 to N, are sitting in a circle. Starting at person 1, a hot potato is passed. After X passes, the person holding the hot potato is eliminated, the circle closes ranks, and the game continues with the person who was sitting after the eliminated person picking up the hot potato. The last remaining person wins. For example: if X = 0 and N = 5, players are eliminated in order,...
Suppose n people are choosing between two activities, hiking or fishing, where n is an even...
Suppose n people are choosing between two activities, hiking or fishing, where n is an even number. The payoff from going to hike is 1 if more than half of the people go hiking, and 0 otherwise. The payoff from going to fish is 1 if more than half of the people go fishing, and 0 otherwise. A.Find all the Nash Equilibria of this game, if any. B.Suppose instead that the payoffs are such that the payoff to hiking is...
Suppose there is a discussion about the minimum wage policy. A group of people argue that...
Suppose there is a discussion about the minimum wage policy. A group of people argue that the wages are currently too low for unskilled labor. They advise government to increase the minimum wage: (5 points) a. What would this probably mean for the labor market for the college-educated skilled workers? Will that market be affected? Will the equilibrium wage change for the skilled workers? Show using our regular tools of supply and demand. (5 points) b. What about unskilled labor?...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT