Print

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

[MiX]

The person would be guessing/signaling in the third round, not the second round. It's not that the person must signal one/two turns before the third round of the all-black/all-white person, it's that the person one/two spaces before the all-black/all-white person must signal in the third round.

If the all-(color) player is the first to play, and it's the third round, how are they supposed to know if they're black or white?

[bitwise]

The person would be guessing/signaling in the third round, not the second round. It's not that the person must signal one/two turns before the third round of the all-black/all-white person, it's that the person one/two spaces before the all-black/all-white person must signal in the third round.

If the all-(color) player is the first to play, and it's the third round, how are they supposed to know if they're black or white?

They don't, so they pass. They will know by the end of the third round and can guess in the fourth and final round.

[bitwise]

I have a further improvement for when there are 4 or more people. It takes 2 full rounds, plus 7 extra people in the worst case.

This solution is similar to hhelibebcnofnena's, but compresses some of the rounds.

1st round: Same as before, everyone passes unless they can deduce that their hand and the face down cards are all the same color.

2nd "round": Same idea that everyone passes unless they see someone with two whites and someone with two blacks. However, only the first 3 people need to do this--after 3 people, it becomes common knowledge that there is at most one person with two cards of the same color.

3rd "round": Similar idea to my combined round earlier--people will signal if there is someone with two whites, or two blacks, or neither. For each of the first 4 people in this round, if they can deduce that they have one white and one black, they guess if a) they are 1st or 3rd in the round, and they see someone with two white cards; b) they are 2nd or 4th in the round, and they see someone with two black cards. (Whenever any of these four people guess, the round ends early, as everyone can now deduce their cards.) If all 4 pass, it means that no one has cards of the same color--otherwise, it's guaranteed someone will signal.

4th round: Everyone left guesses their cards.

This takes n + 3 + 4 + n for all the guesses in the worst case, or 2n+7. It doesn't feel like you can do much better, if at all. (Exception: for n = 3, the old 4-round solution is better).

[hhelibebcnofnena]

I have a further improvement for when there are 4 or more people. It takes 2 full rounds, plus 7 extra people in the worst case.

This solution is similar to hhelibebcnofnena's, but compresses some of the rounds.

1st round: Same as before, everyone passes unless they can deduce that their hand and the face down cards are all the same color.

2nd "round": Same idea that everyone passes unless they see someone with two whites and someone with two blacks. However, only the first 3 people need to do this--after 3 people, it becomes common knowledge that there is at most one person with two cards of the same color.

3rd "round": Similar idea to my combined round earlier--people will signal if there is someone with two whites, or two blacks, or neither. For each of the first 4 people in this round, if they can deduce that they have one white and one black, they guess if a) they are 1st or 3rd in the round, and they see someone with two white cards; b) they are 2nd or 4th in the round, and they see someone with two black cards. (Whenever any of these four people guess, the round ends early, as everyone can now deduce their cards.) If all 4 pass, it means that no one has cards of the same color--otherwise, it's guaranteed someone will signal.

4th round: Everyone left guesses their cards.

This takes n + 3 + 4 + n for all the guesses in the worst case, or 2n+7. It doesn't feel like you can do much better, if at all. (Exception: for n = 3, the old 4-round solution is better).

Nice observations about some of the rounds being compressible. Also, this improvement can work for 3 players, as well, if we extend the 3rd "round" to actually be the first three players + the first person again as a "4th player".

[bitwise]

Also, this improvement can work for 3 players, as well, if we extend the 3rd "round" to actually be the first three players + the first person again as a "4th player".

Oh, nice observation. For 3 people, it's still better just to use the previous protocol that takes the whole round though. Although, that does make me wonder if there's perhaps a way to shave off a bit from this compressed round somehow.

[pacovf]

The last person in the 1st round can also be the first person in the 2nd round, shaving one chance for guessing off the total. Similarly for the passage between the 2nd round and the 3rd round. Not sure about the passage between 3rd and 4th, that one is a bit confusing.

[hhelibebcnofnena]

...Similarly for the passage between the 2nd round and the 3rd round...

I don't believe this is true.
Consider this "2nd round": The players have black/black, white/white, and white/black. The players with black/black and white/white are the only such players. The 2nd round goes: black/black: pass. white/white: pass. white/black: guess. When it gets back around to the player with black/black, because the second and third rounds overlap, they have no way to know whether the player with white/black guessed because they saw double white and double black, or just because they saw double white. Thus, they could have double black, and the hidden cards are white/black, or vice versa.

[MiX]

...Similarly for the passage between the 2nd round and the 3rd round...

I don't believe this is true.
Consider this "2nd round": The players have black/black, white/white, and white/black. The players with black/black and white/white are the only such players. The 2nd round goes: black/black: pass. white/white: pass. white/black: guess. When it gets back around to the player with black/black, because the second and third rounds overlap, they have no way to know whether the player with white/black guessed because they saw double white and double black, or just because they saw double white. Thus, they could have double black, and the hidden cards are white/black, or vice versa.

The black/black player knows they're not white/white because they've seen 3 white cards, so there's only 1 left, and they know they're not white/black because white/black left either to them being white/white or black/black, so they would know they're black/black and could guess. Same for white/white afterwards.

[ghostofmars]

I think you can do even better. Splitting it in two cases

Trivial case: There is a least one of each of WW and BB. After the first round we know exactly the hidden cards and are done after the second round.

Special case: There is either exactly one player with WW or BB or all players have WB. Naturally the corresponding hidden cards are BB, WW, and WB, respectively. After the first round, these 3 cases are not distinguishable by the player who has the special configuration (or by any player in the case of all players WB). However, after one more action is taken, the three configurations separate and everybody knows their cards. Hence the worst case scenario is 2n + 1.

[hhelibebcnofnena]

...Similarly for the passage between the 2nd round and the 3rd round...

I don't believe this is true.
Consider this "2nd round": The players have black/black, white/white, and white/black. The players with black/black and white/white are the only such players. The 2nd round goes: black/black: pass. white/white: pass. white/black: guess. When it gets back around to the player with black/black, because the second and third rounds overlap, they have no way to know whether the player with white/black guessed because they saw double white and double black, or just because they saw double white. Thus, they could have double black, and the hidden cards are white/black, or vice versa.

...they know they're not white/black because white/black left either to them being white/white or black/black...

That's the point, though -- this isn't true. The white/black player guessed either because of them having black/black or because the other player had white/white. They can confirm that the second possibility is true, but cannot confirm whether or not the first possibility is also true. Therefore they don't know whether they have white/black or black/black.

Trivial case: There is a least one of each of WW and BB. After the first round we know exactly the hidden cards and are done after the second round.

I'm not sure I understand; that's what the point of the second round is. The players with WW and BB can't see that both WW and BB are on the board, assuming there's only one of each, so the second round has to communicate that to them.

Special case: There is either exactly one player with WW or BB or all players have WB. Naturally the corresponding hidden cards are BB, WW, and WB, respectively. After the first round, these 3 cases are not distinguishable by the player who has the special configuration (or by any player in the case of all players WB). However, after one more action is taken, the three configurations separate and everybody knows their cards. Hence the worst case scenario is 2n + 1.

I don't understand this either. Why do they separate after only 1 more action? It seems like you need four actions to completely separate them out.

Also, this improvement can work for 3 players, as well, if we extend the 3rd "round" to actually be the first three players + the first person again as a "4th player".

Oh, nice observation. For 3 people, it's still better just to use the previous protocol that takes the whole round though. Although, that does make me wonder if there's perhaps a way to shave off a bit from this compressed round somehow.

The previous protocol took 2 rounds through, not one. It's still more efficient to use the improvement.

[silverspawn]

I think you're both right. 

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   

                                                                                       
                                                                                                                                                     
                                                                              Moat                                                   

                                                                                                                             

                                                                                                                       

[bitwise]

Also, this improvement can work for 3 players, as well, if we extend the 3rd "round" to actually be the first three players + the first person again as a "4th player".

Oh, nice observation. For 3 people, it's still better just to use the previous protocol that takes the whole round though. Although, that does make me wonder if there's perhaps a way to shave off a bit from this compressed round somehow.

The previous protocol took 2 rounds through, not one. It's still more efficient to use the improvement.

There was an intermediate improvement where you could have either the person two before or one before the same-colored-cards person signal, in a single round. It took 4n steps, or 12 steps for 3 players whereas this takes 13. It's not really important, except that it's interesting that signalling in the different way can be more efficient in this case, making me wonder if there was something better than the 4 step solution.

[hhelibebcnofnena]

Also, this improvement can work for 3 players, as well, if we extend the 3rd "round" to actually be the first three players + the first person again as a "4th player".

Oh, nice observation. For 3 people, it's still better just to use the previous protocol that takes the whole round though. Although, that does make me wonder if there's perhaps a way to shave off a bit from this compressed round somehow.

The previous protocol took 2 rounds through, not one. It's still more efficient to use the improvement.

There was an intermediate improvement where you could have either the person two before or one before the same-colored-cards person signal, in a single round. It took 4n steps, or 12 steps for 3 players whereas this takes 13. It's not really important, except that it's interesting that signalling in the different way can be more efficient in this case, making me wonder if there was something better than the 4 step solution.

Ah. I forgot about that intermediate improvement.

[ghostofmars]

Trivial case: There is a least one of each of WW and BB. After the first round we know exactly the hidden cards and are done after the second round.

I'm not sure I understand; that's what the point of the second round is. The players with WW and BB can't see that both WW and BB are on the board, assuming there's only one of each, so the second round has to communicate that to them.

You are right, I forgot about one more special case. If there is exactly one of WW and BB and one of them occupies the last spot, then the simple solution will not work. If there is at least one player left in round 1 with WB, it works like this immediately after both the WW and the BB player have passed, it becomes common knowledge among all WB that the hidden cards are WB, so they can deduce their own cards. Hence, if the WW and BB player see any WB player not passing before the end of the first round the hidden cards are WB.

I'll check how this additional instance modifies the special case treatment.

[gamesou]

By the way that game is kind of fun to play with 3 players WITHOUT a priori discussion on the strategy, and with the weaker winning condition where it's enough that somebody guesses correctly. (We used kings and queens from a regular deck and should guess 'gay' or 'straight'.)

[ghostofmars]

I corrected my previous result to a worst case of 2n + 3 turns for n > 3. n = 3 requires 10 steps to solve.

The trivial case was outlined above, let's focus on the special case now. In most cases, the 1st player will actually know that they are WB after the first round, because if they weren't it would be a trivial case. In these cases, the first player states their identity and one more passing is required to communicate the player with the doublet their identity. This leads to a worst case scenario of 2n + 2 if the player with the doublet is in position 2 and must pass in the second round.

Now to the remaining 7 cases, which are always the same for all n > 3. They are all players having WB, except for player 1 and n which may also have doublets. This results in 7 cases because they may not have the same doublet. In all these 7 cases, the first player must pass in the second round followed by (n - 2) players who all hold WB and using selective passing to communicate the doublets to player 1 and n. Because in the worst case three options are available for player 1, this requires up to 2 players passing. Combined with the passing of the first player in the second round, we get 2n + 3 turns.

[bitwise]

Looks good to me, though I thought I had found a mistake in it about five times before being eventually convinced. I'm a little confused what the protocol is for 3 players though.

I have some more "hat" type problems, not sure if they've been shown on this thread before.

1. 100 players are each given a red or black hat independently and uniformly at random. Each player can see everyone else's hat but not their own. Each player must simultaneously guess the color of their own hat. The players all win if all of their guesses are correct, but otherwise, they all lose. The players may confer on a strategy before the hats are given, but may not communicate once the hats are distributed. What is the maximum probability of victory that they can achieve?

2. Similar to the previous problem, but there are 127 players. Furthermore, each player simultaneously guesses their hat color OR abstains. The players win if all guesses are correct and there was at least one guess, and otherwise, they all lose. What is the maximum probability of victory that they can achieve?

[Tables]

2. Similar to the previous problem, but there are 127 players. Furthermore, each player simultaneously guesses their hat color OR abstains. The players win if all guesses are correct and there was at least one guess, and otherwise, they all lose. What is the maximum probability of victory that they can achieve?

This one... I think this is the answer.

50%.

With the distribution being completely random, there's no way any single person can have more than a 50% chance to guess their own hat colour. No amount of planning a way a person might decide to guess or not guess will give them a better than 50% chance when they actually make their guess. Therefore, one person is designated to guess at random, while everyone else abstains. The person making a guess then has a 50% chance to guess correctly, making everyone win.

[heron]

2. Similar to the previous problem, but there are 127 players. Furthermore, each player simultaneously guesses their hat color OR abstains. The players win if all guesses are correct and there was at least one guess, and otherwise, they all lose. What is the maximum probability of victory that they can achieve?

This one... I think this is the answer.

50%.

With the distribution being completely random, there's no way any single person can have more than a 50% chance to guess their own hat colour. No amount of planning a way a person might decide to guess or not guess will give them a better than 50% chance when they actually make their guess. Therefore, one person is designated to guess at random, while everyone else abstains. The person making a guess then has a 50% chance to guess correctly, making everyone win.

This is not correct. Consider the game with 3 people and the strategy of guessing the opposite color if both other players have the same color hat.

It is true that 50% of guesses made are incorrect, but you can load it so that many wrong guesses are made at once, and when a correct guess is made it is the only guess.

[hhelibebcnofnena]

Sorry, I'm still focused on the previous riddle -- maybe I'll think about the newer hat riddles at some point.

You are right, I forgot about one more special case. If there is exactly one of WW and BB and one of them occupies the last spot, then the simple solution will not work. If there is at least one player left in round 1 with WB, it works like this immediately after both the WW and the BB player have passed, it becomes common knowledge among all WB that the hidden cards are WB, so they can deduce their own cards. Hence, if the WW and BB player see any WB player not passing before the end of the first round the hidden cards are WB.

Still a case you haven't considered (if I am understanding you correctly, which I may not be): the first and last player are both doubles. Although your improvement doesn't bring down the worst case at all (again, if I am not understanding you, please feel free to correct me), it does bring down the average length, which is interesting. I might want to calculate that at some point.

I corrected my previous result to a worst case of 2n + 3 turns for n > 3. n = 3 requires 10 steps to solve.

The trivial case was outlined above, let's focus on the special case now. In most cases, the 1st player will actually know that they are WB after the first round, because if they weren't it would be a trivial case. In these cases, the first player states their identity and one more passing is required to communicate the player with the doublet their identity. This leads to a worst case scenario of 2n + 2 if the player with the doublet is in position 2 and must pass in the second round.

Now to the remaining 7 cases, which are always the same for all n > 3. They are all players having WB, except for player 1 and n which may also have doublets. This results in 7 cases because they may not have the same doublet. In all these 7 cases, the first player must pass in the second round followed by (n - 2) players who all hold WB and using selective passing to communicate the doublets to player 1 and n. Because in the worst case three options are available for player 1, this requires up to 2 players passing. Combined with the passing of the first player in the second round, we get 2n + 3 turns.

I apologize, but I really don't understand what you are saying here. While reading the first paragraph, an improvement passed through my brain, but I have no idea if it is what you are trying to say. And I didn't understand what you meant by "7 remaining cases." Could you outline them?

The improvement I think I was reading: After the possibility of two "doublets" has been ruled out, the current protocol requires 4 guesses to communicate to anyone with a potential "doublet" a) whether they have one and b) whether it is WW or BB. Instead, the first player should guess if they see a WW, and the second player should guess if they see a BB, skipping over any player with a "doublet." This reduces the protocol to three players.

[hhelibebcnofnena]

...immediately after both the WW and the BB player have passed, it becomes common knowledge among all WB that the hidden cards are WB, so they can deduce their own cards. Hence, if the WW and BB player see any WB player not passing before the end of the first round the hidden cards are WB.

Similarly, slight improvement for 5+ players:
After two WWs and two BBs have passed, anyone can deduce their own cards, so we can cut the first round short there as well. Doesn't improve the worst case, but brings down the average length for 5+ players.

[ghostofmars]

Sorry phone post so no spoiler tags.

The 7 cases, in which the first player does not know their own cards after one round, are
WW (n-2)*WB BB [hidden: WB]
WB (n-2)*WB BB [WW]

BB (n-2)*WB WW [WB]
WB (n-2)*WB WW [BB]

WW (n-1)*WB [BB]
WB (n-1)*WB [WB]
BB (n-1)*WB [WW]
I grouped the cases from the perspective of the first player. Because there is more than one case, the first player passes, then the second one passes or not to hint between the different options. In the last group there are three options so the third player needs to do the final communication.

[ghostofmars]

For the new hat problem, I believe the correct answer for the first part is 50%, isn't it?

[hhelibebcnofnena]

Sorry phone post so no spoiler tags.

The 7 cases, in which the first player does not know their own cards after one round, are
WW (n-2)*WB BB [hidden: WB]
WB (n-2)*WB BB [WW]

BB (n-2)*WB WW [WB]
WB (n-2)*WB WW [BB]

WW (n-1)*WB [BB]
WB (n-1)*WB [WB]
BB (n-1)*WB [WW]
I grouped the cases from the perspective of the first player. Because there is more than one case, the first player passes, then the second one passes or not to hint between the different options. In the last group there are three options so the third player needs to do the final communication.

Ah, I see. What about the last player? How do they know? We need three people to split the cases up for both first and last player.
If we do something like this:
1st player: guess if last player has a doublet, pass if last player has WB
2nd player: guess if last player has WW or if last has WB and first has WW, otherwise pass
3rd player: guess if first player has WB, otherwise pass
then the last player can be the last of the three.

Not sure how this works in a three player game, though. Or if there's only one doublet and it's not the first or last player, how that gets communicated to them.

[bitwise]

Thinking about it, I'm actually a bit confused about resolving the "trivial case".

Consider the layout is BB, WW, WW, BB, and everyone else BW. After the first two players pass, and the third player guesses, how can the second player deduce the difference between them being BW and the middle hidden cards WW or vice-versa?

For the new hat problem, I believe the correct answer for the first part is 50%, isn't it?

Yes, that's correct.