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!

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.
