Wednesday, September 13, 2017

mathematics - Exponential time in a Blue Eyes variant


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 2n11 days. On the 2n1th day, the first villager leaves. 2n2 days later, the second villager leaves. This continues until the last villager leaves on the 2n1th day.


No comments:

Post a Comment

classical mechanics - Moment of a force about a given axis (Torque) - Scalar or vectorial?

I am studying Statics and saw that: The moment of a force about a given axis (or Torque) is defined by the equation: $M_X = (\vec r \times \...