Of course, I could trivially I could do the following: Suppose $n$ is the number of inhabitants, and the maximum size number on their heads is $n$, and they each have forehead number either $\lfloor n/2 \rfloor$ or $\lfloor n/2 \rfloor + 1$. Then the amount of time it takes to discover their numbers is roughly proportional to $n^2/2$. Thus, by increasing $n$ I can increase the amount of time quadratically. But I was wondering if it was possible to do better yet.
Is there a way to design a Blue-Eyes-like logic puzzle where the amount of time for the islanders to figure out the answer is exponential in the size of the problem?
A couple notes
- I don't know if this is possible -- my attempts so far haven't done very well. Even rough ideas or explanations as to why it might not be possible would be appreciated.
- Anything about the problem can be changed I'd say: for example, perhaps not everyone can see everyone else. However, the core mechanic of ever increasing common knowledge should remain. Ideally, it would also be a simple to state puzzle, and perhaps with some other twists and turns for any potential puzzle solver.
- Suppose the islanders are immortal -- just in case the solution to your puzzle outpaces a person's expected lifetime.