I created a variant of the Blue Eyes problem where the logic took 4901 days (over 13 years) to totally play out. I thought this was nice, but I was hoping for an even longer period of time.
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 ⌊n/2⌋ or ⌊n/2⌋+1. Then the amount of time it takes to discover their numbers is roughly proportional to n2/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.
Answer
This might not qualify as a blue-eyes puzzle because it does not use common knowledge, but it involves chains of deductions based on nothing happening for a particular amount of time:
n villagers wear either black or white hats. They sit in a line, so that each villager can see all the hats in front of them, but not the hats behind them. If a villager ever deduces their own hat color, they get up and leave the line at noon on the next day (without anyone in front noticing).
One day, a light is installed where all villagers can see it. The light remains on as long as at least one villager in the line has a black hat.
If the villagers all have black hats, nothing happens for the first 2n−1−1 days. On the 2n−1th day, the first villager leaves. 2n−2 days later, the second villager leaves. This continues until the last villager leaves on the 2n−1th day.
No comments:
Post a Comment