Question 1168178: A rumor is spread randomly among a group of 10 people by successively having one person call someone, who calls someone, and so on. A person can pass the rumor on to anyone except the person who just called. (a) By how many different paths can a rumor travel through the group in three calls? In "n" calls? (b) what is the probability that if A starts the rumor, A receives the third calls? (c) What is the probability that if A does not start the rumor, A receives the third call?
Answer by CPhill(1959)   (Show Source):
You can put this solution on YOUR website! Let $n$ be the number of people in the group, so $n=10$. The rumor spreads by a sequence of calls. A person can pass the rumor on to anyone except the person who just called them.
**(a) By how many different paths can a rumor travel through the group in three calls? In "n" calls?**
Let $P_i$ be the person who holds the rumor at the $i$-th step (after $i$ calls), with $P_0$ being the originator of the rumor.
For the first call, $P_0$ can call any of the $n-1$ other people. So there are $n-1$ possibilities for $P_1$.
For the second call, $P_1$ can call any of the $n-1$ people except $P_0$. So there are $n-1$ possibilities for $P_2$.
For the third call, $P_2$ can call any of the $n-1$ people except $P_1$. So there are $n-1$ possibilities for $P_3$.
The total number of different paths a rumor can travel through the group in three calls is the product of the number of choices at each step:
Number of paths in 3 calls = $(n-1) \times (n-1) \times (n-1) = (n-1)^3$.
For $n=10$, the number of different paths in three calls is $(10-1)^3 = 9^3 = 729$.
In "n" calls, let the sequence of people who hold the rumor be $P_0, P_1, P_2, \dots, P_n$.
Number of choices for $P_1$: $n-1$ (anyone except $P_0$)
Number of choices for $P_2$: $n-1$ (anyone except $P_1$)
...
Number of choices for $P_k$: $n-1$ (anyone except $P_{k-1}$)
...
Number of choices for $P_n$: $n-1$ (anyone except $P_{n-1}$)
The total number of different paths in $n$ calls is $(n-1) \times (n-1) \times \dots \times (n-1)$ ($n$ times) = $(n-1)^n$.
**(b) What is the probability that if A starts the rumor, A receives the third call?**
Let A be $P_0$. For A to receive the third call, $P_3$ must be A. The sequence of calls is $A \rightarrow P_1 \rightarrow P_2 \rightarrow A$.
Number of ways for this to happen:
- $P_1$ can be any of the $n-1$ people other than A.
- $P_2$ can be any of the $n-1$ people other than $P_1$.
- $P_3$ must be A (1 choice).
The number of paths where A receives the third call is $(n-1) \times (n-1) \times 1 = (n-1)^2$.
The total number of paths in three calls is $(n-1)^3$.
The probability that A receives the third call is $\frac{(n-1)^2}{(n-1)^3} = \frac{1}{n-1}$.
For $n=10$, the probability is $\frac{1}{10-1} = \frac{1}{9}$.
**(c) What is the probability that if A does not start the rumor, A receives the third call?**
Let the person who starts the rumor be S, where $S \neq A$. The sequence of calls is $S \rightarrow P_1 \rightarrow P_2 \rightarrow A$.
Number of ways for this to happen:
- $P_1$ can be any of the $n-1$ people other than S.
- $P_2$ can be any of the $n-1$ people other than $P_1$.
- $P_3$ must be A (1 choice).
However, we also need to ensure that $P_1 \neq A$ and $P_2 \neq S$.
Consider the total number of paths of length 3, which is $(n-1)^3$.
We need the number of paths $S \rightarrow P_1 \rightarrow P_2 \rightarrow A$ where $S \neq A$.
- $P_1$ can be any of the $n-1$ people other than S.
- $P_2$ can be any of the $n-1$ people other than $P_1$.
For the third call to be to A, $P_2$ must call A. This is 1 specific choice out of $n-1$ possible callers from $P_2$.
The number of sequences $S \rightarrow P_1 \rightarrow P_2$ where $S \neq A$ is $(n-1)(n-1)$. For each such sequence, the probability that $P_2$ calls A is $\frac{1}{n-1}$ (since $P_2 \neq P_1$).
The probability that A receives the third call is the sum of probabilities over all possible starting persons $S \neq A$. There are $n-1$ such starting persons.
Consider a specific path of length 3 ending at A: $S \rightarrow P_1 \rightarrow P_2 \rightarrow A$.
The probability of this specific path is $\frac{1}{n-1} \times \frac{1}{n-1} \times \frac{1}{n-1}$.
The number of such paths where $S \neq A$ is $(n-1)(n-2)$ for the first two calls. The third call must be to A (1 choice). So $(n-1)(n-2) \times 1$.
The probability is $\frac{(n-1)(n-2)}{(n-1)^3} = \frac{n-2}{(n-1)^2}$.
For $n=10$, the probability is $\frac{10-2}{(10-1)^2} = \frac{8}{81}$.
Final Answer: The final answer is $\boxed{(a) (n-1)^3, (n-1)^n; (b) 1/(n-1); (c) (n-2)/(n-1)^2}$
|
|
|
