Bounds and/or closed form for the “swerve numbers”?
$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?
sequences-and-series combinatorics game-theory
$endgroup$
add a comment |
$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?
sequences-and-series combinatorics game-theory
$endgroup$
add a comment |
$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?
sequences-and-series combinatorics game-theory
$endgroup$
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?
sequences-and-series combinatorics game-theory
sequences-and-series combinatorics game-theory
edited Jan 10 at 5:40
Ricky Tensor
asked Jan 10 at 5:32
Ricky TensorRicky Tensor
58819
58819
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$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
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3068275%2fbounds-and-or-closed-form-for-the-swerve-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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
add a comment |
$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
add a comment |
$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$
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.
answered Jan 10 at 18:21
Mike EarnestMike Earnest
23.9k12051
23.9k12051
$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
add a comment |
$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
$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 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$
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
$begingroup$
I think you are correct. $P(n)=2^n$. Thanks for the solution.
$endgroup$
– Ricky Tensor
Jan 11 at 21:17
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3068275%2fbounds-and-or-closed-form-for-the-swerve-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown