I found this puzzle online:
On the top floor of a castle lives a princess. The floor has 17 bedrooms arranged in a row. Each bedroom has doors connecting to the adjoining bedrooms as well as to the outside corridor. The princess sleeps in a different bedroom each night by opening the door to an adjoining bedroom and spending the night and the next day in that room.
One day a prince arrives at the castle and is desirous of marrying the princess. The guardian angel at the castle tells him of the princess' sleeping patterns and informs him that each morning he may knock on one of the outside doors. If the princess happens to be behind that door, she will open it and consent to marry him. The prince also has a return ticket to his kingdom in 30 days, so he can make at most 30 attempts. Can the prince win the hand of the princess, and if so, what is his strategy?
An unstated assumption here is that the princess can move to any adjacent room (she's not restricted to moving in one direction). So a possible sequence could be 3, 2, 3, 4, 5, 4, 3, 2, 1, 2...
Further down the thread at the link, this solution is given:
The Prince should knock on the second door from one of the ends of the corridor (call it door #2), and knock on the next adjacent door each successive day until he reaches the second door from the opposite end of the corridor (door #16). The day after that, he should begin the same process in reverse order (meaning he will knock on the 16th door two days in a row). By the time he reaches his starting point (door #2 on the 30th day), he will have found the princess.
Number the doors 1 thru 17.
If the princess occupies an even numbered room on the day the prince first knocks on a door (#2), then she will either occupy the same room he knocks on or she will be an even number of rooms away. Since both move to an adjacent room each day, this will hold true so she will never be in a room adjacent to the one he knocks on, and thus never be in a position to move past him the next day. She will have nowhere else to go by the time he reaches the 16th door, and will have by then been located. If she, on the other hand, was in an odd numbered room when he began, then she will be in an even numbered room when the prince starts the process again on day 16 (when he knocks on door #16 the second time).
I've been trying to follow the solution, but I don't quite get it. The main assumption the logic in the solution seems to hinge on is this: "she will never be in a room adjacent to the one he knocks on, and thus never be in a position to move past him the next day." I can't figure out what evidence from the puzzle supports that assumption. If we begin knocking at door #2 and the princess is in room #3, our next move (following this solution) will be to knock on door #3. But at this point the princess could have moved to room #2, and we will keep moving to higher numbered rooms, and the princess could easily remain in the lower-numbered rooms.
So I'm having trouble understanding why this is the solution. Can someone explain it more clearly/in a different manner? Why will this process ensure the princess is found?
Answer
Ilmari's answer covers the logic of the answer perfectly, but in case anyone's still confused, here's a version of the diagram I find more intuitive (I made it myself while solving the puzzle).
The Pink squares are rooms where the princess could be on the given day, the blue squares are where the prince knocks that day, and the black squares are rooms in which she logically cannot be. On day 30 all rooms but room 2 have been eliminated, meaning that if the prince has not found the princess already, he will find her there on day 30.
No comments:
Post a Comment