Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[liopoil]

The second person can.

They see a black hat. They know that if they have a black hat as well than the person in the back will see two blacks and will say white. When the person in the back doesn't say white the second person knows that their hat must be white.

[Polk5440]

I love the blue eyed islanders problem because it shows what a strong/important assumption common knowledge is and helps you to understand the difference between Nth level knowledge and common knowledge.

[jonts26]

Another hat problem (the first one I ever heard):
Four buys are captured, yadda yadda,  and put, buried in sand up to their necks, into the following arrangement:
O O O | O
Where O represents a guy's head and | represents a wall that can't be seen through. All of them are facing the direction that corresponds to right in the above diagram. They are told that two of them will have white hats on their heads, the other two black hats. The first thing any of them says must be their own hat color; if they do this, all are freed; if not, they are all executed.
The hats are put on them in the order Black/White/Black|White. Who is able to free them all (none of them, one, or multiple people; if more than 0, specify which)?

So only one person has to say their hat color?

The guy in second position should know the color of his hat. If he and 3rd position had the same color hat, guy in first position would be able to immediately know his hat was the opposite color. After waiting a while, second position knows first position says nothing, thus indicating his own hat is different than the guy in front of him.

[Ozle]

Second guy can sayhis. Because he knows if he is the same as the guy in front of him the guy at the back would know his hat, therefore he must have a different colour to the guy in front

[Titandrake]

Woops was on wrong page.

[Jimmmmm]

A follow-up I thought of for the pirate one:

7 pirates have just ended plundering the Caribbean, so they get together to discuss how they will share the 100 gold coin booty. Now, these aren't your normal kind of pirates, they are blood-thirsty, unlimitedly greedy, perfectly rational pirates, and they are ranked by fighting prowess.

Thus, the captain has to propose how to share the booty, knowing that if more than half of his crew starts a mutiny, he will get killed, and the 2nd in command will take his place (who will in turn have to propose how to share the booty, eventually being replaced by the third in command, etc.).

How much gold will each pirate receive?

How does this change if each pirate is also completely truthful and trustworthy?

[Titandrake]

A follow-up I thought of for the pirate one:

7 pirates have just ended plundering the Caribbean, so they get together to discuss how they will share the 100 gold coin booty. Now, these aren't your normal kind of pirates, they are blood-thirsty, unlimitedly greedy, perfectly rational pirates, and they are ranked by fighting prowess.

Thus, the captain has to propose how to share the booty, knowing that if more than half of his crew starts a mutiny, he will get killed, and the 2nd in command will take his place (who will in turn have to propose how to share the booty, eventually being replaced by the third in command, etc.).

How much gold will each pirate receive?

How does this change if each pirate is also completely truthful and trustworthy?

Not the full answer. I'm assuming that the captain must propose before anyone else can talk, and that the captain cannot change his proposal once the pirates start talking.

The 2 pirate case is easy: 100, 0

3 pirate case: Second pirate will always vote no even if given 100 coins because the pirates are bloodthirsty. So the split is 100-n, 0, n for some n. For any n, the 2nd pirate can promise to split it 100-n, n, and 3rd pirate will vote no because they are bloodthirsty. So, the captain dies.

4 pirate case: Starts getting tricky here, because promises made in this round of proposals can carry over to the next one, and they could start contradicting. Rest later.

[Jimmmmm]

A follow-up I thought of for the pirate one:

7 pirates have just ended plundering the Caribbean, so they get together to discuss how they will share the 100 gold coin booty. Now, these aren't your normal kind of pirates, they are blood-thirsty, unlimitedly greedy, perfectly rational pirates, and they are ranked by fighting prowess.

Thus, the captain has to propose how to share the booty, knowing that if more than half of his crew starts a mutiny, he will get killed, and the 2nd in command will take his place (who will in turn have to propose how to share the booty, eventually being replaced by the third in command, etc.).

How much gold will each pirate receive?

How does this change if each pirate is also completely truthful and trustworthy?

Not the full answer. I'm assuming that the captain must propose before anyone else can talk, and that the captain cannot change his proposal once the pirates start talking.

The 2 pirate case is easy: 100, 0

3 pirate case: Second pirate will always vote no even if given 100 coins because the pirates are bloodthirsty. So the split is 100-n, 0, n for some n. For any n, the 2nd pirate can promise to split it 100-n, n, and 3rd pirate will vote no because they are bloodthirsty. So, the captain dies.

4 pirate case: Starts getting tricky here, because promises made in this round of proposals can carry over to the next one, and they could start contradicting. Rest later.

Pretty much my exact thoughts.

[Titandrake]

A follow-up I thought of for the pirate one:

7 pirates have just ended plundering the Caribbean, so they get together to discuss how they will share the 100 gold coin booty. Now, these aren't your normal kind of pirates, they are blood-thirsty, unlimitedly greedy, perfectly rational pirates, and they are ranked by fighting prowess.

Thus, the captain has to propose how to share the booty, knowing that if more than half of his crew starts a mutiny, he will get killed, and the 2nd in command will take his place (who will in turn have to propose how to share the booty, eventually being replaced by the third in command, etc.).

How much gold will each pirate receive?

How does this change if each pirate is also completely truthful and trustworthy?

Not the full answer. I'm assuming that the captain must propose before anyone else can talk, and that the captain cannot change his proposal once the pirates start talking.

The 2 pirate case is easy: 100, 0

3 pirate case: Second pirate will always vote no even if given 100 coins because the pirates are bloodthirsty. So the split is 100-n, 0, n for some n. For any n, the 2nd pirate can promise to split it 100-n, n, and 3rd pirate will vote no because they are bloodthirsty. So, the captain dies.

4 pirate case: Starts getting tricky here, because promises made in this round of proposals can carry over to the next one, and they could start contradicting. Rest later.

Pretty much my exact thoughts.

More thoughts (no solution yet)

Let's say there are 7 pirates. The captain proposes a split, which I'll label A,B,C,D,E,F,G. The 4th to last pirate can say, "If the 3rd last, 2nd last, and 1st last pirate vote no with me, I will propose D_2,E_2,F_2,G_2 (with D_2 >= D, E_2 >= E, F_2 >= F, G_2 >= G)" Because the pirates are bloodthirsty, the last 4 pirates will all agree to vote no and kill the captain. A similar argument can be done for any number of pirates (except 2), so the first captain will always die.

The tricky part is that the 4th to last pirate will know this, and knows that if he is the captain and hasn't made the others agree to a promise to pass his proposal, he will die. He can ask the others to vote no until he is the captain, but some of the pirates won't agree. My guess is that it is impossible for the 4th last pirate to design a promise that ensures he does not die. If such a promise is made, the other pirates can simply disagree.

The correct answer might actually involve the first half of pirates making an agreement to vote yes because otherwise they'll all die, but balancing it with bloodthirsty makes it tricky.

[pacovf]

I'd put the order of priorities of pirates this way:
-Survive
-Earn as much money as possible
-Kill as many pirates as possible

So, in the case that pirates are perfectly trustworthy, a follow-up to Titandrake's post:

[EDIT: actually, it doesn't work; I'm still thinking on it, but I forgot that in a 4 crew ship, any deal that doesn't involve the captain requires all other pirates to agree, so that they represent the majority]
-With 4 pirates, if no promise is made, the second pirate will accept whatever the captain offers, 0 coins included, or otherwise he will die, as Titandrake said.
However, the third pirate can strike a pact with the second pirate: if he votes against the captain, he will accept a 0, 100, 0 split afterwards, which the second pirate and fourth pirate would normally accept, since that way they kill one extra pirate; but the fourth pirate can also offer a 0,0,100 split, which is equivalent for the second captain; as such, they will both rise their offers until they both reach 99 coins for the second pirate and one coin for the relevant pirate, so that doesn't seem like a very good split for the third or fourth pirates. Assuming (*), this means a 99, 1, 0 split.
Thus, the captain (a bit nervous since everybody is discussing his death) will instead try to earn the loyalty of the third or fourth pirate, and one coin for the fourth pirate should suffice , since otherwise he would earn nothing. But! Whatever 100-n, 0, 0 n split the captain proposes, the second pirate can offer the same to either the third or fourth pirate, and they will accept, since they are bloodthirsty. As such, the captain, trying to survive, will offer the 100 coins to either the third or fourth pirate, and the second pirate, seeing that he will earn nothing, will also offer 100 coins to either the third or fourth pirate, as he is bloodthirsty.
Probably before reaching that point, the captain and the second in command will realize that it may be better to reach an agreement between them, but that's prisoner dilemma: if the captain offers a 100-n, n, 0, 0 split, the second pirate could accept, or try to get a better deal with either the third or fourth pirate, which is always possible, since a 0, n, 0, 100-n split seems better for him (he gets to kill the captain); but that reasoning leads to a 0, 0, 0, 100 split (according to the previous paragraph), which is worse than the previous 100-n, n, 0, 0 split...

Adding extra rules about how and when the pirates can strike a deal would make this quite easier... or solvable...

*I would add that, if a pirate has the choice among more than one deal that are equivalent to him (according to the three laws of buccaneering above), he will choose the one proposed by the highest ranking pirate. It can shave some lines of discussion for higher number of pirates.

[qmech]

Here's my favourite hat problem.  It might not be quite right for this thread, but I'll throw it out there anyway.

A countable infinity of people are all standing in a line and wearing a black or white hat.  Everybody can see the colours of the hats of the (infinitely many) people standing in front of them.  They must all simultaneously shout out a guess as to the colour of their own hat.  Can they ensure that only finitely many people guess wrong?

[liopoil]

AHHH! INFINITY! 

Can they talk before announcing at all?

[qmech]

Yes, they can make whatever (mathematically ideal) arrangements they like.  And, if you decide it matters, there is a first person, at the back of the line, who can see everybody else.

[Galzria]

Are they spaced close enough to touch one another? If so then it's easily solvable for (Infinty - 1), with a 50% chance of all of them guessing correctly.

However, I don't think that's to the spirit of the question.

[DStu]

Can they ensure that only finitely many people guess wrong?

I'd love to be convinced otherwise, but: No.

Edit: Ok, I see a slim path that might work...
Hats are black/white with probability 1/2 and independent?

Edit2: A very slim path...

[liopoil]

yeah. After they have the hats on they have absolutely no means of communication... so it should be impossible.

[qmech]

The hats colours are chosen by the devil after you've decided on your strategy.  And no touching!

[Grujah]

is infinite time available?

[qmech]

is infinite time available?

Yes, and more.  Any precisely stated strategy would be legal, regardless of whether or not it could actually be implemented in a physical universe.

[DStu]

The hats colours are chosen by the devil after you've decided on your strategy.  And no touching!

Then no.

Edit: Except if I may use non-euklidian geometry.

[Grujah]

is infinite time available?

Yes, and more.  Any precisely stated strategy would be legal, regardless of whether or not it could actually be implemented in a physical universe.

How do they coordinate the exact moment when they all shout it together?

[qmech]

They all know in advance.  Or any other answer that prevents them passing information that way: for example, they could each write down their guesses on a piece of paper that nobody else can see.

[Watno]

I think I heard this one before and didn't get it, but i remember it only worked with the Axiom of Choice

[DStu]

I think I heard this one before and didn't get it, but i remember it only worked with the Axiom of Choice

If  I remember correctly, Axiom of Choice follows from the rest of ZF if you only have sets with 2 elements.  But could be wrong...

[Watno]

The Axiom of Chioce is trivial for all countable sets, but I don't see how that matters?