2
$\begingroup$

2 aliens walk on a line randomly. At each timestep they walk independently either left or right (1 meter) with equal probability. They start 10 meters apart. What's the probability that after 7 time steps they have met (passed through the same point)?

Hello,

I'm trying to solve this puzzle but I'm struggling. I know that there are $4^7$ states in the tree. If we imagine them being on a number line. Alien $A$ starting at $0$ and Alien $B$ starting at $10$. I know that they can only meet at points $3$-$7$.

I know that the probability of Alien $A$ getting to $3$ after $3$ time steps is $\frac{1}{8}$.

I don't really know where to go from here. Thank you for your suggestions.

$\endgroup$

closed as off-topic by Gareth McCaughan, boboquack, Gamow, Peregrine Rook, Rand al'Thor Mar 18 '17 at 0:48

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is off-topic as it appears to be a mathematics problem, as opposed to a mathematical puzzle. For more info, see "Are math-textbook-style problems on topic?" on meta." – Gareth McCaughan, boboquack, Gamow, Peregrine Rook, Rand al'Thor
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ they walk sideways? Or ahead and they go left/right after each step ? $\endgroup$ – Marius Mar 17 '17 at 20:36
  • $\begingroup$ Sideways. Like this ______<-A->_________________<-B->______ $\endgroup$ – Rupert Gatwick Mar 17 '17 at 20:49
  • 1
    $\begingroup$ this does not look much as a puzzle. Maybe you have more luck with it here: math.stackexchange.com $\endgroup$ – Marius Mar 17 '17 at 21:37
2
$\begingroup$

Let's start by tracing the probabilities with a single alien:

At the 1st step, he might be at positions $+1$ or $-1$ with $1/2$ probability each.
At the 2nd step, $-2$ ($1/4$), $0$ ($2/4$) or $+2$ ($1/4$).
At the 3rd step, $-3$ ($1/8$), $-1$ ($3/8$), $+1$ ($3/8$), $+3$ ($1/8$).
At the 4th step, $-4$ ($1/16$), $-2$ ($4/16$), $0$ ($6/16$), $+2$ ($4/16$), $+4$ ($1/16$).
At the 5th step, $-5$ ($1/32$), $-3$ ($5/32$), $-1$ ($10/32$), $+1$ ($10/32$), $+3$ ($5/32$), $+5$ ($1/32$).
At the 6th step, $-6$ ($1/64$), $-4$ ($6/64$), $-2$ ($15/64$), $0$ ($20/64$), $+2$ ($15/64$), $+4$ ($6/64$), $+6$ ($1/64$).
At the 7th step, $-7$ ($1/128$), $-5$ ($7/128$), $-3$ ($21/128$), $-1$ ($35/128$), $+1$ ($35/128$), $+3$ ($21/128$), $+5$ ($7/128$), $+7$ ($1/128$).

This can easily be seen when you build:

a triangle with a number 1 in the top and filling each row below it with the sum of the two numbers above.

Like this:

triangle
Each line has a position from $-7$ to $+7$ (the horizontal positions) and the probability of the alien being in that position is expressed as $\frac{x}{2^y}$, where $x$ is the number in the table for the step $y$. Blanks should be considered as $x = 0$.

Now, let's see where the two aliens might meet:

  • [a]

    At the 5th step with $+5$ and $-5$, coming from $+4$ and $-4$ with a probability of $\frac{1}{32} \times \frac{1}{32} = \frac{1}{1024}$.

    Note that:

    At the 6th step with $+6$ and $-6$, coming from $+5$ and $-5$ they would already had met at the 5th step;

  • [b]

    At the 6th step with $+6$ and $-4$ coming from $+5$ and $-3$. This gives a probability of $\frac{1}{64} \times \frac{5}{64} = \frac{5}{4096}$;

  • [c]

    The opposite of [b];

  • [d]

    At the 7th step, having the 5th as $+5$ and $-3$, 6th as $+6$ and $-2$ and 7th as $+7$ and $-3$;

  • [e]

    At the 7th step, having the 5th as $+5$ and $-3$, 6th as $+4$ and $-4$ and 7th as $+5$ and $-5$;

  • [f]

    At the 7th step, having the 5th as $+3$ and $-3$, 6th as $+4$ and $-4$ and 7th as $+5$ and $-5$;

  • [g]

    opposite of [d];

  • [h]

    opposite of [e].

For cases d, e, g and h, the probabilities of reaching the 5th step are calculated as:

$\frac{1}{32} \times \frac{5}{32} = \frac{5}{1024}$ for each.

For case f, the proability of reaching the 5th step is:

$\frac{5}{32} \times \frac{5}{32} = \frac{25}{1024}$

Each one of the cases d to h depend on exacts two steps performed by each of the aliens, so...

... we multiply each of those probabilities by $\frac{1}{16}$, because we have four steps to do, each one having $\frac{1}{2}$ of probability of happening.

This gives the probabilities as:

$ P = p_a + p_b + p_c + p_d \times \frac{1}{16} + p_e \times \frac{1}{16} + p_f \times \frac{1}{16} + p_g \times \frac{1}{16} + p_h \times \frac{1}{16}$

However...

Given that $p_b = p_c$ and that $p_d = p_e = p_g = p_h$, then $p_b + p_c = 2 p_b$ and $p_d + p_e + p_g + p_h = 4 p_d$ and we can simplify the formula to:

$P = p_a + 2 p_b + 4 p_d \times \frac{1}{16} + p_f$

Now, we can solve this as...

$$ \begin{align} P & = p_a + 2 p_b + 4 p_d \times \frac{1}{16} + p_f \\ & = \frac{1}{1024} + 2 \times \frac{5}{4096} + 4 \times \frac{5}{1024} \times \frac{1}{16} + \frac{25}{1024} \times \frac{1}{16} \\ & = \frac{16}{16384} + \frac{40}{16384} + \frac{20}{16384} + \frac{25}{16384} \\ & = ... \end{align}$$

And the final result is...

$$P = \frac{101}{16384}$$

And a final curiosity:

The aliens are always separated by an even number of meters. This also ensures that if they meet, they will collide and not pass one through the other swapping their positions.

$\endgroup$
  • $\begingroup$ Oh, you typed all that math on phone? :-O Cool! $\endgroup$ – Techidiot Mar 18 '17 at 2:57
  • $\begingroup$ @Techidiot Yes. And posting answers in SE using cellphones is an exercise of torture, specially when they feature math. Now that I am at my notebook, I edited the answer severely to put it in a more adequate format. $\endgroup$ – Victor Stafusa Mar 18 '17 at 11:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.