Find a bug under 6 tiles

Question

The question seems rather simple, yet it is suprisingly difficult.

There is a bug under one of six tiles and it is my job to find it. The tiles lie in a row. At night, the bug moves randomly 1 tile, so it either moves to the left or to the right. During the day you are allowed to pick up one tile to see if the bug is there. If you choose the tiles as optimal as possible, how many days will it take you to find the bug, at most?

The answer is multiple choice, namely a.) 6 days, b.) 8 days or c.) 10 days.

Lets defne the tiles as follows: the first tile on the left we call 1, then the tile on the right of the first tile we call 2, etc. until we have a set {1,2,3,4,5,6}.

MY APPROACH: [I was thinking that you start with 3. You find that it's not there, but the bug could have been under 4 and moved during the night under 3, so the next day you lift 3 again. It's not there, but the bug could have gone from 5 to 4 and now there is again a possibility that the bug moves under 3 when you decide to lift another tile, so again you would think it's best to lift 3. Since the bug can move between 5 and 6 back and forth it is useless to continue looking under just tile 3. But if you decide to look under another tile there is always the possibility that the bug will move under the tile you looked under one days before that. Therefore, it seems to me that the problem is unsolvable.

I tried to visualize the problem on a lattice of 10 by 6 where every day (the number of rows) is representated by a row of 6 tiles. Then drawing two lines from every tile in the first row to the left and right tile in the row below and leaving out the lines from the tile I looked under. Then I eliminated the tiles to which the most lines come to. But after 10 days there are about 4/5 lines per tile, so this doesn't work even though it seems rock solid to me.]

Does anybody have any suggestions or solutions?

Answer 1

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

Answer 2

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.

Answer 3

This should be a clear pictorial explanation of the fact that the $2-3-4-5-5-4-3-2$ strategy catches the bug in at most $8$ days (on the right, the number of edges between consecutive layers):

Can we do better? Well, we may try to cut $2$ edges at each step, but then the vertices with a single incoming edge propagate. On the other hand the bug might chose to alternate between two adjacent tiles among $1-2,3-4,5-6$, and six days are necessary to rule out just this possibility.