Looking for a strategy for finding each other in a crowd, is it better to have one person move and one person stay put, or have both people move?

Suppose we have a $n$ by $n$ grid of squares. Each person begins on a random square. If a person decides to move, then every second, they move 1 square in a random direction, excluding the direction bringing the person to the square they were previously on. If at some time, both people are on the same square, we are done. We want to compare the expected meeting time of either strategy.

This is like a random walk on $\mathbb{Z}^2$, but the boundedness prevents us from taking the difference of their positions and considering that as another random walk. This is also like a random walk on a graph, but the random direction depends not just on the current square, but also the previous one.

  • 1
    $\begingroup$ Now that everyone has a phone handy, this question has lost some of its motivation. $\endgroup$ – Gerry Myerson Dec 2 at 11:41
  • 1
    $\begingroup$ Alas, as we become dependent, and batteries die, we may be forced to drastic measures ;) $\endgroup$ – Kiochi Dec 2 at 11:42
  • $\begingroup$ I bring a chair, stand on it briefly and wave , and then sit and wait for the other person to get to me. Gerhard "Uses Vertical And Lateral Thinking" Paseman, 2019.12.02. $\endgroup$ – Gerhard Paseman Dec 2 at 16:05

Not an answer, but a long comment: Consider $n=2$. In this case there are only 2 possibilities (up to symmetry) for start position, "adjacent" and "diagonal".

One Moves, One stays put.

Diagonal: In any case, they meet in 2 moves.

Adjacent: In one case they meet in 3 moves, in one case 1 moves.

Both move.

Diagonal: In one case, they meet in 1 move, in other case they never meet .

Adjacent: In both cases, they never meet. (Although in one case, they "pass" each other while swapping adjacent squares; in the other they are "chasing each other's tails".)

Thus it seems clear that, at least for some $n$ (the example of 2) it is better for only one to move.

For $n>2$, neither strategy will guarantee that the two meet, since now there is more "room" for one or both people to move back and forth without intersecting.

  • 2
    $\begingroup$ This answers it for all even n, because if they meet in a larger square, then they must meet mod 2, and the dynamics are the same as in this case. $\endgroup$ – Gabe K Dec 2 at 13:32
  • $\begingroup$ @Gabe K I'm not sure it's quite the same in such a case, because if n>2, even if they meet in a 2x2, square, they can leave this smaller square. So we no longer have the guarantee they meet in case only one moves, for example. $\endgroup$ – Kiochi Dec 3 at 13:23
  • $\begingroup$ That is true. For larger squares it will take longer. However, you have shown there are cases where they never meet mod 2 if both move, which means that they also never meet in the larger square. In those cases only one person should move. $\endgroup$ – Gabe K Dec 3 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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