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.