5

Let $~A_1 = (0,0), ~~A_2 = (1,0),~~ A_3 = (1,1)~$ and $~A_4 = (0,1)~$ be the four vertices of a square.

A particle starts from the point $~A_1~$ at time $~0~$ and moves either to $~A_2~$ or to $~A_4~$ with equal probability.

Similarly, in each of the subsequent steps, it randomly chooses one of its adjacent vertices and moves there. Let $~T~$ be the minimum number of steps required to cover all four vertices. The probability $~P(T = 4)~$ is

$(A) ~~~~0$

$(B) ~~~~\frac{1}{16}$

$(C) ~~~~\frac{1}{8}$

$(D) ~~~~\frac{1}{4}$

I am getting it as $~\frac{3}{4}~$ but answer is $~\frac{1}{8}~$ please help!

nmasanta
  • 9,222
debdutt
  • 137

2 Answers2

5

To have $4$ steps, it means it visited exactly one node twice and we can check that the repeated node must be $1$.

It could have been $12143$ or $14123$.

Hence $\frac{2}{2^4}=\frac18$

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • How are you labelling the nodes? – coffeemath Jan 01 '19 at 09:26
  • 1
    oops, I see. i made a mistake. thanks. – Siong Thye Goh Jan 01 '19 at 09:30
  • @SiongThyeGoh, why 1 need to be visited twice? Can u please explain , why r u taking only 2 outcomes among 16 outcomes? – Srestha Jun 20 '19 at 12:32
  • Suppose we begin from $1$, and fix the next move to be $2$, and suppose you purposely visit $3$, if you visit $4$ directly, you will end up with $T=3$. If from $3$, you visit $2$, and then carry on again, the distance would be more than than $4$. Hence we know starting from $12$, the next move must be $1$ again. Similarly for the other direction. – Siong Thye Goh Jun 20 '19 at 12:42
  • @SiongThyeGoh, if we move 1234 and visit no repeated vertex , then what will be the problem? – Srestha Jun 20 '19 at 13:18
  • then $T=3$ isn't it. – Siong Thye Goh Jun 20 '19 at 13:20
  • @SiongThyeGoh ok, but they are asking for "minimum number of steps required to cover all four vertices"-Now, if we repeat some vertex, then will it be minimum number of steps? – Srestha Jun 20 '19 at 13:51
  • 1
    you are misunderstanding the question, the question is asking about the time when we first visited all distinct vertices. It can be $3, 4$ or even more. what is the probability that when we visit $4$ vertices, we took $4$ steps. – Siong Thye Goh Jun 20 '19 at 14:07
  • Thank you, Now I got it :) – Srestha Jun 20 '19 at 14:11
1

The only two favorable outcomes are: $12143$ and $14123$. Each has the probability of $1/16$, hence their sum is $1/8$.

farruhota
  • 31,482