Juicy Gossip

Probability Level 3

Math town has 1990 residents. Everyday the residents would tell all of their friends about the gossip they heard yesterday. If there is a gossip, it is guaranteed that all residents will know it from the friends over time.

If a gossip is told to 180 residents on day 0, the next day(day 1) the 180 residents will tell all their friends about it, and the day after that(day 2) all of the residents who knew the gossip will start talking about it to their friends. This process continue for 10 days.On day 10, is it guaranteed that all of the 1990 residents in Math Town knew the gossip?

No Yes I don't know Cannot be determined

2 solutions

Dylan Pentland
Mar 5, 2015

Here's a counter example: Give each resident a number, $1$ through $1990$ . Say we create a friendship between residents $n$ and $n+1$ for all $n$ from $1$ to $1989$ . Clearly, if there is gossip all residents will know it after a finite amount of time.

Now, suppose gossip is told to residents $1$ through $180$ . Then, only one new person learns the gossip every day, so by day $10$ not everybody knows the gossip.

Nate Ji
Feb 6, 2015

Gossip spreads when residents who know it tell it to all of their friends. However, should at least one person, who is outside of the 180 that knew the gossip in the beginning, not have any friend, then they would have no way of knowing the gossip. Thus, it is not guaranteed that all 1990 residents in Math Town knew the gossip by day 10.

Wrong. It says, "it is guaranteed that all residents will know it from their friends over time." This means that no one is isolated from everyone else; in other words, everyone has at least one friend.

Nathanael Case - 6 years, 4 months ago

Juicy Gossip

2 solutions

0 pending reports