O princess, where art thou?

Question

In the highest tower of her castle, a princess has N bedrooms which are arranged in a circle. She never sleeps in the same room on two consecutive days. Every morning she moves to another room by advancing the same number of rooms along the circle (in the same direction).

A secret admirer of her is aware of this and tries to visit her at night by climbing the tower. However, he does not know her current location nor the fixed number of rooms that she moves every morning. Moreover, each night he can only inspect one room before the guards might catch him. Can the admirer think of a strategy to find the princess with certainty in a finite time? If so, how? What is the smallest number of rooms that he must inspect (in the worst case scenario)?

Here are some reflections:

Yes, he can find the princess in finite time since the space of possibilities is only finite. Label the rooms 0, 1, 2, …, N-1. We call “a” the position of the princess on day 0 and “b” the number of rooms that the princess moves every morning. The position of the princes on day t is then equal to (a+bt)(mod N). Since a can take N values (from 0 to N-1) and b can take N-1 values (from 1 to N-1). The total number of possible trajectories for the princess is N(N-1). We can check each of these possibilities separately. Suppose we want to eliminate the possibility (a,b) on day t, then we must visit room (a+bt)(mod N). Therefore the necessary number of checks is bounded from above by N(N-1). However, this upper bound is too crude, since one can eliminate multiple possibilities by checking a single room.

The necessary number of checks is bounded from below by N. Imagine that we make N*(N-1) copies of the princess, where each copy follows a different possible trajectory. Then each night there must be exactly N-1 copies of the princess in each room, coming from 1, 2, 3, …, N-1 rooms back in the circle the night before. So by checking a single room on some night, we can eliminate at most N-1 possibilities. Therefore at least N checks will be necessary. This lower bound can actually be obtained whenever N is a prime number. The admirer just has to check the same room on N consecutive nights.

My main question is this:

What if N is a composite number? What is the best strategy for the admirer to find the princess with certainty in the least number of nights? Can the lower bound still be obtained? How (or why not)?

Answer 1

The lower bound can't be obtained if $N$ is composite, because

We can see that: to obtain the lower bound, we have to inspect different copies of the princess every day. So

- if the admirer inspects the same room every day, the princess may never use this room.
- if the admirer inspects the $i$-th room someday and the $j$-th room on the next day, then he will inspect the same copy (with a step length $j-i\bmod N$) twice.

And here is my strategy for the admirer (probably not the optimal):

Check the $i$-th room for $\max\limits_{j|N,i<j<N}N/j$ days, continuously. The rooms are 0-indexed here.

For example, if $N=6$, the admirer checks room $0,0,0,0,0,0, 1,1,1, 2,2$ on each day.

Correctness: We call $a$ the position of the princess on day 0 and $b$ the number of rooms that the princess moves every morning. The admirer can find the princess when he checks the room $b\bmod \gcd(a, N)$, and he will not check that room for more than $\gcd(a, N)$ when he finds the princess.