5

There are 8 smugglers standing in a row and they are waiting for customs inspecting. One of the smugglers takes a small bag which contains smugglings. There is one officer who can examine one smuggler at a time. After every examination, smuggler with the bag must pass the bag to another smuggler who stands next to him. The officer may examine as many times as he wants till he finds the bag.

The question：

Is there a winning strategy for officer? What tool should I use to solve this question?

JMP
  • 21,771
Alexander
  • 53
  • 4
  • 1
    I was super drunk at a conference once, and this guy from Waterloo University was really into this story, but it was a hunter shooting at a rabbit, and the rabbit bounced from hole to hole stochastically if he shot at an empty hole. Everyone got really into it and it turned out you could kill the rabbit. I was too drunk to remember the solution though, but I think we tried to bracket the rabbit in a corner and then use backwards induction. Good times! –  May 22 '20 at 03:20
  • Is an officer allowed to search the same smuggler twice in a row? – SlipEternal May 22 '20 at 03:38
  • @InterstellarProbe Yes. Officer may search anyone he wants every time. – Alexander May 22 '20 at 03:39

1 Answers1

0

Label the smugglers 1, 2, 3, ..., 8, and make two passes.

The first pass goes 2, 3, 4, 5, 6, 7. If the contraband started on an even-valued smuggler it must be discovered in this pass. If not, it started on an odd-valued smuggler and the second pass is just counting back down in the reverse of the same pattern.

ETA: Assume it starts on an even number, i.e. it is initially on one of 2, 4, 6, or 8.

  1. Check 2. If we didn't find it, then it must have started on 4, 6, or 8, so now it can only be at 3, 5, or 7.
  2. Check 3. If we didn't find it, the it must have been on 5 or 7, so now it has been passed to 4, 6, or 8.
  3. Check 4. If we didn't find it, then it must have been on 6 or 8, so now it has been passed to 5 or 7.
  4. Check 5. If we didn't find it, then it must have been on 7, so now it has been passed to 6 or 8.
  5. Check 6. If we didn't find it, then it must have been on 8, so it has been passed to 7.
  6. Check 7. If we didn't find it, it must have started on an odd value, so move on to the second pass.
Michael Biro
  • 13,757