0

There are $8$ doors from left to right, and initially, there is a monkey behind each door. Each time a boy can choose to open a door and mark the monkey(s) he saw. After marking the monkey(s), he closes the door and each monkey will have $1/2$ probability to move to the left adjacent door and $1/2$ probability to move to the right adjacent door (if the monkey is at door $1$, then it move to door $2$ with probability $1$ because there is no door on the left; same for the monkey at door $8$). What is the smallest number of times of opening the doors that guarantees the boy to mark all $8$ monkeys? What is the corresponding strategy?

Someone proposes that this is similar to the situation that there is only one monkey behind one of $8$ doors and we want to use least number of steps to find it out. For reference, see Find a bug under 6 tiles. However, I cannot see the relation between them, can anyone give a hint on it?

William
  • 987
  • What have you tried so far, and where are you stuck? Here you are expected to show the efforts you have made (in the main body) before help starts coming – true blue anil Feb 21 '22 at 22:45
  • 1
    The solutions in "1 bug under 6 tiles" tells you that the optimum number of tries to guarantee finding "1 monkey behind 8 doors" is 12. Since this holds for whatever position the monkey is in, hence it will also give us "all monkeys behind 8 doors". – Calvin Lin Feb 21 '22 at 23:41
  • I could understand your point @CalvinLin. However, I am not so sure because for each monkey behind different doors, the strategy might be different (i.e., you might follow different sequences of doors to find it in 12 steps). In this case, how to guarantee that along one sequence (12 steps) to find a certain monkey, you actually also meet all of the other monkeys? If for each monkey, we can follow exactly the same sequence of doors, then I can see why the answers are exactly the same. – William Feb 21 '22 at 23:50
  • 1
    @William You can look and see that the solution in the bug problem just says to look at certain doors (tiles) in a certain order: it is fixed in advance. – Misha Lavrov Feb 21 '22 at 23:54
  • @MishaLavrov Thanks for your explanation. I understand it now. – William Feb 22 '22 at 01:07

0 Answers0