A simple (*not* bonanova 'simple') hat problem

[Yoruichi-san]

Having grown ennuied of torturing prisoners on death row with hat problems (after all, where was the suspense if they had nothing to lose?), the sadistic king decided it was time to expand his horizons.

As luck would have it, today was the day the fishermen's guild was sending its tribute, brought by five of its most capable members. After graciously receiving a crate of fresh, lovely salmon, mahi mahi, and white tuna, the king thanked his guests by promptly ordering their arrest.

"But what did we do?" the unfortunate artisans asked.

"You are harming the kingdom. Your practices are not..." the king searched for the politically correct buzzword of the day, "...sustainable. Hence, you will be put to death."

The fishermen pleaded and begged for mercy. The king reclined in his throne, covering his smile with his generously ringed hand, and savored the moment. Finally, he raised the hand for silence.

"I am a benevolent and fair ruler," he proclaimed, "Hence, I will allow you one chance to save yourselves." He gestured to his manservant, who, all too familiar with the drill by now, went to fetch his box of hats. The king continued, "After my manservant returns, I will have you all stand, facing the directions I specify, with eyes closed, in a circle in front of me." He gestured towards the expansive floor of the throne room. "Then I will have my manservant place a hat on each of your heads. There are three white hats and two black hats. Without speaking or moving in any way other than I direct, you must determine what color the hat on top of your own head is, and when you do, you may raise your hand and my manservant will come to you and you may whisper the color in his ear."

"So if one of us figures out the color of out hat, we all go free?" asked one fisherman who had heard mention of the king's tyrannical games before.

But the king shook his head in a lordly manner. "You must ALL determine the color of the hat you each wear. If one man declares an incorrect color, you will all be executed."

"But, surely, you can't expect us to figure out the color of our hat with no information...your majesty," another fisherman protested.

"Of course not," the king stated. "I am much too beneficient." He nodded towards a large bronze gong residing in one corner. "When the gong sounds the first time, the man closest to me may look at the hats of the two standing closest to him. When the gong sounds the second time, the two men farthest from me may look at each other's hats, and the hat of the man standing closest to me. When the gong sounds the third and final time, the remaining two men may look at each other's hats. My guards will be stationed closely to prevent cheating. If cheating is attempted, you will all be executed."

The fisherman shot glances at each other. "But, your munificent majesty," one finally spoke, "we need something more, if we are not allowed to speak or move other than to look or raise our hands."

"Well, too bad," the king replied, yawning. "That's all I'm giving you."

The most diminutive and bravest of the fishermen asked, "What if we use something we already have? Then you don't have to give us anything."

The king stroked his chin. The only thing the men had on them, besides their clothes, was fishing line. He shrugged. "Sure, let's just get this party started."

The fisherman huddled together for a few moments, then positioned themselves as directed, evenly spaced in a large circle. Shortly, the manservant returned with the hats and the game was afoot.

What is the maximum number of the fisherman that can raise their hand after the second gong but before the third gong?

How will the fisherman standing closest to the king determine what color his hat is?

[Aaryan]

Holy Crap Mobile version is weird.

Anyway, can you specify how the circle works?

Edited May 11, 2012 by Aaryan

[Yoruichi-san]

Something like this, in a very big room, where 1 gets to look at the two 3's after the first gong (he starts facing outward but is allowed to turn to both sides slightly), the 2's get to turn to look at each other and then turn to 1 after the 2nd gong (closing their eyes in between, and directed by the king and his guards), and the 3's get to look at each other after the 3rd gong, and there is no cheating (or else there be mass beheadings). There may be another element to the circle...but that's kinda part of the puzzle ;P.

[Aaryan]

Calling them A's, B's, and C's to avoid ambiguity.

Ok, let's loom from A's perspective.

If he sees the C's and sees two white hats, he calls out that he has a black hat. The B's now know that they have black hats, since the C's have both white hats. C's then know that they have white hats, and everyone is happy.

A does not see two white hats and does not call out. Therefore, B's know that at least one of them (A and 2 B's) has a white hat.

Assume one of the B's sees a white hat on the other and a white hat on A. He now knows that he has a black hat. Then, using that as a cue the other B knows he has a white hat; same with A. The C's can then follow suit.

Or, one of the B's sees two black hats; he now knows that he MUST have a white hat, since the maximum number of white hats A could see on either of the C's is one.

It appears that the C's need to see each other before they can guess their hats.

The maximum number of fisherman who can know their hats before the third gong is 3.

As to the object they use, perhaps they use their fishing line to tell each other that they have guessed?

Edited May 12, 2012 by Aaryan

[plasmid]

Do the fisherman have a practically infinite amount of fishing line? And is it just one big piece or can it be cut it into several different pieces?

It should be doable fairly easily by tugging on string held by different fishermen when they see which color hats the others are wearing, if that doesn't lead to beheading.

[Yoruichi-san]

Calling them A's, B's, and C's to avoid ambiguity.

Ok, let's loom from A's perspective.

If he sees the C's and sees two white hats, he calls out that he has a black hat. The B's now know that they have black hats, since the C's have both white hats. C's then know that they have white hats, and everyone is happy.

A does not see two white hats and does not call out. Therefore, B's know that at least one of them (A and 2 B's) has a white hat.

Assume one of the B's sees a white hat on the other and a white hat on A. He now knows that he has a black hat. Then, using that as a cue the other B knows he has a white hat; same with A. The C's can then follow suit.

Or, one of the B's sees two black hats; he now knows that he MUST have a white hat, since the maximum number of white hats A could see on either of the C's is one.

It appears that the C's need to see each other before they can guess their hats.

The maximum number of fisherman who can know their hats before the third gong is 3.

As to the object they use, perhaps they use their fishing line to tell each other that they have guessed?

Good work, but not quite finished. To complete it, consider all possibilities, not just the most convenient ones. Alternatively, let's ask: What is the non-zero minimum number of fisherman who can raise their hand after the 2nd gong but before the 3rd gong? That is, if any raise their hands at all, what is the minimum?

Do the fisherman have a practically infinite amount of fishing line? And is it just one big piece or can it be cut it into several different pieces?

It should be doable fairly easily by tugging on string held by different fishermen when they see which color hats the others are wearing, if that doesn't lead to beheading.

You're definitely on the right string , but remember, they aren't allowed to move except to turn their heads in the specified directions to look, or to raise their hands to declare they know their color.

And yes, of course, it would have been easier to make the rules, and be effectively equivalent, if the positions of 2's and 3's were switched...but the king likes the feng-shui of this orientation, and, well, he is the king. ;P

Edited May 12, 2012 by Yoruichi-san

[Aaryan]

Good work, but not quite finished. To complete it, consider all possibilities, not just the most convenient ones. Alternatively, let's ask: What is the non-zero minimum number of fisherman who can raise their hand after the 2nd gong but before the 3rd gong? That is, if any raise their hands at all, what is the minimum?

The only possibilities I can see:

C's have 2 whites, variation 1.

C's have one black and one white, variation 2.

C's have two blacks, meaning one of the remaining (A or the B's) should see two whites and know their hat color, which should be covered in variation two.

Asking the question of minimum number is tricky, because if the five work together at least 3 should make it.

[Yoruichi-san]

I think I see where there may be some confusion. Let me clarify for those unfamiliar with my style: the two questions in the OP are separate, hence they are set in different paragraphs. The second question is not [specifically in the arrangement of the first question], but, in general, in any arrangement, how will the first fisherman figure out what color his hat is? I'm asking for an algorithm/set of rules that he should follow.

[bushindo]

Having grown ennuied of torturing prisoners on death row with hat problems (after all, where was the suspense if they had nothing to lose?), the sadistic king decided it was time to expand his horizons.

As luck would have it, today was the day the fishermen's guild was sending its tribute, brought by five of its most capable members. After graciously receiving a crate of fresh, lovely salmon, mahi mahi, and white tuna, the king thanked his guests by promptly ordering their arrest.

"But what did we do?" the unfortunate artisans asked.

"You are harming the kingdom. Your practices are not..." the king searched for the politically correct buzzword of the day, "...sustainable. Hence, you will be put to death."

The fishermen pleaded and begged for mercy. The king reclined in his throne, covering his smile with his generously ringed hand, and savored the moment. Finally, he raised the hand for silence.

"I am a benevolent and fair ruler," he proclaimed, "Hence, I will allow you one chance to save yourselves." He gestured to his manservant, who, all too familiar with the drill by now, went to fetch his box of hats. The king continued, "After my manservant returns, I will have you all stand, facing the directions I specify, with eyes closed, in a circle in front of me." He gestured towards the expansive floor of the throne room. "Then I will have my manservant place a hat on each of your heads. There are three white hats and two black hats. Without speaking or moving in any way other than I direct, you must determine what color the hat on top of your own head is, and when you do, you may raise your hand and my manservant will come to you and you may whisper the color in his ear."

"So if one of us figures out the color of out hat, we all go free?" asked one fisherman who had heard mention of the king's tyrannical games before.

But the king shook his head in a lordly manner. "You must ALL determine the color of the hat you each wear. If one man declares an incorrect color, you will all be executed."

"But, surely, you can't expect us to figure out the color of our hat with no information...your majesty," another fisherman protested.

"Of course not," the king stated. "I am much too beneficient." He nodded towards a large bronze gong residing in one corner. "When the gong sounds the first time, the man closest to me may look at the hats of the two standing closest to him. When the gong sounds the second time, the two men farthest from me may look at each other's hats, and the hat of the man standing closest to me. When the gong sounds the third and final time, the remaining two men may look at each other's hats. My guards will be stationed closely to prevent cheating. If cheating is attempted, you will all be executed."

The fisherman shot glances at each other. "But, your munificent majesty," one finally spoke, "we need something more, if we are not allowed to speak or move other than to look or raise our hands."

"Well, too bad," the king replied, yawning. "That's all I'm giving you."

The most diminutive and bravest of the fishermen asked, "What if we use something we already have? Then you don't have to give us anything."

The king stroked his chin. The only thing the men had on them, besides their clothes, was fishing line. He shrugged. "Sure, let's just get this party started."

The fisherman huddled together for a few moments, then positioned themselves as directed, evenly spaced in a large circle. Shortly, the manservant returned with the hats and the game was afoot.

What is the maximum number of the fisherman that can raise their hand after the second gong but before the third gong?

How will the fisherman standing closest to the king determine what color his hat is?

I would like some clarification. My impression is that whenever a participant raises his hand, the other 4 participant would be aware of this fact. For instance, if participant 1 raises his hand after the first gong sounding but before the second gong sounding, the other 4 participants would be aware that number 1 raised his hand, even though they would not know the color of 1's hat. Is this true?

[Yoruichi-san]

I would like some clarification. My impression is that whenever a participant raises his hand, the other 4 participant would be aware of this fact. For instance, if participant 1 raises his hand after the first gong sounding but before the second gong sounding, the other 4 participants would be aware that number 1 raised his hand, even though they would not know the color of 1's hat. Is this true?

That's the other part of the puzzle . Plasmid was very close, the answer to that part just needs to be refined to fit the specified rules laid down by his oh-so-munificent majesty. ;P

[bushindo]

That's the other part of the puzzle . Plasmid was very close, the answer to that part just needs to be refined to fit the specified rules laid down by his oh-so-munificent majesty. ;P

Well, here's are some strategies

Suppose that whenever a participant raises his hand, the other 4 participant would be aware of this fact. Here's a general strategy that would allow all 5 participants to win.

I) After the first gong sounding, participant 1, who is the closest one to the king, is to raise his hand if he sees 2 black hats. Everyone should be able to figure their hat colors if this happens.

II) If the second gong sounds and participant 1 didn't raise his hand, then there are four classes of hat patterns, which are listed in the drawing below. (Note that the classes of patterns are listed as A, B, C, and D, each of which may include mirror images of one another along the vertical axis. For instance, in class A, the hat colors of participants 2a and 2b can be reversed without consequence on the following strategy).

III) After the second gong sounding, participants 2a and 2b are each supposed to raise his hand if he or she sees 2 hats of the same colors (2 whites or 2 blacks). Let's say that 2a raises his hand after the second gong sounds, then the hat patterns fall into class A or B. Participant 2b would then be able to figure out which pattern it is, and he needs to convey this information to participants 1, 3a, and 3b.

III-a) If the pattern is A, then participant 2b should raise his hand after participant 2a, but before the third gong sounding.

III-b) If the pattern is B, then participant 2b should raise his hand after the third gong sounding. Everyone else should be able to figure out his hat color. Participants 3a and 3b may need to observe each other's hat before being able to calculate their own color.

IV) If the third gong sounds and no one has raised his hand yet, then the hat pattern is either C or D. At this point, participants 2a and 2b would know which is the true pattern and they can convey it to the rest with the following:

IV-a) If the pattern is C, then participant 2a should raise his hand after the third gong.

IV-b) If the pattern is D, then participant 2b should raise his hand after the third gong. Everyone else should be able to figure out his color.

Minor details about the fish lines

In the general strategy, we assumed that whenever a participant raises his hand, the other 4 participant would be aware of this fact. The information in the OP doesn't specify whether this assumption is true or not.

1) If the assumption is true, things are all well and good.

2) If the assumption is not true, then simply use the fishlines to attach each participant to the other four. For instance, we could attach four lines from participant 1 to the thumbs of each of the other four, then attach four lines from participant 2a to the index finger of each of the other 4, and so on. Whenever a participant raises his hand, simply hold on to the fishlines as he or she raises the hand, and the other 4 would know who raised the hand.

Edited May 13, 2012 by bushindo

[Yoruichi-san]

Well, here's are some strategies

Suppose that whenever a participant raises his hand, the other 4 participant would be aware of this fact. Here's a general strategy that would allow all 5 participants to win.

I) After the first gong sounding, participant 1, who is the closest one to the king, is to raise his hand if he sees 2 black hats. Everyone should be able to figure their hat colors if this happens.

II) If the second gong sounds and participant 1 didn't raise his hand, then there are four classes of hat patterns, which are listed in the drawing below. (Note that the classes of patterns are listed as A, B, C, and D, each of which may include mirror images of one another along the vertical axis. For instance, in class A, the hat colors of participants 2a and 2b can be reversed without consequence on the following strategy).

III) After the second gong sounding, participants 2a and 2b are each supposed to raise his hand if he or she sees 2 hats of the same colors (2 whites or 2 blacks). Let's say that 2a raises his hand after the second gong sounds, then the hat patterns fall into class A or B. Participant 2b would then be able to figure out which pattern it is, and he needs to convey this information to participants 1, 3a, and 3b.

III-a) If the pattern is A, then participant 2b should raise his hand after participant 2a, but before the third gong sounding.

III-b) If the pattern is B, then participant 2b should raise his hand after the third gong sounding. Everyone else should be able to figure out his hat color. Participants 3a and 3b may need to observe each other's hat before being able to calculate their own color.

IV) If the third gong sounds and no one has raised his hand yet, then the hat pattern is either C or D. At this point, participants 2a and 2b would know which is the true pattern and they can convey it to the rest with the following:

IV-a) If the pattern is C, then participant 2a should raise his hand after the third gong.

IV-b) If the pattern is D, then participant 2b should raise his hand after the third gong. Everyone else should be able to figure out his color.

Minor details about the fish lines

In the general strategy, we assumed that whenever a participant raises his hand, the other 4 participant would be aware of this fact. The information in the OP doesn't specify whether this assumption is true or not.

1) If the assumption is true, things are all well and good.

2) If the assumption is not true, then simply use the fishlines to attach each participant to the other four. For instance, we could attach four lines from participant 1 to the thumbs of each of the other four, then attach four lines from participant 2a to the index finger of each of the other 4, and so on. Whenever a participant raises his hand, simply hold on to the fishlines as he or she raises the hand, and the other 4 would know who raised the hand.

An excellent strategy! Although, in the story, I was trying to convey (and I guess didn't) that they didn't have a lot of time to come up with a strategy of say "you raise your hand when to indicate a particular arrangement". But major points to Bushindo for his solution.

Also, I was trying to convey (by the rules) that they couldn't speak or look at each other until their respective gong rang, so there needed to be another element to alert them to the others raising their hands, hence the fishing line, which Bushindo correctly arranged. Looking at the final shape...well, it's befitting the most benevolent king, don't you think?

Anyways, let me ask this question then. If there was no time to devise and agree on a strategy, hence allowing the fishermen only to raise their hand when they knew their own color of hat, what is the algorithm for the first fisherman?

[bushindo]

An excellent strategy! Although, in the story, I was trying to convey (and I guess didn't) that they didn't have a lot of time to come up with a strategy of say "you raise your hand when to indicate a particular arrangement". But major points to Bushindo for his solution.

Also, I was trying to convey (by the rules) that they couldn't speak or look at each other until their respective gong rang, so there needed to be another element to alert them to the others raising their hands, hence the fishing line, which Bushindo correctly arranged. Looking at the final shape...well, it's befitting the most benevolent king, don't you think?

Anyways, let me ask this question then. If there was no time to devise and agree on a strategy, hence allowing the fishermen only to raise their hand when they knew their own color of hat, what is the algorithm for the first fisherman?

This is puzzling, since a previously-agreed-upon strategy is the hallmark of these everyone-must-be-correct-to-win problems. I would like some clarification. Do you mean to say "If there was no time to devise and agree on a strategy, hence allowing the fishermen only to raise their hand when they knew their own color of hat, what is the algorithm for the first fisherman such that the 5 participants are guaranteed to win?" Or perhaps you mean to ask for an algorithm for the first fisherman such that the chance of fishermen winning is as high as possible?

Edited May 13, 2012 by bushindo

[Yoruichi-san]

This is puzzling, since a previously-agreed-upon strategy is the hallmark of these everyone-must-be-correct-to-win problems. I would like some clarification. Do you mean to say "If there was no time to devise and agree on a strategy, hence allowing the fishermen only to raise their hand when they knew their own color of hat, what is the algorithm for the first fisherman such that the 5 participants are guaranteed to win?" Or perhaps you mean to ask for an algorithm for the first fisherman such that the chance of fishermen winning is as high as possible?

Honestly, I haven't looked at enough of this kind of problem to know what the hallmarks are, but in this situation, the fishermen should be able to solve what color hat they are wearing through just logic, and not strategy, given that the fishermen figure out a way to alert all the other players when they've figured out their hat (which you did). I could ask for the algorithms for all the fisherman, but I think asking for the first fisherman's algorithm/set of rules will suffice to make people consider about all the possibilities. I put the gongs in to make it easier to mark the time and define the algorithm.

[bushindo]

Honestly, I haven't looked at enough of this kind of problem to know what the hallmarks are, but in this situation, the fishermen should be able to solve what color hat they are wearing through just logic, and not strategy, given that the fishermen figure out a way to alert all the other players when they've figured out their hat (which you did). I could ask for the algorithms for all the fisherman, but I think asking for the first fisherman's algorithm/set of rules will suffice to make people consider about all the possibilities. I put the gongs in to make it easier to mark the time and define the algorithm.

My impression of the claim you intend the BD to prove is the following:

Claim: Given that the fishermen figure out a way to alert all the other players when they've figured out their hat, then the fishermen should be able to solve what color hat they are wearing through just logic; that is, they do not need to confer among themselves for a common strategy.

In other words, let's say that we remove the fishlines from the problem, and just assume that there is a royal announcer. Every time participant X raises his hand, the royal announcer would then intone within all participant's hearing "Participant X is ready to guess his hat color". Are you saying that, without absolutely no talking among themselves before the game start, the 5 participants can logically come to a solution that is guaranteed to win?

Edited May 14, 2012 by bushindo

[Yoruichi-san]

My impression of the claim you intend the BD to prove is the following:

Claim: Given that the fishermen figure out a way to alert all the other players when they've figured out their hat, then the fishermen should be able to solve what color hat they are wearing through just logic; that is, they do not need to confer among themselves for a common strategy.

In other words, let's say that we remove the fishlines from the problem, and just assume that there is a royal announcer. Every time participant X raises his hand, the royal announcer would then intone within all participant's hearing "Participant X is ready to guess his hat color". Are you saying that, without absolutely no talking among themselves before the game start, the 5 participants can logically come to a solution that is guaranteed to win?

Yep , assuming that each fisherman will raise their hand pretty much as soon as they know their own hat color.

[bushindo]

Yep , assuming that each fisherman will raise their hand pretty much as soon as they know their own hat color.

Ah, I see what you are getting at then. Your claim is absolutely right. This is a superbly designed puzzle, by the way.

Assuming that all fisherman are perfect logicians, here's the strategy for the fisherman closest to the the king,

1) If he sees two BLACK hats after the first gong, his hat is WHITE.

2) Let's say that 1) did not happen. If someone else raises his hand after the second gong, then the fisherman closest to the king's hat is

2a) WHITE if his neighbors have alternating hat colors

2b) BLACK if his neighbors have both WHITE colors

3) If the third gong sounds without any hand raised so far, then the first fisherman's hat is

3a) BLACK if his neighbors have alternating hat colors,

3b) WHITE if his neighbors have both WHITE colors

Edited May 14, 2012 by bushindo

[Yoruichi-san]

Ah, I see what you are getting at then. Your claim is absolutely right. This is a superbly designed puzzle, by the way.

Assuming that all fisherman are perfect logicians, here's the strategy for the fisherman closest to the the king,

1) If he sees two BLACK hats after the first gong, his hat is WHITE.

2) Let's say that 1) did not happen. If someone else raises his hand after the second gong, then the fisherman closest to the king's hat is

2a) WHITE if his neighbors have alternating hat colors

2b) BLACK if his neighbors have both WHITE colors

3) If the third gong sounds without any hand raised so far, then the first fisherman's hat is

3a) BLACK if his neighbors have alternating hat colors,

3b) WHITE if his neighbors have both WHITE colors

Nice job . Thanks for the compliment, although I think it took me longer to design it than for you to solve it...in two ways...*whistling*

[bushindo]

Nice job . Thanks for the compliment, although I think it took me longer to design it than for you to solve it...in two ways...*whistling*

The first solution was really just a clumsy variant of the canonical solution. After that first solution I thought this is a pretty neat puzzle, but it turns out the puzzle is even more elegant than I thought. Thanks a lot for sharing this gem.