15
$\begingroup$

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 $\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.
Improve this question
$\endgroup$

3 Answers 3

Reset to default
20
$\begingroup$

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 $2^{n-1}-1$ days. On the $2^{n-1}$th day, the first villager leaves. $2^{n-2}$ days later, the second villager leaves. This continues until the last villager leaves on the $2^n-1$th day.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Fast and fantastic answer! I'll hold off accepting for a bit in case anyone else wants to try, but this is the sort of thing I was hoping for. Even with 43 villagers you're approaching the age of the universe deduction time ... $\endgroup$
    – Tyler Seacrest
    Commented Sep 22, 2015 at 15:33
  • $\begingroup$ @f" The "common knowledge" is that they all know (a) when the light is supposed to switch off (b) the fact that it is still on. $\endgroup$
    – ghosts_in_the_code
    Commented Sep 23, 2015 at 7:12
  • $\begingroup$ Do the villagers know how many people are sitting behind them? It seems that this is quadratic? ($n$ days for the first to leave). $\endgroup$
    – Dr Xorile
    Commented Sep 24, 2015 at 1:23
  • 1
    $\begingroup$ @DrXorile The villagers know $n$, so they can figure out how many people are behind them by subtracting the number of people they see. $\endgroup$
    – f''
    Commented Sep 24, 2015 at 1:39
  • 1
    $\begingroup$ @DrXorile It would be quadratic if villagers knew when people behind them leave. Otherwise, I think it's exponential. $\endgroup$
    – f''
    Commented Sep 24, 2015 at 1:41
1
$\begingroup$

These puzzles break my brain, but I'll give it a shot:

Edit: This is wrong, this is just another quadratic version.

There are n islanders, each wearing a hat with a number on it. It's common knowledge that they are all wearing hats with non-negative integers on them, and they can all see each others' hats, but nobody knows their own hat number. At midnight, any islander that knows they are wearing a hat with the smallest number (or tied for smallest) of those on the island must leave on the ferry.

One day, an oracle shows up and tells them that nobody is wearing a hat with a number greater than m. Suppose that everybody actually has the number 0 on their hat. What happens?

Let n=m=100. I think that after the first night, it's now common knowledge that there are at least two people with hats less than 100, since everybody who sees 99 people with hats saying 100 would have left, and nobody left. After that, though, we can only rule out one specific configuration each night: after night 2, we know that it's not [99]*2, [100]*98. After night 3, we know that it's not [99]*3, [100]*97. After 100 nights, we know that there is at least one person who has neither a 99 nor a 100, and so on. Once all possibilities except a hundred zeros have been eliminated everybody leaves at once.

So I think the time is about m^n (something like m^n - m). If we arbitrarily constrain m to be equal to n, then we get better than exponential growth. With constant m it's exponential in n.

Edit: Nope, everything but the last paragraph is right (I think) but then I got the actual math wrong. It's just m * n as pointed out by f''.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think this is only m times n. Every n days, one possible smallest value is eliminated. Within those periods, the number of people who could have that value if it was the smallest decreases by 1 each day. $\endgroup$
    – f''
    Commented Sep 23, 2015 at 15:39
  • $\begingroup$ For example, with *m*=*n*=100, after 100 nights, it is known that the smallest value is at most 98. Then, if there was one person with 98 and the rest had 99 or 100, then that person would leave. If there were two people with 98 and the rest had 99 or 100, the 98s would leave the next day instead, and so on. $\endgroup$
    – f''
    Commented Sep 23, 2015 at 15:41
  • $\begingroup$ You're right, I was miscounting since all "[99]*2, [100]*98" cases are equivalent and thus eliminated at the same time but I was counting them as distinct. $\endgroup$
    – histocrat
    Commented Sep 23, 2015 at 15:47
0
$\begingroup$

I'm hoping that the following Q increases the time exponentially, but I don't know the answer myself.

Knowledge about common knowledge (hats puzzle)

@f" Yes, I have mostly copied it from you. Thanks for the idea. (Must I apologise?)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.