An invisible ghost jumping on a regular hexagon

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
13
down vote

favorite
3












Given a regular hexagon and an invisible ghost at one of the vertices of the hexagon (we don’t know which). We have a special gun, that can kill ghosts. In a step we are able to shoot the gun twice (i.e. choose two vertices and see if the ghost is there). After every step, the gost moves to an adjacent vertex. What is the minimum number of moves required to kill the ghost?



I have an example with 6 steps. I am sure this is not the minimum. My friend has an example for 4. So what is the minimum? And can you generalize for a regular $n$-gon? Thanks!




combinatorics combinatorial-game-theory extremal-combinatorics




share|cite|improve this question

















  • 3




    The minimum is $1$, we could hit the ghost immediately.
    – Servaes
    Aug 1 at 12:19










  • This 'minimum' is also easily verified to be at least $4$.
    – Servaes
    Aug 1 at 12:43






  • 17




    You should provide your $6$-step solution, and your friend's $4$-step solution, so that answerers do not duplicate your effort.
    – Blue
    Aug 1 at 13:33














up vote
13
down vote

favorite
3












Given a regular hexagon and an invisible ghost at one of the vertices of the hexagon (we don’t know which). We have a special gun, that can kill ghosts. In a step we are able to shoot the gun twice (i.e. choose two vertices and see if the ghost is there). After every step, the gost moves to an adjacent vertex. What is the minimum number of moves required to kill the ghost?



I have an example with 6 steps. I am sure this is not the minimum. My friend has an example for 4. So what is the minimum? And can you generalize for a regular $n$-gon? Thanks!




combinatorics combinatorial-game-theory extremal-combinatorics




share|cite|improve this question

















  • 3




    The minimum is $1$, we could hit the ghost immediately.
    – Servaes
    Aug 1 at 12:19










  • This 'minimum' is also easily verified to be at least $4$.
    – Servaes
    Aug 1 at 12:43






  • 17




    You should provide your $6$-step solution, and your friend's $4$-step solution, so that answerers do not duplicate your effort.
    – Blue
    Aug 1 at 13:33












up vote
13
down vote

favorite
3









up vote
13
down vote

favorite
3






3





Given a regular hexagon and an invisible ghost at one of the vertices of the hexagon (we don’t know which). We have a special gun, that can kill ghosts. In a step we are able to shoot the gun twice (i.e. choose two vertices and see if the ghost is there). After every step, the gost moves to an adjacent vertex. What is the minimum number of moves required to kill the ghost?



I have an example with 6 steps. I am sure this is not the minimum. My friend has an example for 4. So what is the minimum? And can you generalize for a regular $n$-gon? Thanks!




combinatorics combinatorial-game-theory extremal-combinatorics




share|cite|improve this question













Given a regular hexagon and an invisible ghost at one of the vertices of the hexagon (we don’t know which). We have a special gun, that can kill ghosts. In a step we are able to shoot the gun twice (i.e. choose two vertices and see if the ghost is there). After every step, the gost moves to an adjacent vertex. What is the minimum number of moves required to kill the ghost?



I have an example with 6 steps. I am sure this is not the minimum. My friend has an example for 4. So what is the minimum? And can you generalize for a regular $n$-gon? Thanks!





combinatorics combinatorial-game-theory extremal-combinatorics





share|cite|improve this question












share|cite|improve this question




share|cite|improve this question








edited Aug 1 at 13:38









Batominovski

22.7k22776




22.7k22776









asked Aug 1 at 11:57









Leo Gardner

35411




35411







  • 3




    The minimum is $1$, we could hit the ghost immediately.
    – Servaes
    Aug 1 at 12:19










  • This 'minimum' is also easily verified to be at least $4$.
    – Servaes
    Aug 1 at 12:43






  • 17




    You should provide your $6$-step solution, and your friend's $4$-step solution, so that answerers do not duplicate your effort.
    – Blue
    Aug 1 at 13:33












  • 3




    The minimum is $1$, we could hit the ghost immediately.
    – Servaes
    Aug 1 at 12:19










  • This 'minimum' is also easily verified to be at least $4$.
    – Servaes
    Aug 1 at 12:43






  • 17




    You should provide your $6$-step solution, and your friend's $4$-step solution, so that answerers do not duplicate your effort.
    – Blue
    Aug 1 at 13:33







3




3




The minimum is $1$, we could hit the ghost immediately.
– Servaes
Aug 1 at 12:19




The minimum is $1$, we could hit the ghost immediately.
– Servaes
Aug 1 at 12:19












This 'minimum' is also easily verified to be at least $4$.
– Servaes
Aug 1 at 12:43




This 'minimum' is also easily verified to be at least $4$.
– Servaes
Aug 1 at 12:43




17




17




You should provide your $6$-step solution, and your friend's $4$-step solution, so that answerers do not duplicate your effort.
– Blue
Aug 1 at 13:33




You should provide your $6$-step solution, and your friend's $4$-step solution, so that answerers do not duplicate your effort.
– Blue
Aug 1 at 13:33










3 Answers
3






active

oldest

votes

















up vote
12
down vote



accepted










For an $n$-gon, the answer is $n-2$ if $n$ is even and $n-1$ if $n$ is odd (with the exceptions $n=0,1,2$).



Let $S$ be the set of possible vertices that the ghost is on.



When you shoot, the number of possible positions for the ghost decreases by (at most) 2.



When the ghost moves, the number of possible positions for the ghost increases by at least 1 unless all vertices one to the right of one of the elements of $S$ are also one to the left of one of the vertices of one of the elements of $S$. This case can only happen if $n$ is even and every other vertex is in $S$ (another possibility is that S consists of all vertices, but that won't be the case after shooting).



Therefore, after you shoot and the ghost moves, the size of $S$ decreases by at most 1 except in the case that $n$ is even and the possible positions for the ghost are every other vertex. This can only occur if the size of $S$ is $n/2$, so if the size is decreasing after every shoot it will only occur once. This proves that $n-1$ is a lower bound for the number of shots required if $n$ is odd, and that $n-2$ is a lower bound if $n$ is even.



It remains to show that these bounds are achievable. To do this, number the vertices from $-k$ to $k$ if $n$ is odd (so $k=(n-1)/2$) and number them from $-k$ to $k+1$ if $n$ is even (so $k=(n-2)/2$). The algorithm is as follows:



Shoot 1 and -1.



Shoot 2 and -2.



.



.



.



Shoot $i$ and $-i$.



.



.



.



Shoot $k-1$ and $-(k-1)$.



Shoot $k$ and $-k$.



Shoot $k$ and $-k$.



Shoot $k-1$ and $-(k-1)$.



.



.



.



Shoot 2 and -2.



Shoot 1 and -1.



Done.



This takes $2k$ steps, as desired.






share|cite|improve this answer






























    up vote
    15
    down vote













    Brute force exhaustion of possible strategies gives two solutions requiring four turns:



    • Shoot at $(1,3)$ then $(4,6)$ then $(2,4)$ then $(1,5)$

    • Shoot at $(1,3)$ then $(4,6)$ then $(4,6)$ then $(1,3)$

    along with reflections and rotations of these basic solutions. There are none requiring three turns.



    To see that the second solution works, we can use the following method to analyze the locations where there could possibly be a live ghost:



    • The ghost is among $1,2,3,4,5,6$. After shooting $(1,3)$, the ghost is among $2,4,5,6$.

    • The ghost is among $1,3,4,5,6$. After shooting $(4,6)$, the ghost is among $1,3,5$.

    • The ghost is among $2,4,6$. After shooting $(4,6)$, the ghost is at $2$.

    • The ghost is among $1,3$. After shooting $(1,3)$, it can't be anywhere.





    share|cite|improve this answer




























      up vote
      8
      down vote













      I shall prove that five moves are sufficient (for a hexagon), and believe that we need at least five moves. Let $ABCDEF$ be the hexagon, arranged in the counterclockwise order.



      In each of the first two moves, shoot the gun at the vertices $B$ and $F$. If the ghost is not killed by now, then it must be somewhere amongst $C$, $D$, and $E$. Then, in each of the next two moves, shoot the gun at the vertices $C$ and $E$. Since the ghost cannot be at $D$ consecutively, either it is finally killed or its location is now $A$. Then, we point the gun at $B$ and $F$ again. this strategy guarantees that the ghost is dead (well, twice dead, because being a ghost means it has died before).



      Since Hurkyl already provided a $4$-step solution, I am proving that there does not exist a foolproof strategy with $3$ moves. When the first move is made, we suppose for now that at least three consecutive vertices, say, $A$, $B$, and $C$, are not harmed. Therefore, if there exists a $3$-step strategy to kill the ghost, the next two moves will kill the ghost, even when the ghost starts at somewhere amongst $A$, $B$, and $C$.



      The second move will have to involve at least one of the vertices $A$, $B$, and $C$; otherwise the last move will leave at least one vertex of the three untouched, and the ghost can survive. Without loss of generality, the second move hits $A$ or $B$.



      1. Both $A$ and $B$ are gunned down in the second move. Then, to survive, the ghost must be at $C$, or it has already left area $A$, $B$, and $C$ entirely. In this case, the third move may do no harm to the ghost. (If the ghost is at $C$, then we have to kill $B$ and $D$; nonetheless, the ghost could also be at $D$ then move to $C$, where this last move will not succeed.)

      2. The second move hits $A$ and some vertex $Xnotin A,B,C$. To survive, the ghost can be at vertex $B$, $C$, or $D$ just before the second move is made. Then again, there are too many options to survive for the ghost, as prior to the third move, it can be anywhere from $A$, $B$, $C$, and $D$.

      3. The second move hits $B$ and some vertex $Xnotin A,B,C$. If the ghost survives both the first and the second murder attempts, it must have originally been at $B$, and then move to $A$ or $C$ prior to the second move. Thus, by the third move, the ghost can be anywhere amongst $F$, $B$, and $D$, and hitting two vertices will not secure the mission.

      Now, we shall deal with the case that the first move hits two opposite vertices, say, $A$ and $D$. Then, prior to the second move, the ghost can be anywhere on the hexagon. Therefore, the second move will leave at least two adjacent vertices untouched. Before the third move, the ghost will now have at least four places to be.






      share|cite|improve this answer























      • Nice solution!$$
        – quasi
        Aug 1 at 13:29






      • 1




        I made a flow chart of your algorithm in paragraph 2: imgur.com/Ech54cQ
        – Burnsba
        Aug 1 at 16:02










      • @Burnsba Thanks! The ghost is lovely.
        – Batominovski
        Aug 1 at 16:10










      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',
      convertImagesToLinks: true,
      noModals: false,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      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%2f2869002%2fan-invisible-ghost-jumping-on-a-regular-hexagon%23new-answer', 'question_page');

      );

      Post as a guest

















      3 Answers
      3






      active

      oldest

      votes








      3 Answers
      3






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes








      up vote
      12
      down vote



      accepted










      For an $n$-gon, the answer is $n-2$ if $n$ is even and $n-1$ if $n$ is odd (with the exceptions $n=0,1,2$).



      Let $S$ be the set of possible vertices that the ghost is on.



      When you shoot, the number of possible positions for the ghost decreases by (at most) 2.



      When the ghost moves, the number of possible positions for the ghost increases by at least 1 unless all vertices one to the right of one of the elements of $S$ are also one to the left of one of the vertices of one of the elements of $S$. This case can only happen if $n$ is even and every other vertex is in $S$ (another possibility is that S consists of all vertices, but that won't be the case after shooting).



      Therefore, after you shoot and the ghost moves, the size of $S$ decreases by at most 1 except in the case that $n$ is even and the possible positions for the ghost are every other vertex. This can only occur if the size of $S$ is $n/2$, so if the size is decreasing after every shoot it will only occur once. This proves that $n-1$ is a lower bound for the number of shots required if $n$ is odd, and that $n-2$ is a lower bound if $n$ is even.



      It remains to show that these bounds are achievable. To do this, number the vertices from $-k$ to $k$ if $n$ is odd (so $k=(n-1)/2$) and number them from $-k$ to $k+1$ if $n$ is even (so $k=(n-2)/2$). The algorithm is as follows:



      Shoot 1 and -1.



      Shoot 2 and -2.



      .



      .



      .



      Shoot $i$ and $-i$.



      .



      .



      .



      Shoot $k-1$ and $-(k-1)$.



      Shoot $k$ and $-k$.



      Shoot $k$ and $-k$.



      Shoot $k-1$ and $-(k-1)$.



      .



      .



      .



      Shoot 2 and -2.



      Shoot 1 and -1.



      Done.



      This takes $2k$ steps, as desired.






      share|cite|improve this answer



























        up vote
        12
        down vote



        accepted










        For an $n$-gon, the answer is $n-2$ if $n$ is even and $n-1$ if $n$ is odd (with the exceptions $n=0,1,2$).



        Let $S$ be the set of possible vertices that the ghost is on.



        When you shoot, the number of possible positions for the ghost decreases by (at most) 2.



        When the ghost moves, the number of possible positions for the ghost increases by at least 1 unless all vertices one to the right of one of the elements of $S$ are also one to the left of one of the vertices of one of the elements of $S$. This case can only happen if $n$ is even and every other vertex is in $S$ (another possibility is that S consists of all vertices, but that won't be the case after shooting).



        Therefore, after you shoot and the ghost moves, the size of $S$ decreases by at most 1 except in the case that $n$ is even and the possible positions for the ghost are every other vertex. This can only occur if the size of $S$ is $n/2$, so if the size is decreasing after every shoot it will only occur once. This proves that $n-1$ is a lower bound for the number of shots required if $n$ is odd, and that $n-2$ is a lower bound if $n$ is even.



        It remains to show that these bounds are achievable. To do this, number the vertices from $-k$ to $k$ if $n$ is odd (so $k=(n-1)/2$) and number them from $-k$ to $k+1$ if $n$ is even (so $k=(n-2)/2$). The algorithm is as follows:



        Shoot 1 and -1.



        Shoot 2 and -2.



        .



        .



        .



        Shoot $i$ and $-i$.



        .



        .



        .



        Shoot $k-1$ and $-(k-1)$.



        Shoot $k$ and $-k$.



        Shoot $k$ and $-k$.



        Shoot $k-1$ and $-(k-1)$.



        .



        .



        .



        Shoot 2 and -2.



        Shoot 1 and -1.



        Done.



        This takes $2k$ steps, as desired.






        share|cite|improve this answer

























          up vote
          12
          down vote



          accepted







          up vote
          12
          down vote



          accepted






          For an $n$-gon, the answer is $n-2$ if $n$ is even and $n-1$ if $n$ is odd (with the exceptions $n=0,1,2$).



          Let $S$ be the set of possible vertices that the ghost is on.



          When you shoot, the number of possible positions for the ghost decreases by (at most) 2.



          When the ghost moves, the number of possible positions for the ghost increases by at least 1 unless all vertices one to the right of one of the elements of $S$ are also one to the left of one of the vertices of one of the elements of $S$. This case can only happen if $n$ is even and every other vertex is in $S$ (another possibility is that S consists of all vertices, but that won't be the case after shooting).



          Therefore, after you shoot and the ghost moves, the size of $S$ decreases by at most 1 except in the case that $n$ is even and the possible positions for the ghost are every other vertex. This can only occur if the size of $S$ is $n/2$, so if the size is decreasing after every shoot it will only occur once. This proves that $n-1$ is a lower bound for the number of shots required if $n$ is odd, and that $n-2$ is a lower bound if $n$ is even.



          It remains to show that these bounds are achievable. To do this, number the vertices from $-k$ to $k$ if $n$ is odd (so $k=(n-1)/2$) and number them from $-k$ to $k+1$ if $n$ is even (so $k=(n-2)/2$). The algorithm is as follows:



          Shoot 1 and -1.



          Shoot 2 and -2.



          .



          .



          .



          Shoot $i$ and $-i$.



          .



          .



          .



          Shoot $k-1$ and $-(k-1)$.



          Shoot $k$ and $-k$.



          Shoot $k$ and $-k$.



          Shoot $k-1$ and $-(k-1)$.



          .



          .



          .



          Shoot 2 and -2.



          Shoot 1 and -1.



          Done.



          This takes $2k$ steps, as desired.






          share|cite|improve this answer















          For an $n$-gon, the answer is $n-2$ if $n$ is even and $n-1$ if $n$ is odd (with the exceptions $n=0,1,2$).



          Let $S$ be the set of possible vertices that the ghost is on.



          When you shoot, the number of possible positions for the ghost decreases by (at most) 2.



          When the ghost moves, the number of possible positions for the ghost increases by at least 1 unless all vertices one to the right of one of the elements of $S$ are also one to the left of one of the vertices of one of the elements of $S$. This case can only happen if $n$ is even and every other vertex is in $S$ (another possibility is that S consists of all vertices, but that won't be the case after shooting).



          Therefore, after you shoot and the ghost moves, the size of $S$ decreases by at most 1 except in the case that $n$ is even and the possible positions for the ghost are every other vertex. This can only occur if the size of $S$ is $n/2$, so if the size is decreasing after every shoot it will only occur once. This proves that $n-1$ is a lower bound for the number of shots required if $n$ is odd, and that $n-2$ is a lower bound if $n$ is even.



          It remains to show that these bounds are achievable. To do this, number the vertices from $-k$ to $k$ if $n$ is odd (so $k=(n-1)/2$) and number them from $-k$ to $k+1$ if $n$ is even (so $k=(n-2)/2$). The algorithm is as follows:



          Shoot 1 and -1.



          Shoot 2 and -2.



          .



          .



          .



          Shoot $i$ and $-i$.



          .



          .



          .



          Shoot $k-1$ and $-(k-1)$.



          Shoot $k$ and $-k$.



          Shoot $k$ and $-k$.



          Shoot $k-1$ and $-(k-1)$.



          .



          .



          .



          Shoot 2 and -2.



          Shoot 1 and -1.



          Done.



          This takes $2k$ steps, as desired.







          share|cite|improve this answer















          share|cite|improve this answer



          share|cite|improve this answer








          edited Aug 1 at 22:12









          Community♦

          1




          1











          answered Aug 1 at 15:50









          alphacapture

          1,757320




          1,757320




















              up vote
              15
              down vote













              Brute force exhaustion of possible strategies gives two solutions requiring four turns:



              • Shoot at $(1,3)$ then $(4,6)$ then $(2,4)$ then $(1,5)$

              • Shoot at $(1,3)$ then $(4,6)$ then $(4,6)$ then $(1,3)$

              along with reflections and rotations of these basic solutions. There are none requiring three turns.



              To see that the second solution works, we can use the following method to analyze the locations where there could possibly be a live ghost:



              • The ghost is among $1,2,3,4,5,6$. After shooting $(1,3)$, the ghost is among $2,4,5,6$.

              • The ghost is among $1,3,4,5,6$. After shooting $(4,6)$, the ghost is among $1,3,5$.

              • The ghost is among $2,4,6$. After shooting $(4,6)$, the ghost is at $2$.

              • The ghost is among $1,3$. After shooting $(1,3)$, it can't be anywhere.





              share|cite|improve this answer

























                up vote
                15
                down vote













                Brute force exhaustion of possible strategies gives two solutions requiring four turns:



                • Shoot at $(1,3)$ then $(4,6)$ then $(2,4)$ then $(1,5)$

                • Shoot at $(1,3)$ then $(4,6)$ then $(4,6)$ then $(1,3)$

                along with reflections and rotations of these basic solutions. There are none requiring three turns.



                To see that the second solution works, we can use the following method to analyze the locations where there could possibly be a live ghost:



                • The ghost is among $1,2,3,4,5,6$. After shooting $(1,3)$, the ghost is among $2,4,5,6$.

                • The ghost is among $1,3,4,5,6$. After shooting $(4,6)$, the ghost is among $1,3,5$.

                • The ghost is among $2,4,6$. After shooting $(4,6)$, the ghost is at $2$.

                • The ghost is among $1,3$. After shooting $(1,3)$, it can't be anywhere.





                share|cite|improve this answer























                  up vote
                  15
                  down vote










                  up vote
                  15
                  down vote









                  Brute force exhaustion of possible strategies gives two solutions requiring four turns:



                  • Shoot at $(1,3)$ then $(4,6)$ then $(2,4)$ then $(1,5)$

                  • Shoot at $(1,3)$ then $(4,6)$ then $(4,6)$ then $(1,3)$

                  along with reflections and rotations of these basic solutions. There are none requiring three turns.



                  To see that the second solution works, we can use the following method to analyze the locations where there could possibly be a live ghost:



                  • The ghost is among $1,2,3,4,5,6$. After shooting $(1,3)$, the ghost is among $2,4,5,6$.

                  • The ghost is among $1,3,4,5,6$. After shooting $(4,6)$, the ghost is among $1,3,5$.

                  • The ghost is among $2,4,6$. After shooting $(4,6)$, the ghost is at $2$.

                  • The ghost is among $1,3$. After shooting $(1,3)$, it can't be anywhere.





                  share|cite|improve this answer













                  Brute force exhaustion of possible strategies gives two solutions requiring four turns:



                  • Shoot at $(1,3)$ then $(4,6)$ then $(2,4)$ then $(1,5)$

                  • Shoot at $(1,3)$ then $(4,6)$ then $(4,6)$ then $(1,3)$

                  along with reflections and rotations of these basic solutions. There are none requiring three turns.



                  To see that the second solution works, we can use the following method to analyze the locations where there could possibly be a live ghost:



                  • The ghost is among $1,2,3,4,5,6$. After shooting $(1,3)$, the ghost is among $2,4,5,6$.

                  • The ghost is among $1,3,4,5,6$. After shooting $(4,6)$, the ghost is among $1,3,5$.

                  • The ghost is among $2,4,6$. After shooting $(4,6)$, the ghost is at $2$.

                  • The ghost is among $1,3$. After shooting $(1,3)$, it can't be anywhere.






                  share|cite|improve this answer













                  share|cite|improve this answer



                  share|cite|improve this answer











                  answered Aug 1 at 14:04









                  Hurkyl

                  107k9112253




                  107k9112253




















                      up vote
                      8
                      down vote













                      I shall prove that five moves are sufficient (for a hexagon), and believe that we need at least five moves. Let $ABCDEF$ be the hexagon, arranged in the counterclockwise order.



                      In each of the first two moves, shoot the gun at the vertices $B$ and $F$. If the ghost is not killed by now, then it must be somewhere amongst $C$, $D$, and $E$. Then, in each of the next two moves, shoot the gun at the vertices $C$ and $E$. Since the ghost cannot be at $D$ consecutively, either it is finally killed or its location is now $A$. Then, we point the gun at $B$ and $F$ again. this strategy guarantees that the ghost is dead (well, twice dead, because being a ghost means it has died before).



                      Since Hurkyl already provided a $4$-step solution, I am proving that there does not exist a foolproof strategy with $3$ moves. When the first move is made, we suppose for now that at least three consecutive vertices, say, $A$, $B$, and $C$, are not harmed. Therefore, if there exists a $3$-step strategy to kill the ghost, the next two moves will kill the ghost, even when the ghost starts at somewhere amongst $A$, $B$, and $C$.



                      The second move will have to involve at least one of the vertices $A$, $B$, and $C$; otherwise the last move will leave at least one vertex of the three untouched, and the ghost can survive. Without loss of generality, the second move hits $A$ or $B$.



                      1. Both $A$ and $B$ are gunned down in the second move. Then, to survive, the ghost must be at $C$, or it has already left area $A$, $B$, and $C$ entirely. In this case, the third move may do no harm to the ghost. (If the ghost is at $C$, then we have to kill $B$ and $D$; nonetheless, the ghost could also be at $D$ then move to $C$, where this last move will not succeed.)

                      2. The second move hits $A$ and some vertex $Xnotin A,B,C$. To survive, the ghost can be at vertex $B$, $C$, or $D$ just before the second move is made. Then again, there are too many options to survive for the ghost, as prior to the third move, it can be anywhere from $A$, $B$, $C$, and $D$.

                      3. The second move hits $B$ and some vertex $Xnotin A,B,C$. If the ghost survives both the first and the second murder attempts, it must have originally been at $B$, and then move to $A$ or $C$ prior to the second move. Thus, by the third move, the ghost can be anywhere amongst $F$, $B$, and $D$, and hitting two vertices will not secure the mission.

                      Now, we shall deal with the case that the first move hits two opposite vertices, say, $A$ and $D$. Then, prior to the second move, the ghost can be anywhere on the hexagon. Therefore, the second move will leave at least two adjacent vertices untouched. Before the third move, the ghost will now have at least four places to be.






                      share|cite|improve this answer























                      • Nice solution!$$
                        – quasi
                        Aug 1 at 13:29






                      • 1




                        I made a flow chart of your algorithm in paragraph 2: imgur.com/Ech54cQ
                        – Burnsba
                        Aug 1 at 16:02










                      • @Burnsba Thanks! The ghost is lovely.
                        – Batominovski
                        Aug 1 at 16:10














                      up vote
                      8
                      down vote













                      I shall prove that five moves are sufficient (for a hexagon), and believe that we need at least five moves. Let $ABCDEF$ be the hexagon, arranged in the counterclockwise order.



                      In each of the first two moves, shoot the gun at the vertices $B$ and $F$. If the ghost is not killed by now, then it must be somewhere amongst $C$, $D$, and $E$. Then, in each of the next two moves, shoot the gun at the vertices $C$ and $E$. Since the ghost cannot be at $D$ consecutively, either it is finally killed or its location is now $A$. Then, we point the gun at $B$ and $F$ again. this strategy guarantees that the ghost is dead (well, twice dead, because being a ghost means it has died before).



                      Since Hurkyl already provided a $4$-step solution, I am proving that there does not exist a foolproof strategy with $3$ moves. When the first move is made, we suppose for now that at least three consecutive vertices, say, $A$, $B$, and $C$, are not harmed. Therefore, if there exists a $3$-step strategy to kill the ghost, the next two moves will kill the ghost, even when the ghost starts at somewhere amongst $A$, $B$, and $C$.



                      The second move will have to involve at least one of the vertices $A$, $B$, and $C$; otherwise the last move will leave at least one vertex of the three untouched, and the ghost can survive. Without loss of generality, the second move hits $A$ or $B$.



                      1. Both $A$ and $B$ are gunned down in the second move. Then, to survive, the ghost must be at $C$, or it has already left area $A$, $B$, and $C$ entirely. In this case, the third move may do no harm to the ghost. (If the ghost is at $C$, then we have to kill $B$ and $D$; nonetheless, the ghost could also be at $D$ then move to $C$, where this last move will not succeed.)

                      2. The second move hits $A$ and some vertex $Xnotin A,B,C$. To survive, the ghost can be at vertex $B$, $C$, or $D$ just before the second move is made. Then again, there are too many options to survive for the ghost, as prior to the third move, it can be anywhere from $A$, $B$, $C$, and $D$.

                      3. The second move hits $B$ and some vertex $Xnotin A,B,C$. If the ghost survives both the first and the second murder attempts, it must have originally been at $B$, and then move to $A$ or $C$ prior to the second move. Thus, by the third move, the ghost can be anywhere amongst $F$, $B$, and $D$, and hitting two vertices will not secure the mission.

                      Now, we shall deal with the case that the first move hits two opposite vertices, say, $A$ and $D$. Then, prior to the second move, the ghost can be anywhere on the hexagon. Therefore, the second move will leave at least two adjacent vertices untouched. Before the third move, the ghost will now have at least four places to be.






                      share|cite|improve this answer























                      • Nice solution!$$
                        – quasi
                        Aug 1 at 13:29






                      • 1




                        I made a flow chart of your algorithm in paragraph 2: imgur.com/Ech54cQ
                        – Burnsba
                        Aug 1 at 16:02










                      • @Burnsba Thanks! The ghost is lovely.
                        – Batominovski
                        Aug 1 at 16:10












                      up vote
                      8
                      down vote










                      up vote
                      8
                      down vote









                      I shall prove that five moves are sufficient (for a hexagon), and believe that we need at least five moves. Let $ABCDEF$ be the hexagon, arranged in the counterclockwise order.



                      In each of the first two moves, shoot the gun at the vertices $B$ and $F$. If the ghost is not killed by now, then it must be somewhere amongst $C$, $D$, and $E$. Then, in each of the next two moves, shoot the gun at the vertices $C$ and $E$. Since the ghost cannot be at $D$ consecutively, either it is finally killed or its location is now $A$. Then, we point the gun at $B$ and $F$ again. this strategy guarantees that the ghost is dead (well, twice dead, because being a ghost means it has died before).



                      Since Hurkyl already provided a $4$-step solution, I am proving that there does not exist a foolproof strategy with $3$ moves. When the first move is made, we suppose for now that at least three consecutive vertices, say, $A$, $B$, and $C$, are not harmed. Therefore, if there exists a $3$-step strategy to kill the ghost, the next two moves will kill the ghost, even when the ghost starts at somewhere amongst $A$, $B$, and $C$.



                      The second move will have to involve at least one of the vertices $A$, $B$, and $C$; otherwise the last move will leave at least one vertex of the three untouched, and the ghost can survive. Without loss of generality, the second move hits $A$ or $B$.



                      1. Both $A$ and $B$ are gunned down in the second move. Then, to survive, the ghost must be at $C$, or it has already left area $A$, $B$, and $C$ entirely. In this case, the third move may do no harm to the ghost. (If the ghost is at $C$, then we have to kill $B$ and $D$; nonetheless, the ghost could also be at $D$ then move to $C$, where this last move will not succeed.)

                      2. The second move hits $A$ and some vertex $Xnotin A,B,C$. To survive, the ghost can be at vertex $B$, $C$, or $D$ just before the second move is made. Then again, there are too many options to survive for the ghost, as prior to the third move, it can be anywhere from $A$, $B$, $C$, and $D$.

                      3. The second move hits $B$ and some vertex $Xnotin A,B,C$. If the ghost survives both the first and the second murder attempts, it must have originally been at $B$, and then move to $A$ or $C$ prior to the second move. Thus, by the third move, the ghost can be anywhere amongst $F$, $B$, and $D$, and hitting two vertices will not secure the mission.

                      Now, we shall deal with the case that the first move hits two opposite vertices, say, $A$ and $D$. Then, prior to the second move, the ghost can be anywhere on the hexagon. Therefore, the second move will leave at least two adjacent vertices untouched. Before the third move, the ghost will now have at least four places to be.






                      share|cite|improve this answer















                      I shall prove that five moves are sufficient (for a hexagon), and believe that we need at least five moves. Let $ABCDEF$ be the hexagon, arranged in the counterclockwise order.



                      In each of the first two moves, shoot the gun at the vertices $B$ and $F$. If the ghost is not killed by now, then it must be somewhere amongst $C$, $D$, and $E$. Then, in each of the next two moves, shoot the gun at the vertices $C$ and $E$. Since the ghost cannot be at $D$ consecutively, either it is finally killed or its location is now $A$. Then, we point the gun at $B$ and $F$ again. this strategy guarantees that the ghost is dead (well, twice dead, because being a ghost means it has died before).



                      Since Hurkyl already provided a $4$-step solution, I am proving that there does not exist a foolproof strategy with $3$ moves. When the first move is made, we suppose for now that at least three consecutive vertices, say, $A$, $B$, and $C$, are not harmed. Therefore, if there exists a $3$-step strategy to kill the ghost, the next two moves will kill the ghost, even when the ghost starts at somewhere amongst $A$, $B$, and $C$.



                      The second move will have to involve at least one of the vertices $A$, $B$, and $C$; otherwise the last move will leave at least one vertex of the three untouched, and the ghost can survive. Without loss of generality, the second move hits $A$ or $B$.



                      1. Both $A$ and $B$ are gunned down in the second move. Then, to survive, the ghost must be at $C$, or it has already left area $A$, $B$, and $C$ entirely. In this case, the third move may do no harm to the ghost. (If the ghost is at $C$, then we have to kill $B$ and $D$; nonetheless, the ghost could also be at $D$ then move to $C$, where this last move will not succeed.)

                      2. The second move hits $A$ and some vertex $Xnotin A,B,C$. To survive, the ghost can be at vertex $B$, $C$, or $D$ just before the second move is made. Then again, there are too many options to survive for the ghost, as prior to the third move, it can be anywhere from $A$, $B$, $C$, and $D$.

                      3. The second move hits $B$ and some vertex $Xnotin A,B,C$. If the ghost survives both the first and the second murder attempts, it must have originally been at $B$, and then move to $A$ or $C$ prior to the second move. Thus, by the third move, the ghost can be anywhere amongst $F$, $B$, and $D$, and hitting two vertices will not secure the mission.

                      Now, we shall deal with the case that the first move hits two opposite vertices, say, $A$ and $D$. Then, prior to the second move, the ghost can be anywhere on the hexagon. Therefore, the second move will leave at least two adjacent vertices untouched. Before the third move, the ghost will now have at least four places to be.







                      share|cite|improve this answer















                      share|cite|improve this answer



                      share|cite|improve this answer








                      edited Aug 1 at 15:05


























                      answered Aug 1 at 12:19









                      Batominovski

                      22.7k22776




                      22.7k22776











                      • Nice solution!$$
                        – quasi
                        Aug 1 at 13:29






                      • 1




                        I made a flow chart of your algorithm in paragraph 2: imgur.com/Ech54cQ
                        – Burnsba
                        Aug 1 at 16:02










                      • @Burnsba Thanks! The ghost is lovely.
                        – Batominovski
                        Aug 1 at 16:10
















                      • Nice solution!$$
                        – quasi
                        Aug 1 at 13:29






                      • 1




                        I made a flow chart of your algorithm in paragraph 2: imgur.com/Ech54cQ
                        – Burnsba
                        Aug 1 at 16:02










                      • @Burnsba Thanks! The ghost is lovely.
                        – Batominovski
                        Aug 1 at 16:10















                      Nice solution!$$
                      – quasi
                      Aug 1 at 13:29




                      Nice solution!$$
                      – quasi
                      Aug 1 at 13:29




                      1




                      1




                      I made a flow chart of your algorithm in paragraph 2: imgur.com/Ech54cQ
                      – Burnsba
                      Aug 1 at 16:02




                      I made a flow chart of your algorithm in paragraph 2: imgur.com/Ech54cQ
                      – Burnsba
                      Aug 1 at 16:02












                      @Burnsba Thanks! The ghost is lovely.
                      – Batominovski
                      Aug 1 at 16:10




                      @Burnsba Thanks! The ghost is lovely.
                      – Batominovski
                      Aug 1 at 16:10












                       

                      draft saved


                      draft discarded


























                       


                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function ()
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2869002%2fan-invisible-ghost-jumping-on-a-regular-hexagon%23new-answer', 'question_page');

                      );

                      Post as a guest
































































                      Comments

                      Post a Comment

                      Popular posts from this blog

                      What is the equation of a 3D cone with generalised tilt?

                      Image
                      Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite What is the equation of a 3D cone with generalized tilt? I've noticed that in most equations given to represent a cone, there is no parameter which defines the tilt of the cone in 3D space and that most of them have their point at the origin $(0,0,0)$ - I was wondering if anyone could give me a more generalized cone equation for a cone in any position in 3D space 3d share | cite | improve this question edited Jul 25 '16 at 0:05 ervx 9,425 3 13 36 asked Jul 24 '16 at 15:38 Charlene 11 2 2 Welcome to Math.SE! Could you please explain a few things to help people give an answer useful to you: 1. What do you mean by "generalized tilt"? 2. Are you asking about a right circular cone? Does the angle at the vertex matter? 3. What form of answer (implicit, parametric...?) are you looking for? 4. If this is homework, what tools do you have available, an...
                      Read more

                      Color the edges and diagonals of a regular polygon

                      Image
                      Clash Royale CLAN TAG #URR8PPP up vote 5 down vote favorite 1 Here is the problem: For what $n$ is it possible to color the edges and diagonals of an $n$-side regular polygon with $dfracbinomn23$ colors, such that you use every color exactly three times and for every color the three segments (edges or diagonals) with that color form a triangle? Trivially $nequiv 0 text or 1 pmod3$. I can also prove that if the statement is true for $k$ than it is true for $3k$ as well. How to finish? Please help! Thanks combinatorial-geometry share | cite | improve this question edited Aug 6 at 21:57 alcana 118 4 asked Aug 6 at 21:15 Leo Gardner 356 11 Even assuming "polyhpn" in the title is a typo for polygon , it is unclear what you mean by "the edges and sides". Aren't the side of a regular polygon the same as the edges? A regular $n$-sided polygon has $n$ edges. – hardmath Aug 6 at 21:20 3 $n$ ne...
                      Read more

                      Relationship between determinant of matrix and determinant of adjoint?

                      Image
                      Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite We are studying adjoints in class, and I was curious if there is a relationship between the determinant of matrix A, and the determinant of the adjoint of matrix A? I assume there would be a relationship because finding the adjoint requires creating a cofactor matrix and then transposing it. linear-algebra determinant adjoint-operators share | cite | improve this question asked Nov 17 '17 at 17:32 CluelessCoder 32 5 For a square matrix $A$ of order $n$, we have $A(operatornameadj A)=(operatornameadj A)A=|A|I_n$ where $I_n$ is the identity matrix of order $n$. This should tell you about the determinant of the adjoint in terms of that of $A$ (use multiplicative property and other elementary properties of determinants). – Prasun Biswas Nov 17 '17 at 17:35 1 @CluelessCoder: see here: math.stackexchange.com/questions/516127/…...
                      Read more