Problem of the Day: June 21
A magical castle has n identical rooms, each of which contains m distinguishable doors arranged in a line. In each room i<n, there is one door that takes you to room i+1, and all other doors take you back to room 1. In room n, there is one door that takes you out of the castle, and all other doors take you back to room 1. When you go through a door into a room, you are unable to tell which room of the castle is is (and there is no way of marking rooms). You also cannot tell which doors have been opened before. Determine for which pairs (n,m) there is a strategy that guarantees escape from the castle, and explain the strategy.
Edited to add solution: Here's a starting thought: if we could reliably know when we are in room 1, we could solve the problem easily for any n and m. We would then:
1. Enumerate all length n sequences from the alphabet {1,...,m}.
2. For each sequence in that list, (i) get to room 1, and (ii) then follow that sequence.
Eventually we'd get to the correct escape sequence, and then we'd follow it and escape the castle.
The difficulty, of course, is that we don't have an obvious way to tell when we are in room 1. Fortunately, it's not hard to get to room 1 -- all we have to do is make a wrong door choice. But since we don't know what the right door choices are, we also don't know what the wrong door choices are.
The key insight is that we don't need to know that a door is definitely wrong. All we need to know is that it is wrong according to the escape sequence we are testing. So we modify the above plan. After enumerating the potential escape sequences, we take a sequence on the list. We then take what according to that sequence is the wrong first move. We then make that move n times in a row. If that doesn't take us out of the castle, then -- if this escape sequence is right -- we're back in room 1 (and staying there, since we're making a move that doesn't get us out of room 1). After making that "wrong" move n times in a row, we then do the potential escape sequence.
If that works, we are out. If not, we move on to the next sequence on the list, and run through the same procedure. Eventually we must get to the correct sequence, and escape the castle. Thus the castle can be escaped for any choice of n and m.
(Minor challenge variant: show that the castle can be escaped even if we don't know how many rooms there are in the castle.)
(Problem source: 2015 Canadian Mathematical Olympiad Qualification #8.)
Edited to add solution: Here's a starting thought: if we could reliably know when we are in room 1, we could solve the problem easily for any n and m. We would then:
1. Enumerate all length n sequences from the alphabet {1,...,m}.
2. For each sequence in that list, (i) get to room 1, and (ii) then follow that sequence.
Eventually we'd get to the correct escape sequence, and then we'd follow it and escape the castle.
The difficulty, of course, is that we don't have an obvious way to tell when we are in room 1. Fortunately, it's not hard to get to room 1 -- all we have to do is make a wrong door choice. But since we don't know what the right door choices are, we also don't know what the wrong door choices are.
The key insight is that we don't need to know that a door is definitely wrong. All we need to know is that it is wrong according to the escape sequence we are testing. So we modify the above plan. After enumerating the potential escape sequences, we take a sequence on the list. We then take what according to that sequence is the wrong first move. We then make that move n times in a row. If that doesn't take us out of the castle, then -- if this escape sequence is right -- we're back in room 1 (and staying there, since we're making a move that doesn't get us out of room 1). After making that "wrong" move n times in a row, we then do the potential escape sequence.
If that works, we are out. If not, we move on to the next sequence on the list, and run through the same procedure. Eventually we must get to the correct sequence, and escape the castle. Thus the castle can be escaped for any choice of n and m.
(Minor challenge variant: show that the castle can be escaped even if we don't know how many rooms there are in the castle.)
(Problem source: 2015 Canadian Mathematical Olympiad Qualification #8.)
Comments
Post a Comment