0
$\begingroup$

In a castle, there are N rooms in a line. Each room has a door to the two neighbouring rooms (or the one neighbouring room, for the rooms at either end). A treasure is hidden in one of the rooms. Each night, you can break into one of the rooms and search for the treasure. If you break into the right room, you will find it, but otherwise the next day the guardian of the castle will move the treasure to an adjacent room (they never leave it in the same room, nor move it to a non-adjacent room).

Is it possible to guarantee you find the treasure? How many nights do you need in the worst case?

Could someone give me a pointer or two on how I could solve this? I tried breaking the problem into recursive subcases but I didn't get anywhere.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
2
$\begingroup$

For N=4:

Label the rooms A,B,C,D. Then a search of B,B ensures the treasure is in room C or D. Now search C,C. The treasure must be in A, so searching room B ensures victory in 5 nights.

Addendum (@JaapScherphuis)

The first search of B is not needed, so 4 nights. Because you search B (t=A), you search C (t=B), you search C (t=A), and s=B (t=B). Or s=B (t=C), s=C (t=B), s=C (t=A), and s=B (t=B).

Improve this answer
$\endgroup$
4
  • $\begingroup$ rot13(Cebivqrq gernfher vf va P jura zbivat gb frnepu va P sebz O gur bjare pbhyq'ir zbirq gur gernfher gb ebbz O qhevat gur qnl.). $\endgroup$
    – Abbas
    Aug 14, 2019 at 16:11
  • 1
    $\begingroup$ @Abbas; if the treasure starts in A or B, then BB finds it. Game over. If not, it must start in C or D. If it ever moves to B within 2 nights, game over. Otherwise it is in C or D. It is then moved, to either (if in C) B or D, or (if in D) C. If it is now in C or D, a search of CC finds it, so when we switch to searching CC it MUST be in B after the first C search, and in A after the second. And next it must be in B, so this is the only search left. $\endgroup$
    – JMP
    Aug 14, 2019 at 16:16
  • $\begingroup$ You don't actually need your first B move. If you remove that, then you essentially have the same 4-step solution as described in the linked duplicate question. $\endgroup$
    – Jaap Scherphuis
    Aug 15, 2019 at 8:00
  • $\begingroup$ @JaapScherphuis; fixed, tnx. $\endgroup$
    – JMP
    Aug 15, 2019 at 8:08
0
$\begingroup$

We think we have a partial answer.

For the case N=1, you will find the treasure in the first night

For N=2, you just have to search the same room twice and you will have the treasure in the second night (worst case scenario)

For N=3, same thing with the middle room

For N=4 or more, we don't see any strategy that can allow you to get the treasure in a finite time. You can spamm the same room but the keeper can switch forever between the same two rooms. And if you want to switch he can switch to avoid your search also.

Maybe we miss something in the explanation text though.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.