Find the queen!
Probability
Level
2
There are 100 rooms (in a line). The queen is in one of the rooms. In every day at 6:00 am the queen goes to an adjacent room. The king in every day at 12:00 can open exactly one of the rooms, and check if the queen is there. Can the king find the queen for sure in a year?
No, he can't
Yes, he can
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Observe that the king has a clear advantage: he can open any room, while the queen has to change to an adjacent one.
Now label the n rooms as following:
Note that since there are 100 rooms, the string will indeed end with a one. One algorithm (ignore the queen for now) is as following, thinking left to right:
Worst case scenario, the queen will be found in the end, after 1+96+2+97 = 98+98 (symmetry) = 196 days, which is less than 365. (In general: 2(n-2))
This works because if you both start in a label 1 room, the queen can't be adjacent to the king any day so she can't skip him, and since the king is moving to the right, they are forced to meet. If the queen were to start in a label 0 room and moved along to the right, she is forced to meet the king at alg. step 2 since she was cornered. Only exception is the queen starting in the first room and that translates to the same case as a skip before the game even started so to say, which is now explained. If the queen were to start in a label 0 room and skipped the king by going to the left while he was going to the right (or was in the first room), the waiting move of alg. step 2 does not change the parity of the king's position, and thus they are forced to meet at one point because now he'll corner her by moving to the left (same principle as the first case, the waiting move aligns them since the queen does move and that changes her parity which was different from the king's before, but there is no reason in doing a waiting move before you know for sure she's not on the same parity as you are).
More greedy ways of thinking boil down to the same idea, my first solution needed 3(n-2) , but had redundant waiting moves. I feel like 2(n-2) is the most effective in a worst case scenario perspective.