Complexity to Simplicity and Back Again

Generalizing a problem can make the solution simpler or more complicated, and it’s often hard to predict which beforehand. Here’s a mini-example of a puzzle and four generalizations which alternately make it simpler or more complicated.

Warning: The solutions are given right after the puzzles. If you want to think about them, cover the screen.

Puzzle: There are 10 prisoners labeled P=\{1,2,\ldots,10\}. A malicious warden puts a black or white hat on each. Prisoner i can see prisoner j‘s hat iff i < j. The warden has each prisoner guess the hat color on their head, in order starting from prisoner 1. The prisoners can hear previous guesses.

If a prisoner guesses right, they are freed, otherwise they are sent back to jail. Given that the prisoners can strategize as a group beforehand, for how many prisoners can they guarantee freedom in the worst case?

It turns out that the prisoners can guarantee the freedom of all prisoners except prisoner 1: Prisoner 1 first counts the number of black hats, then guesses black if it’s even and white if it’s odd. Now prisoner 2 knows their hat color, since they heard prisoner 1′s guess and they can count the number of black hats they see. Once prisoner 2 guesses correctly, prisoner 3 can guess correctly using prisoner 1 and 2′s answer, and so forth.

Generalization 1:What if there are 3 hat colors? What if there are n hat colors? What if the hat colors are drawn from an arbitrary, possibly infinite set S?

This generalization makes the solution simpler, since it reveals something about what was going on in the first solution.

As long as the prisoners can put a group structure on the hat colors, they can run the same strategy as before: Player 1 adds up all the colors and announces that. Each subsequent player adds up all the colors they can see and the correct guesses, and subtracts that from the sum that player 1 announced.

Generalization 2: What if P=\{1,2,3,\ldots\}, i.e., there are infinitely many prisoners, arranged like \mathbb{N}?

The solution to this generalization makes things more complicated: it uses a trick which is not related to the previous problems, and which is not clear how to generalize.

It turns out there is still a strategy to free all but the first prisoner.

Here’s the new trick: Consider the set S of all possible assignments of hat colors to prisoners. Let s\equiv t for s,t\in S iff s agrees with t for all but finitely many prisoners. This is an equivalence relation. Beforehand, the prisoners choose a representative from each equivalence class (this requires the axiom of choice).

Since each prisoner can see all but finitely many of the other prisoner’s hats, each prisoner knows which equivalence class they’re in. Then the solution is similar to before: The first prisoner adds up the finitely many differences between the hat colors and the chosen representative, and the subsequent ones can then all correctly deduce their own hat color.

Generalization 3: What if P is an arbitrary ordinal? What if P is an arbitrary linear ordering?

This solution makes things simpler, as it reveals what was going on in the previous solution. This problem was solved by Chris Hardin and Alan Taylor.

The answer is that, for P an arbitrary linear order, the prisoners have a strategy that does not use communication (i.e., nobody can hear anyone else’s guess) and guarantees that the set W of prisoners who guess wrong does not have an infinite ascending chain.

If P is an ordinal, this guarantees that W is finite, and then the prisoners can use communication to save all but the first prisoner. If P is the reals, then this guarantees that they can free all prisoners except those in a set of measure zero.

The solution is surprisingly simple. The prisoners agree beforehand on a well-ordering \leq of the set of assignments of hat colors to prisoners, then each prisoner takes the \leq-least assignment consistent with what they can see, and guesses the hat color they have in that assignment.

As an exercise, try showing that an infinite ascending sequence of wrong guesses would translate into an infinite descending sequence of hat color assignments, and thus contradict well-ordering.

Generalization 4: What if P is just a relation, not necessarily transitive?

Chris Hardin and Alan Taylor considered this generalization in this paper. It turns out that things become complicated again.

For example, suddenly the number of different hat colors matters. Hardin and Taylor prove the following striking theorem:

Theorem: Suppose the prisoners are labeled 1,2,3,\ldots and that each even can see all higher-numbered odds and each odd can see all higher-numbered evens. Suppose that no prisoner can hear anyone else’s guess. Then:

  1. If there are 2 hat colors, the prisoners have a strategy guaranteed to save infinitely many prisoners.
  2. If there are \aleph_2 hat colors, the prisoners have no strategy guaranteed to save anybody.
  3. If there are \aleph_0 hat colors, whether or not the prisoners have a strategy that can save anybody is independent of ZFC.
About these ads

5 Comments

Filed under Uncategorized

5 responses to “Complexity to Simplicity and Back Again

  1. Frank Vega

    Hi people
    Could I have your opinion about one post “P versus UP” in:

    http://the-point-of-view-of-frank.blogspot.com/

    ?
    Thanks

  2. Jason

    Great Puzzle, though it should be made clear that the warden has N black hats and N white hats, depending on the number (N) of prisoners. If he just puts black or white hats on the prisoners at random and without bounds there could be all black or all white hats.

  3. Amit

    In generalization 1, how can all prisoner saved except 1st ? You said if prisoner are able to put group on hat colors (I understand u mean if they are able to communicate information about colors of others’ hats with guesses , can u please give an example for 4 colors.)

    What I understood is in case of 3 colors ,1st prisoner can tell about color 1′s parity and 2nd prisoner can tell about 2nd color’s , from that onwards another prisoner can tell about their colors.This make sure all prisoners can be saved definitely but first 2.

    • yot

      @Amit
      You have not factored in the fact that more information can be conveyed since there are more colors. This was not explained in the article so don’t blame yourself for not following. Think of this if you will:

      Assume there are N hat colors. The prisoners assign a number to each color {0,1,…N-1}. The first prisoner then adds up all of the colors he sees and divides the number by N. He then figures out the remainder and states it (by it’s corresponding color). He has a bleak 1/N chance of surviving. The rest have guaranteed safety though. The next prisoner also adds up all of the colors he sees to figure out which color should be added to get the previous result announced (you can prove there is one and only one answer to this at all times). Now he knows which color he is wearing. Any prisoner following adds up the colors he sees, adds the colors announced by the previous prisoners (except the first) and derives what color he’s wearing like the 2nd prisoner did.

  4. Bruce Smith

    In Generalization 2, the solution presented doesn’t *only* require the axiom of choice — it requires that a group of prisoners can select and agree on a single choice of representatives, even though no such choice can be computable or finitely describable (so there is no way one of them could either imagine one choice, or communicate it to others, if they were finite beings). I.e. the prisoners have godlike powers. (Of course, if they could see an infinite number of hats in the first place, I guess they did anyway.)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s