4

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?

Alex
  • 87
  • I think if you pick up a tile, it stays picked up. If that is the case then the answer is obviously a), $6$ days. – Landuros Dec 26 '17 at 11:00
  • 1
    I believe the problem can be solved and the answer is 10. Consider two cases, depending on whether the bug starts under an even or an odd-numbered tile. – MJD Dec 26 '17 at 14:12
  • @MJD Yes, that is the key! And it totally surprised me that the parity-argument can be apllied in this problem!. Great diabolic problem! – Peter Dec 26 '17 at 14:19
  • I found a simpler solution; only 8 tries are needed. – MJD Dec 26 '17 at 14:25
  • 2
    The question is isomorphic to this: https://math.stackexchange.com/questions/206095 – Bart Michels Dec 26 '17 at 14:37
  • 1
    Interesting side-question: can the bug escape his death indefinetely, if he is able to teleport from tile $6$ to tile $1$ and vice-versa? – Jack D'Aurizio Dec 26 '17 at 16:30
  • @JackD'Aurizio: Yes because the path grid becomes a cylinder and so clearly after every step all other points except under the opened tile are still reachable by some path. – user21820 Dec 26 '17 at 17:38
  • 2
    The answer you accepted did not prove that it is correct, because your question asks for the optimal strategy. – user21820 Dec 29 '17 at 06:31
  • If you understand and agree with my answer, you can accept it instead of leaving the incomplete answer accepted. If there is anything unclear in my answer, feel free to clarify first. – user21820 Dec 29 '17 at 13:50
  • @Bram28: None of the answers on the linked post prove optimality... – user21820 Dec 31 '17 at 09:16
  • @user21820 True! I did not see that! – Bram28 Dec 31 '17 at 13:20
  • Some related links, though proof of optimality is not always given: https://math.stackexchange.com/questions/2435154/proving-that-a-solution-to-the-cat-behind-7-doors-puzzle-is-optimal ; https://puzzling.stackexchange.com/questions/455/why-does-this-solution-guarantee-that-the-prince-knocks-on-the-right-door-to-fin ; https://www.theguardian.com/science/2017/jul/03/did-you-solve-it-are-you-smarter-than-a-cat – Bram28 Jan 26 '18 at 20:38
  • Related: https://math.stackexchange.com/questions/206095/finding-the-robot – leonbloy Aug 05 '20 at 02:21

3 Answers3

3

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.

user21820
  • 57,693
  • 9
  • 98
  • 256
  • (+1) I exploited a similar idea and a similar diagram, too (I finished writing my answer after you, I hope you do not mind if I keep it there). Well done. – Jack D'Aurizio Dec 26 '17 at 16:17
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
MJD
  • 65,394
  • 39
  • 298
  • 580
  • Thanks! Moreover, $$2,3,4,5,5,4$$ works as well. You can try it by making the 6 by 10 lattice as I proposed in my original approach. Thus the answer is 6 days. – Alex Dec 26 '17 at 14:48
  • 1
    @Alex: No. The bug can be at $1,2,3,4,3,2$ and you won't find it with $2,3,4,5,5,4$. – MJD Dec 26 '17 at 15:12
  • @MJD Yes you are right, since the question is find the bug (which is how I formulated it). Though it would be $2,3,4,5,5,4$ if the question was many times it would take to tell where the bug is. Because after $2,3,4,5,5$ the bug can only be under $2$ or $4$, hence if you pick up one you know where for sure where it is. – Alex Dec 26 '17 at 15:19
  • @user21820 Not true concerning MJD , but he decided to hide the proof. – Peter Dec 26 '17 at 16:21
  • @Peter: Did you downvote both MJD's answer and my answer?? Yes I see he did not claim it, but sort of implied because the question is about the optimal solution. – user21820 Dec 26 '17 at 16:22
  • I didn't downvote anything here. – Peter Dec 26 '17 at 16:24
  • @Peter: Strange then; there's a silent downvoter downvoting correct answers here. – user21820 Dec 26 '17 at 16:26
  • I decided to delete my answer because this (accepted) answer contains a (hidden) proof. So, my answer is clearly inferior. – Peter Dec 26 '17 at 16:36
  • @Peter: Oh okay. Did you check my proof that $8$ days are necessary? – user21820 Dec 26 '17 at 16:37
  • I did not claim optimality. I only claimed that $8<10$. – MJD Dec 29 '17 at 15:37
0

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): enter image description here

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.

Jack D'Aurizio
  • 353,855