2
$\begingroup$

You've probably experienced this: You're walking down a hallway when you notice you're on a collision course with somebody. Both of you swerve in one direction. Then you both swerve in the opposite direction. Repeat.

As embarrassing as such incidents are, they could be easily solved by just having everyone agree to always keep to the right. But creatures living on a Möbius strip or other non-orientable manifold have it much harder. Even if all such creatures agreed amongst themselves to always keep to the right, they would still bump into one another with alarming frequency. A better solution is required.

To formalize the problem, let's suppose that two creatures heading towards each other always notice that they are one a collision course when they are the same distance away. Thus, they will be always be allowed some number, $n$, of swerves, before colliding painfully with one another. Let us refer to the side of the hallway along which both creatures were originally walking as $A$, and let us call the opposite side $B$. Then the creatures play $n$ rounds of a game where both creatures simultaneously choose an element of $\{A, B\}$. As long as the creatures choose differently by the last round, disaster is averted. If the creatures both make the same choice in every single round, however, they both lose. We will assume that all creatures are allowed to confer with each other to agree on a strategy beforehand. This strategy must win with certainty for all possible pairs of creatures encountering each other. Finally, we assume anonymity: The creatures all look alike, and so cannot recognize each other by their faces. Any information about each other's identity must be gleaned from the pattern of their swerving. (This eliminates a promising strategy: assign an ordering to the creatures, and have the higher creature in the ordering play $A$, while the lower plays $B$.)

For example, when $n=1$, one round is played. The creatures must play $(A, B)$ or $(B, A)$ in order to win. The losing plays are $(A, A)$ where both hold their course, and $(B, B)$ where both swerve.

If $n=1$, then 2 creatures can win by letting creature 1 always play $A$, and creature 2 always play $B$.

If there are 3 creatures and $n=1$, there is no winning strategy. Probabilistic strategies are out: we must win with certainty. But this means that on the opening move, each creature must always play the same move. (By anonymity, there is no way for it to shake things up by playing different moves when faced with different creatures.) Since there are 3 creatures, and only 2 opening moves, we can match up two creatures with the same opening move against each other, and they will collide.

Thus when $n=1$, the maximum number of creatures that can be guaranteed to not collide with each other is 2. We call this number $P(n)$ in general. (If for some $n$, an arbitrary number of creatures can be guaranteed not to collide with each other, then we say $P(n)=\infty$. The sequence defined by $P$ is the "swerve number sequence" defined in the title.)

So far, we know that $P(1)=2$. I will now give a lower bound on $P(n)$.

$$ P(n) \geq 2^n $$

Strategy for $2^n$: Assign each creature a unique binary string of length $n$. (So all strings are used exactly once.) Each creature's strategy is then to literally play the sequence of $A$s and $B$s corresponding to its own string. Since the strings are unique, every pair of creatures will differ on at least one turn. Therefore this is a winning strategy.

So here is my question: Can anyone determine any more terms of the sequence $P(n)$, or give an upper bound, or a tighter lower bound, or best of all, a closed form expression?

$\endgroup$
1
$\begingroup$

The same argument you used to show $P(1)=2$ can be used to show $P(n)=2^n$. Since people can only base their choices on their own identities, and not that of their opponents, their strategy must correspond to a string of $n$ symbols $X_1,X_2,\dots,X_n$, each equal to $A$ or $B$. This means that if they crash $k$ times, the next move they will try is $X_{k+1}$. Since there are only $2^n$ possible strategies (as you said, randomness is useless), if there were more than $2^n$ people, there would have to be two people who used the same strategy, and they would crash if they were the first pair of people to meet.

$\endgroup$
  • $\begingroup$ The flaw here is that people can base their strategies in later moves on what the other person does in their earlier moves. This gives more than $2^n$ possible strategies. For example, when $n=2$, playing $A$ first, and then playing the opposite of whatever your opponent played is a strategy. $\endgroup$ – Ricky Tensor Jan 11 at 5:00
  • $\begingroup$ The strategy you just described is given by $X_1=A$, $X_2=B$, so is one of the $2^2$ strategies I described. If you start by playing $A$, and then do the opposite of what your opponent just did, that means you will now do $B$, since the second move would only come up if your opponent's first move was $A$. @RickyTensor $\endgroup$ – Mike Earnest Jan 11 at 18:35
  • $\begingroup$ I think you are correct. $P(n)=2^n$. Thanks for the solution. $\endgroup$ – Ricky Tensor Jan 11 at 21:17

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.