An invisible ghost jumping on a regular hexagon

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!

Solution 1:

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.

Solution 2:

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.

Solution 3:

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 $X\notin \{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 $X\notin \{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.