document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1168178>Question 1168178</A>: <I><SPAN STYLE=\"word-break: break-all;\"> 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? </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #851669 by </B><A HREF=/tutors/aboutme.mpl?userid=CPhill><B>CPhill(1959)</B></A><img src=\"/images/stars/stars-12.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=CPhill><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/cgi-bin/show-face.mpl?user=CPhill><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=851669\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> 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.\r<BR>\n" );
document.write( "\n" );
document.write( "**(a) By how many different paths can a rumor travel through the group in three calls? In \"n\" calls?**\r<BR>\n" );
document.write( "\n" );
document.write( "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.\r<BR>\n" );
document.write( "\n" );
document.write( "For the first call, $P_0$ can call any of the $n-1$ other people. So there are $n-1$ possibilities for $P_1$.\r<BR>\n" );
document.write( "\n" );
document.write( "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$.\r<BR>\n" );
document.write( "\n" );
document.write( "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$.\r<BR>\n" );
document.write( "\n" );
document.write( "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:<BR>\n" );
document.write( "Number of paths in 3 calls = $(n-1) \times (n-1) \times (n-1) = (n-1)^3$.\r<BR>\n" );
document.write( "\n" );
document.write( "For $n=10$, the number of different paths in three calls is $(10-1)^3 = 9^3 = 729$.\r<BR>\n" );
document.write( "\n" );
document.write( "In \"n\" calls, let the sequence of people who hold the rumor be $P_0, P_1, P_2, \dots, P_n$.<BR>\n" );
document.write( "Number of choices for $P_1$: $n-1$ (anyone except $P_0$)<BR>\n" );
document.write( "Number of choices for $P_2$: $n-1$ (anyone except $P_1$)<BR>\n" );
document.write( "...<BR>\n" );
document.write( "Number of choices for $P_k$: $n-1$ (anyone except $P_{k-1}$)<BR>\n" );
document.write( "...<BR>\n" );
document.write( "Number of choices for $P_n$: $n-1$ (anyone except $P_{n-1}$)\r<BR>\n" );
document.write( "\n" );
document.write( "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$.\r<BR>\n" );
document.write( "\n" );
document.write( "**(b) What is the probability that if A starts the rumor, A receives the third call?**\r<BR>\n" );
document.write( "\n" );
document.write( "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$.<BR>\n" );
document.write( "Number of ways for this to happen:<BR>\n" );
document.write( "- $P_1$ can be any of the $n-1$ people other than A.<BR>\n" );
document.write( "- $P_2$ can be any of the $n-1$ people other than $P_1$.<BR>\n" );
document.write( "- $P_3$ must be A (1 choice).<BR>\n" );
document.write( "The number of paths where A receives the third call is $(n-1) \times (n-1) \times 1 = (n-1)^2$.<BR>\n" );
document.write( "The total number of paths in three calls is $(n-1)^3$.<BR>\n" );
document.write( "The probability that A receives the third call is $\frac{(n-1)^2}{(n-1)^3} = \frac{1}{n-1}$.<BR>\n" );
document.write( "For $n=10$, the probability is $\frac{1}{10-1} = \frac{1}{9}$.\r<BR>\n" );
document.write( "\n" );
document.write( "**(c) What is the probability that if A does not start the rumor, A receives the third call?**\r<BR>\n" );
document.write( "\n" );
document.write( "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$.<BR>\n" );
document.write( "Number of ways for this to happen:<BR>\n" );
document.write( "- $P_1$ can be any of the $n-1$ people other than S.<BR>\n" );
document.write( "- $P_2$ can be any of the $n-1$ people other than $P_1$.<BR>\n" );
document.write( "- $P_3$ must be A (1 choice).<BR>\n" );
document.write( "However, we also need to ensure that $P_1 \neq A$ and $P_2 \neq S$.\r<BR>\n" );
document.write( "\n" );
document.write( "Consider the total number of paths of length 3, which is $(n-1)^3$.<BR>\n" );
document.write( "We need the number of paths $S \rightarrow P_1 \rightarrow P_2 \rightarrow A$ where $S \neq A$.<BR>\n" );
document.write( "- $P_1$ can be any of the $n-1$ people other than S.<BR>\n" );
document.write( "- $P_2$ can be any of the $n-1$ people other than $P_1$.<BR>\n" );
document.write( "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$.\r<BR>\n" );
document.write( "\n" );
document.write( "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$).<BR>\n" );
document.write( "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.\r<BR>\n" );
document.write( "\n" );
document.write( "Consider a specific path of length 3 ending at A: $S \rightarrow P_1 \rightarrow P_2 \rightarrow A$.<BR>\n" );
document.write( "The probability of this specific path is $\frac{1}{n-1} \times \frac{1}{n-1} \times \frac{1}{n-1}$.<BR>\n" );
document.write( "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$.<BR>\n" );
document.write( "The probability is $\frac{(n-1)(n-2)}{(n-1)^3} = \frac{n-2}{(n-1)^2}$.<BR>\n" );
document.write( "For $n=10$, the probability is $\frac{10-2}{(10-1)^2} = \frac{8}{81}$.\r<BR>\n" );
document.write( "\n" );
document.write( "Final Answer: The final answer is $\boxed{(a) (n-1)^3, (n-1)^n; (b) 1/(n-1); (c) (n-2)/(n-1)^2}$ </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );