Bounds and/or closed form for the “swerve numbers”?












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?










share|cite|improve this question











$endgroup$

















    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?










    share|cite|improve this question











    $endgroup$















      2












      2








      2


      0



      $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?










      share|cite|improve this question











      $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






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Jan 10 at 5:40







      Ricky Tensor

















      asked Jan 10 at 5:32









      Ricky TensorRicky Tensor

      58819




      58819






















          1 Answer
          1






          active

          oldest

          votes


















          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.






          share|cite|improve this answer









          $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





          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
          });


          }
          });














          draft saved

          draft discarded


















          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









          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.






          share|cite|improve this answer









          $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
















          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.






          share|cite|improve this answer









          $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














          1












          1








          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.






          share|cite|improve this answer









          $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.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          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


















          • $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


















          draft saved

          draft discarded




















































          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.




          draft saved


          draft discarded














          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





















































          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







          Popular posts from this blog

          Human spaceflight

          Can not write log (Is /dev/pts mounted?) - openpty in Ubuntu-on-Windows?

          張江高科駅