1
$\begingroup$

This is the story of the sister of the princess in this puzzle. I will shamelessly copy-paste some parts of this post. I have no reference to give for this version as I adapted a Computer Science problem I once saw on paper.

In a big castle lives a princess. 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 castle is particular in the sense that there is a central bedroom – the white room – and 3 wings, each composed of 3 bedrooms – the red, green and blue rooms – separated by a corridor.

enter image description here

Like her sister, she knows that if a prince comes, the guardian angel of the castle will tell him of her sleeping patterns and inform him that each morning he may knock on one of the outside doors. She would have to marry him if he ever find the right door.

However, she is quite disillusioned about princes and love and such things. She want to keep her independence and still have her freedom to sleep all day. Knowing that the guardian angel would not budge about this tradition, she only asks that the prince tells in advance what rooms he will check, and in which order (no matter how long he stays, he must tell all his future tries).

Show that if a prince ever comes, no matter how long he stays and whatever the checking order, the princess will still have a way to avoid him if she can choose the room of the first night while still following the "adjoining bedroom" rule.

Note that knowing the checking order would not have helped her sister. The prince would still have married her.

$\endgroup$

1 Answer 1

1
$\begingroup$

Here is a strategy:

The idea behind this strategy is to always make sure the princess is in a "superposition" of two rooms. That is, the prince doesn't know which of the two rooms she's in, and cannot catch both at once. The princess will then be able to use her advance knowledge to pick the option that doesn't get caught.

(0) The princess's first move will be to go in any green room that the prince is not picking on the first turn.
(1) Case 1: The princess is in a superposition of two green rooms -- say, G₁ and G₂.

Consider the prince's move two turns from now.
(1a) If it's W₀ or G₃, both "copies" of the princess can live by hopping off their rooms and back on. (The prince's intermediate move can be easily avoided.)
(1b) If the prince's second move is G₁ and his first isn't R₂, the princess on G₂ can go to R₂, then "split" to W₀ or G₂.
(1c) If the prince's second move is G₁ and his first is R₂, the princesses can live by going (G₁→)R₁→W₀ and (G₂)→B₂→G₂.

(and of course, (1b) and (1c) also handle the case where the prince chooses G₂ on his second move.)

(2) Case 2: The princess is in a superposition of W₀ and a green room -- say, G₁.
Consider the four paths:
(2a) (W₀)→R₂→G₂
(2b) (W₀)→R₃→G₃
(2c) (G₁)→R₁→W₀
(2d) (G₁)→B₁→G₁

The prince can eliminate at most one of these paths with his first, and one with his second. So the princess will still have two paths open to her.

This completes the strategy. The princess always has at least two ways to be alive no matter what the prince does. The prince can eliminate one of those options, but each time he does, the princess will have chosen the other... and his wrong guess will allow her to leave him two options once again.

$\endgroup$
1
  • $\begingroup$ Damn, I didn't know it was the kingdom of Schrödinger! Good job! $\endgroup$
    – Nathaniel
    Dec 2, 2021 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.