Steem Riddle of the Week #9: Wandering Monster -- Solution Revealed + Prize awared

Steem Riddle of the Week #9: Wandering Monster

For those who missed it, the full riddle is stated here: https://steemit.com/riddle/@droopy/steem-riddle-of-the-week-9-wandering-monster

Solution

The solution to this riddle is actually very simple, you can just check the following caves is this order.

2,3,4,5,6,7,8,9,10,10,9,8,7,6,5,4,3,2.

This is guaranteed to catch the monster, but seeing why is not immediately obvious. The easiest way to understand the solution is to first imagine a smaller example with 4 caves. Suppose we check 2,3,3,2.

After we check cave 2 on night 1, if the room is empty, where can the monster be on the night 2? Well, he cannot be in cave 1, because the only path into cave 1 is from cave 2 and he was not in cave 2 the night 1. But the monster could be in caves 2,3 or 4. Next we check cave 3 on night 2. If cave 3 is empty on night 2, where can the monster be on night 3? Well it cannot be in cave 4, because cave 3 is the only path into cave 4. It also cannot be cave 2. Why? Because the possible paths into cave 2 are from cave 3 (which was empty on night 2) and cave 1 (which must have been empty on night 2 from our previous step). Thus the monster is either in cave 1 or cave 3 on night 3. If we then check cave 3 on night 3 and it is empty then the monster must have been in cave 1 on night 3 which means it had to move to cave 2. We check that cave as our final check and we're done.

The same logic scaled up solves the 11 cave version. This riddle is actually a rewording of a well known riddle about a princess who changes bedrooms each night. There is an interactive version of the game here, where you can see the possible caves that the monster might be in after each cave you check: http://bit.ly/2E5nQay.

Prize

This weeks one SBD prize went to @uber-dragon. Congratulations and thanks to everyone who participated!

Don't forget to follow and to check out my past riddles

First off, thanks to everyone for all the support! If you'd like to browse my older riddles you can do so at the links below:

https://steemit.com/life/@droopy/steem-riddle-of-the-week-2-flipping-cards-prize-doubled
https://steemit.com/life/@droopy/steem-riddle-of-the-week-3-alternating-truth-prize-for-first-correct-answer
https://steemit.com/life/@droopy/steem-riddle-of-the-week-4-black-cards-prize-for-first-correct-answer
https://steemit.com/life/@droopy/steem-riddle-of-the-week-5-the-cup-game-prize-for-first-correct-answer
https://steemit.com/life/@droopy/steem-riddle-of-the-week-6-burning-ropes-prize-doubled
https://steemit.com/life/@droopy/steem-riddle-of-the-week-7-midpoints
https://steemit.com/life/@droopy/steem-riddle-of-the-week-8-truth-lies-and-chaos