10. On the Top Floor of a Castle Lives a Princess.
A princess occupies the entire top floor of a castle. The floor contains 17 bedrooms arranged in a straight line. Each bedroom has
• an interior door to each adjacent bedroom, and
• an exterior door that opens onto a common corridor.
Every night, just after midnight, the princess moves through an interior door to one of the two neighbouring bedrooms and then spends the entire next day there. She never stays in the same room two nights in a row and she never skips a room.
A prince arrives wishing to marry her. Each morning, before the princess makes her nightly move, he may knock on exactly one exterior door. If the princess is in that bedroom she will open the door and agree to marry him; otherwise nothing happens and the day is lost.
The prince must return to his kingdom after 30 days, so he has at most 30 knocks. Knowing the princess’s routine but not her initial location, can the prince guarantee success? If so, describe an explicit day-by-day strategy.
Submitted by tartle · Added 17 January 2013
Solution:
Label the bedrooms 1 through 17 from left to right. The prince never needs to knock on rooms 1 or 17; instead he proceeds as follows.
Days 1–15 : knock on room 2, then 3, 4, …, up to room 16.
Day 16 : knock on room 16 again.
Days 17–30 : knock on room 15, then 14, 13, …, back down to room 2.
This schedule uses exactly 30 attempts (room 16 is visited twice) and is guaranteed to succeed.
Why it works
Suppose the princess starts in room k on the morning of day 1.
• While the prince is moving to the right (days 1–15), he advances one room each day, exactly as the princess does. The difference k − P (where P is the room he knocks on) therefore changes by 0 or ±2 each day, so its parity is preserved. In particular the princess can never pass the prince—she can only stay the same distance away or get closer. By the morning of day 15 the prince is at room 16, so if the princess started in any even-numbered room (2, 4, …, 16) he must already have found her.
• If instead she started in an odd-numbered room, then on day 16 she is in an even-numbered room (because she moves every night). Day 16 is the moment the prince stops and knocks on room 16 a second time; from that day on he reverses direction and again moves in lock-step with the princess. The same “cannot pass” argument now applies to the left-moving phase, and the prince must catch the princess no later than day 30 when he knocks on room 2.
Thus, regardless of her initial position, the princess will open the door within 30 days, and the prince is assured of winning her hand.
Comments (13)
He should just goto the same door, in the middle of the hallway every day.
_ = door
+= prince
_ _ _ _ _ _ _ _ _ + _ _ _ _ _ _ _ _
Even if she's 1 door after him on the first day he chose that door, he would always "find" her, regardless of it she "turned around" at the end of the hallway, or walked back to the "start"
At least, I'm pretty sure.
he should wait in the hallway. if the rooms are in a row there is a beginning and an end. so he is bound to see her and ask for her hand.
he mines the walls :lol:
The Prince would knock on door 9 every day. No matter where the princess was, it would take a maximum of 9 days for her to make it back to him. (Assuming that when she arrived at the end she would cycle back- and not use the hallway).
Shout "FIRE!" and wait for her to run out...
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.
The prince could knock on any one of the doors day after day waiting for the princess, but the problem says she moves to an adjoining room at night. This means the princess may very well move between rooms 16 and 17 exclusively.
This may just be me, but whenever I head over to my friends place, I tend to knock on the front door of his house to get his attention, not his bedroom door.
i think the prince should wait at the first door because as he have 30 chances the princess will surely come in the first room as there are only 17 room available if she is in the 3 room also at the arrrival of the prince she will return to the 1 room within 30 days :roll: 8) :lol:
I 'ld suggest him to marry guardian angel.... :lol:
Because the princess could alternate only between door 16 and 17, he should not knock on the same door every time and wait for her to pass him.
He should knock twice on door 2 then twice on door 3 then 4 and 5 and so on until door 16.
If the princess were moving across the rooms from 8 to 7 to 6, he would intercept her as he moves across. If she is alternating only in 1 and 2 she could spend the first night in 1 and he would knock on 2, but the next night she would have to move to 2 and he would knock there again, this would be the same for doors 16 and 17.
he only has to knock on one door,there are only 17 door's.
:o
to alt_16064
Knocking twice on door 2 then twice on door 3 then 4 and 5 and so on until door 16 won't work.
That strategy is defeated if the princess begins in room 4 and moves 4-3-2. On the third day she's in room 2 when he's knocking on room 3. He would then need to double back to catch her if she continued 1-2-1-2 so 2-2-3-3 etc. won't work.
The princess can never be in an adjacent room when the prince knocks a second time because she can skip over him on the next move if he knocks on her previous room
I'm not sure if there is a solution in 30 knocks. I certainly don't consider this a "very easy logic problem" unless I'm missing something.
Its a very refined question and is "Not very easy"
Strategy begins from the point:
let the rooms be A,B,C,... from one end of corri to other.
Its a very good game of Trapping and position.
For eg. if I knock at room F on day 1
and if princess is in E or G,
she may move to D or F if in E,
she may move to H or F, if in G,
next I should knock on room D, then next on I (she could not have escaped had the hypothesis been true, and recursively reduce the length of rooms in which she may move.)
I do not think finding an algorithm will be easy.
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).
Add a Comment or Suggest an Answer