Find a bug under 6 tiles

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.

3 disjoint zigzag paths

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.