Finding The Mad Prince

Question

The prince has gone mad and no one can find him! Now, our good luck has it that the prince's madness compels him to always sleep in one of the $6$ royal bedrooms assigned to him - and, for convenience, these rooms have been labelled from $1$ to $6$. Moreover, our prince is sticking rigorously to a routine: He has chosen some cycle of bedrooms to sleep in each night and this cycle is free of repetitions. For instance, if we make a list $s_1,s_2,\ldots$ where $s_i$ is the room he sleeps in on the $i^{th}$ night, all of the following are possible (using just the first three rooms): $$3,2,1,3,2,1,\ldots$$ $$1,3,1,3,1,3,\ldots$$ $$2,2,2,2,2,2,\ldots$$ whereas none of the following are possible: $$3,2,1,2,1,2,\ldots$$ $$1,1,3,1,1,3,\ldots$$ $$1,3,1,2,1,3,1,2,\ldots.$$

You are the royal-prince finder. It is your job to find the prince as fast as possible. You are permitted to wait for the prince in one bedroom each night and you may choose the bedroom you sleep in freely each night. If the prince sleeps there, you will see him and will have completed your job. If the prince does not, you will see nothing.

Now, the king is a patient king - at least as far as kings go - and is willing to forgive you if the prince happens to choose the cycle that evades your strategy for the longest - but if the king ever finds a strategy which guarantees a faster discovery of the prince than yours, it will be off with your head!

Being the royal prince-finder under such conditions, you wonder: What is the strategy that guarantees finding the prince in the least number of nights?

Answer 1

65555543333321111 does it in 17 days.

$\bullet$ All cycle of length 6 has either 5 or 3 on days 2-6, which are repeated on days 8-12.
$\bullet$ Any cycle of length 5 has either a 5 or a 3, which is caught because they are repeated five times in a row.
$\bullet$ Any cycle of length 4 has either 5, 3, or 1, which is caught because they are repeated four times in a row.
$\bullet$ For cycles of length 3 or less, all six rooms are visited on the first day of the cycle, so they are caught.

Proof that this is the best possible:

If we have a plan to find the prince, we can

express it as a string of digits 1 through 6.

Now

imagine writing this list in a table with $n$ columns, where $1 \le n \le 6$.

If we can choose a different number for each column such that each number doesn't appear in its corresponding column, then the plan fails because the prince could be using that as his cycle. Hall's marriage theorem states that we can find these numbers if and only if for every group of $x$ columns, there are at least $x$ numbers which are absent from at least one column in that group.

So...

...if we want to cover all of the prince's possible cycles, we must have some group of $x$ columns such that there are at least $7-x$ numbers that appear in every one of those columns.

Suppose

there is a solution in 16 days.

When we arrange it with 4 columns, each column has 4 numbers. Either 4 numbers appear in each of 3 columns, or 3 numbers appear in every column. When we arrange it with 5 columns, there are 4 columns of 3 and 1 column of 4. Either 3 numbers appear in four columns, or 2 numbers appear in 5 columns. Also, every number must appear at least once, in case the prince never changes rooms. If the layout with 4 columns has 4 numbers appearing 3 times each, then there must be either (4+4+4+3+1+1) or (5+5+3+3+1+1) numbers total, but both of these are greater than 16, so it is impossible.

Therefore...

...with 4 columns, there must be 3 numbers that appear 4 times each.

Now

if we write the numbers with 3 columns, there are 2 columns of 5 and 1 column of 6. Either 4 numbers appear in all 3 columns, 5 numbers appear in 2 columns, or all 6 numbers appear in 1 column. The first two cases require (4+4+4+3+1+1) or (4+4+4+2+2+1) numbers, which are both greater than 16, so it must be all 6 numbers in the first column.

If we write the numbers with 6 columns, there are 2 columns of 2 and 4 columns of 3. Either 3 numbers appear in 4 columns, 2 numbers appear in 5 columns, or 1 number appears in 6 columns. The second and third cases require (5+5+4+1+1+1) and (6+4+4+1+1+1) numbers, which is also too many.

So...

...there must be 3 numbers appearing in each of the 4 columns with 3 spaces. This means that the other three numbers cannot appear in those four columns.

However...

...these four columns include all the spaces from the first column in the 3-column layout, so all 6 numbers must appear in them. This is a contradiction, so

it is impossible to have a solution in 16 days.

Answer 2

this cycle is free of repetitions

Makes it clear that the cycle will be, at most, as long as the number of rooms he visits.

I would begin, therefore, by visiting room 6 (I begin by room 6, rather than 1, just to make numbers coincide). I can't be sure he won't use it until 6 nights had passed, since he could visit it the 6th night.

If, after 6 nights he hadn't visited room 6, it means, at most, prince's cycle visits 5 rooms. Therefore I'd stay 5 nights at room 5.

Same is true for the rest of the rooms...

So I'd stay, 6 nights in room 6, 5 in room 5, 4 in room 4, 3 in room 3, 2 in room 2 and 1 in room 1.

At the end, my visiting pattern is: $$6,6,6,6,6,6,5,5,5,5,5,4,4,4,4,3,3,3,2,2,1$$ So after $21$ nights I'm guaranteed to find the prince.

I think this is the fastest strategy that garantees to find the prince whichever strategy he uses, though if there's a fastest strategy that garantees that, it must use somehow the divisors of each of the numbers (just a guide in case someone wants to follow my lead).