The problem is a generalization of this uyhip riddle. A similar puzzle has also been discussed in Puzzle Toad.
A prisoner has been trapped in a dark room, and he can only escape if he could successfully solve out the following puzzle:
In front of the prisoner is a large circular table with $n$ poker cards equidistantly placed along the perimeter of the table. He can feel the cards but cannot tell if each one of them is face-up or face-down due to the darkness. The prisoner is allowed to turn over any subset of the cards each time. Once he finishes doing so, a check will be made and the prisoner will be freed if all cards are face-up.
Unfortunately, the table will be rotated by a supervisor after a fixed number of tries. After each rotation, the prisoner will be unable to recognize the previous position of any of the cards. Furthermore, the supervisor knows exactly the prisoner's strategy and will always rotate the table in a way to hinder the prisoner's success.
Now we let $\varphi(n)$ be the least number such that the prisoner may come up with a winning strategy in finitely many times when table is rotated after every $\varphi(n)$ tries.
It has been already proved that
$$\varphi(2^k)=1,\qquad \forall k\textrm{ non-negative integer}.$$
It is also easy to show $\varphi(3)\leq 3$. And I believe we actually have $\varphi(3)= 3$. Here goes the questions:
-
Is it true that $\varphi(5)\leq 5$? In general, do we have $\varphi(n)\leq n$?
-
Is it true that $\varphi(2^k m)=\varphi(m)$, where $m$ is odd?
-
Do we have an explicit formula for $\varphi(n)$?
Any help would be appreciated.
Best Answer
I wrote a program to solve this by modeling it as a graph problem in the following way:
The nodes are the possible states the cards may be in (not counting the one where all cards are face-up) + how many rounds has passed since the table was rotated. The edges are subsets of the cards we may flip. We start at the node where all states are possible and traverse the graph until we reach one where the only possible state is the one where all cards are face-up. The source code can be found here, there is one implementation in Python and one in Rust.
As this is a pretty brute-force approach, it doesn't scale very well. I've tried some further optimizations but I haven't been able to calculate $\varphi(6)$ yet. Still, what I have found is that:
$\varphi(3)=3$, $\varphi(5)=6$, and $\varphi(6)>4$.
This shows that the answers to your first and second questions are both no.
Edit:
I've found that $\varphi(6)=5$. Calculating this took 7 hours of compute, even though I added several optimizations, small and big (some specialized for when $n < 7$).
One thing to note is that I only do a simple depth-first search of the graph. Finding the node where all cards must be face-up could be much faster if you used some kind of heuristic (such as decreasing the number of possible states). The problem is that this wouldn't be very useful to find lower bounds as that forces you to explore the whole graph anyway.