# Why does this solution guarantee that the prince knocks on the right door to find the princess?

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...

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?

• The last sentence covers the situation where she starts in #3. – Kendall Frey May 28 '14 at 15:14
• @Kendall I'm afraid I don't really understand that either. How does starting in an odd-numbered room guarantee that she ends up in room #16? – WendiKidd May 28 '14 at 15:17
• @DavidWilkins The way I understand it, the princess could perpetually move back and forth between rooms 1 and 2 if she wanted. She 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... – WendiKidd May 28 '14 at 15:26
• Is it also possible to solve this problem by staying in room #2 twice (eliminating rooms #1 and #2 as a possibility), staying in room #3 twice, room #4 twice, etc? As you proceed toward room #16, you constrain the princess' location to only rooms higher than the ones you've stayed in. By the second night you stay in room #16, you are guaranteed to discover the princess. This seems like an alternative solution to me. – Stephen Touset Oct 27 '14 at 21:51
• Open door, check if princess is inside, close door, knock if she was inside. Princess found day 1 because Guardian Angel failed to mention that he's not allowed to check if she's inside the room before knocking. – Theik Feb 17 '15 at 15:14

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.

• Thank you so much for this answer. I agree that Ilmari's was great too, and I upvoted it, but I still didn't quite understand until I saw this diagram. So thank you very much! :) – WendiKidd May 29 '14 at 21:51
• This diagram is glorious. Made an account to upvote this answer. – Cruncher May 30 '14 at 14:21

In this diagram, the vertical axis shows the room number (1–17) and the horizontal axis shows the day (1–30). The $\color{red}{\text{red}}$ dots show the rooms on whose door the prince knocks on each day, and the $\color{darkgreen}{\text{green}}$ dots and arrows show the possible locations and movements available to the princess, assuming that she has not yet been found by the prince.

(For the sake of clarity, I have omitted the green dots and arrows from the dark-colored squares on the left half of the diagram, representing the days 1–15, even though the princess could also be in any of those rooms during those days.)

As the left side of the diagram shows, if the princess starts in an even-numbered room on day 1, then she will be restricted to the light-colored squares in the diagram (as she must move by exactly one room every day), and will be found by the prince by day 15 at the latest.

Conversely, if she starts in an odd-numbered room on day 1, then she will not be found by the prince during the first 15 days. However, this means that she's restricted to the dark-colored squares on the diagram, and so, on day 16, when the prince turns back, she must be in one of the even-numbered rooms, and will thus be found by the prince on his second pass through the rooms, during the days 16–30.

Ps. In any case, the important thing to realize is that, if the princess is in an even-numbered room on day $n$, then she must move to an odd-numbered room on day $n+1$, and vice versa. Thus, in the diagram above, she is restricted to always staying on squares of one color, like the bishop on a chessboard.

Incidentally, the diagram also shows that the given strategy is not the only possible one for the prince. Besides the obvious mirror-image variant, the prince could also start as in the given solution, but decide on day 16 to move back to room #2 and work upwards from there, instead of staying at room #16 and working downwards. Either way, if he hasn't found the princess by day 15, she must be staying in the rooms corresponding to the dark-colored squares, and so, by systematically knocking on each room's door when it's dark, he will eventually find the princess by day 30.

• This is an excellent answer, and I really appreciate you taking the time to answer my question (I upvoted :)). I was still a little confused until I saw the image in this answer, which is why I accepted that one. But it was the combination of the two answers that helped me understand, and I just wanted to say that I really appreciate it! – WendiKidd May 29 '14 at 21:52
• @WendiKidd: No problem, at least I got a badge for it. ;-) (Ps. Wow, looks like that's the first gold badge anyone's gotten on this site. Thanks!) – Ilmari Karonen May 30 '14 at 9:56

The solution assumes that she cannot ever stay in the the same room. Either on even days she is in even rooms or on even days she is in odd rooms.

As he is going from room 2 to room 3 he is going from an odd day to an even day. She can go from room 3 to 2 if she is in even rooms on even days. She can never pass him if she is in odd rooms on even days as he is moving to higher numbered rooms.

When he moves from low numbers to high numbers, he eliminates one by one each possibility of her being in odd rooms on even days and then, as he goes backwards, he eliminates the possibilities of her being in even rooms on even days.

when he goes from 3 to 2 she cannot go from 2 to 3 as she cannot be in room 2 as that was already eliminated.

• Wow. Great answer! I haven't thought of this. – klm123 Jun 10 '14 at 5:18

The princess moves 1 room (never 0, never 2) each day. So does the prince. To meet, they have to be at distance 2, and move toward each other.

Therefore, their distance either stays constant, increases by 2, or decreases by 2, but the oddity is unchanged, except once on day 16.

If the initial distance is even (first case discussed in the solution), it will always stay even, which is why the princess can never get past the prince, and therefore gets stuck in the final room. That also implies that the princess is not in room 1 (distance is 1), but only in rooms (2, 4, 6, 8, 10, 12, 14, 16).

If the initial distance is odd, just move forward to the 15th day. At this point, the prince does not move but the princess still does, changing their distance by only 1, making it even, reducing to the initial problem.

If we begin knocking at door #2 and the princess is in room #3

The distance in this case is 1, which is odd, meaning the prince will necessarily miss the princess in the first 15 days. (try it. the princess can skip the prince at any moment, and the prince can never get to here in the first part.). But as soon as day 16, the distance becomes even, and the prince is sure to catch up with the princess at some point

• Good answer, just noting we call the concept of matching states as "parity", not "oddity". – Kyle Hale Oct 5 '14 at 16:19

I find it easier to understand the solution by remarking at the onset that there is an interesting parity invariant: the sum of the day number and the princess's room number always has the same parity (it's either always even or always odd). This holds because every time the day number increases by 1, the room number either decreases or increases by 1, so their sum increases by either 2 or 0.

Suppose that the sum is always odd. On day 1, the prince visits room 2; on day 2, he visits room 3, and so on. Notice how his visits have odd parity too, and the day+room sum of the prince increases by 2 every day. The princess's sum cannot have started smaller than the prince's, since on day 1 and with rooms numbered from 1 the smallest possible sum is 3. So the prince is pushing the princess towards higher-numbered rooms, until on day 15 he visits room 16, which is the highest possible odd sum. Thus, if the princess has an odd sum, the prince will flush her out no later than day 15. If the princess has an even sum, these 15 days are for nothing.

On day 16, the prince starts exactly the same procedure, but with even sums. It doesn't actually matter whether he starts with door 2 or door 16. By the same phenomenon as before, after 15 days of going from the second door to the next-to-last door, the prince will flush out the princess if her sum is even, no matter where she started out.

It's important to realize that it doesn't matter if the princess starts in a high-numbered room and crosses the prince during the first phase. If the princess has an odd sum, then the two will meet in the middle. If she doesn't meet the prince somewhere, it means that she had an even sum, and he'll catch her during the second phase.

Try a specific example. Say she starts in 6. He knocks on 2 and doesn't find her. She can move to 5 or 7. He knocks on 3 and doesn't find her. She moves to 4,6, or 8. He knocks on 4 and might find her. The thing that can't happen (if she started in an even room) is for her to slip by him. In this example, she must be in 6 or 8 if he doesn't find her, and now moves to 5,7, or 9. He knocks on 5. The rooms she might be in keep getting pushed toward high numbers. If she started in an even room, he is guaranteed to find her by the time he knocks on 16. If she started in an odd room, by the time he gets to 16 that is all he knows-that she started in an odd room. If she is now in 17, she will move to 16 and he will find her. Otherwise he knows that she is now in an even room and the series back to 2 will find her. The critical point is that her room changes parity each move, so he takes advantage of that.

• you beat me by seconds... I will have to make a better answer. – kaine May 28 '14 at 15:42
• @kaine I would love for you to undelete your answer. I found it to be useful. I think all the answers to this question explain it in a slightly different way, and it was reading all those answers together that eventually helped me figure this out :) – WendiKidd May 29 '14 at 22:28

You can't just dissect each statement when following a proof. You have to keep the assumptions and the context in mind. The problematic statement you quote should be read like this:

If the princess occupies an even numbered room on the day the prince first knocks on a door then she will never be in a room adjacent to the one he knocks on

Of course the assumption is not proven in any way. But the point is if the assumption doesn't hold then the second part of the proof applies.