Find a bug under 6 tiles

Solution 1:

I shall present a general solution and optimality proof for $n$ tiles! But first for $6$ tiles.

Here is a proof that $8$ is the optimal number of steps, meaning that it is the minimum number of steps needed to guarantee finding the bug.

First follow MJD's proof that it is sufficient. In short, one sweep $2,3,4,5$ ensures finding the bug if it starts under an even tile and the second sweep $5,4,3,2$ ensures finding the bug if it starts under an odd tile, in both cases because the bug cannot cross the sweep.

Next we shall prove that it is necessary. Notice that each step is relevant only for an even bug or an odd bug, but not both, where the bug parity is defined as the parity of the tile it starts under. In particular, for every step, if it can possibly hit an even bug, then it does nothing to help you find an odd bug. So every sequence of $7$ steps has only $3$ steps relevant for some bug parity, which we can assume to be an odd bug by symmetry. Now consider the $3$ disjoint zigzag paths for the odd bug, namely $1,2,1,2,1,2,1$ and $3,4,3,4,3,4,3$ and $5,6,5,6,5,6,5$. The leftmost and rightmost zigzag paths must each be hit by at least $1$ of those $3$ steps, so the middle zigzag path will be hit by at most $1$ of those steps. The bug can then follow the middle zigzag path but deviate to evade that hitting step, which is possible since you are not allowed to open $2$ tiles in the same step.

For example if the big dots represent the tiles opened in those $3$ steps, then the middle path (pink) can be adjusted by the dotted segments to evade that $1$ hitting step.

This proof also shows that the condition that we can only open $1$ tile in each step is crucial. If we can open $2$ tiles in one step, the minimum number of tile openings we need goes down to $6$ with the $3$-day sequence $\{3,5\},\{2,5\},\{2,4\}$.

Now for the general solution for $n$ tiles. It is obvious that if $n = 1$ then $1$ step is optimal, and that if $n = 2$ then $2$ steps is optimal. Henceforth we can assume $n \ge 3$, and for that I claim that $2(n-2)$ steps is optimal.

To show that $2(n-2)$ steps is sufficient, we use the same sweep solution as before, namely $2,3,...,n-1,n-1,...,3,2$, which works for the same reason as before.

To show that $2(n-2)$ steps is necessary, I found an elegant proof. Simply observe that for each tile that is not the first or last tile, we must open it at least once relevant to each bug parity, otherwise the bug can keep returning to it and on every other step going either left or right to evade any tile that you open. Thus you need at least $(n-2)$ steps for each bug parity.

Solution 2:

I think Peter's solution elsewhere in the thread works, and I think the following solution also works, but is shorter.

$$2,3,4,5,5,4,3,2$$

Proof:

1. I claim that if the bug starts under an even-numbered tile, then $2,3,4,5$ will find it. If the bug starts under an even-numbered tile it is under 2,4, or 6. If it is under 2 we find it immediately. Otherwise it was at 4 or 6 and is now at 3 or at 5. If it is at 3 we find it on the second try. Otherwise it was at 5 and has moved to 4 or 6. If it moved to 4 we find it on the third try. If not, it was at 6 and has just moved to 5 and we find it on the fourth try.
2. Using the same type of reasoning, we see that if the bug starts under an odd-numbered tile, then $5,4,3,2$ will find it.
3. Now suppose we have just done $2,3,4,5$ and failed to find the bug. It must have started under an odd-numbered tile, or else we would have found it. Since the bug switches between odd and even every night, it must now be under an odd-numbered tile again, and $5,4,3,2$ will find it.

So the answer is that no more than 8 steps are needed.

Addendum 2019-08-28: I find it very surprising that, no matter how many tiles there are, we can always guarantee to find the bug! The strategy of this post is easily extended to find the bug in at most $2n-4$ guesses, where $n$ is the number of tiles.

Addendum 2019-10-09: The paper Finding a princess in a palace: A pursuit-evasion problem (Britnell, John R. and Mark Wildon, 2012) generalizes this problem to a bug moving from node to node of an arbitrary graph, rather than just a line, and proves the following remarkable results:

1. A very simple generalization of the strategy above will guarantee to find the bug in bounded time, if any such strategy exists.
2. A strategy exists if and only if the graph is (1) acyclic and (2) does not contain any vertex from which emerge three or more paths of length 2.
3. If a strategy does exist, the one they provide yields the optimum possible bound