bushindo

I forgot to say that at the beginning of step 4, the Easter Bunny then removes everybody's blindfold. That shouldn't detract from the puzzle, though, as that fact is implied in later details. The Easter Bunny does draw random hat color for everybody based on independent coin flips. Please assume that the reindeers are sentient and can write. No cheating using ipads, reindeer eyes, Rudolph's big red nose, etc. At least that's what I think. It is possible to find a strategy with positive expected winning. The strategy does not require much charting or computation. In fact, you just may go 'ah-ha' once you find the solution.

In this economic downturn, Santa is having a bit of financial trouble preparing for his yearly trip. There are a couple of outstanding lawsuits against Santa Inc. for broken roofs and busted chimneys; the North Pole Toy-Assembling Elves Union (NPTEU) is demanding a raise; prices for toy raw materials are skyrocketing; and Mrs. Claus just blew the family budget on a bunch of iPads for the reindeers. Knowing this, the Easter Bunny is offering Santa a chance to make money through a game. The game is as follows: 1) The Easter Bunny is the game host. Santa and his 9 reindeers (Dasher, Dancer, Prancer, Vixen, Comet, Cupid, Donner, Blitzen, Rudolph) will be the participants. Santa and his reindeers has to pay a total of 1 gold coin to play the game. 2) The Easter Bunny will blindfold all participants, and then place either a RED or GREEN Santa hat on each participant's head. 3) The Bunny will then randomly arrange all participants in a circle in such a way that each participant can only see the 7 immediate neighbors in the clockwise direction. 4) The Bunny will then present each player with a list of 10 names, one for each participant. Each player is then requested to guess the hat color of ALL participants and write them down on this list. (Note: Each player can already see 7 other participants, so each player effectively only need to guess his own hat and the hats of 2 immediate neighbors in the counterclockwise direction). Each player must write down either RED or GREEN next to each name on the list, and all players must write at the same time. 5) If ALL of the 10 lists are correct, then Santa and company will win 32 gold coins. If 1 or more list is incorrect, then Santa and company wins nothing. A correct list means that all ten names has the correct hat color written next to them. Please assume that Santa and company do not cheat (e.g. trying to exchange information through words, utterances, signs, facial expressions, delays in writing their answer, etc.). The reindeers don't want to get on the naughty list, and Santa of course would never be naughty. Santa and the reindeers can discuss a strategy before the game, and the Easter Bunny said that he is willing to play this game as many times as Santa wants. Please help fund Santa's yearly trip by determining a strategy with positive expected winnings. Good children around the world (and the elves in the NPTEU) eagerly await your input.

Just read Jobe17's solution. Wish I thought of that. Thanks for the superbly constructed puzzle. I really enjoy it. It was devilishly challenging/fun to work through.

Well, if that's the case, then here's a strategy,

More clarification: Suppose that an infected member is in a room with a non-infected unconscious member, presumably he would need an excuse to touch the unconscious person. What would the infected member say about the result of his scan? What happens when you connect two conscious crewmember together, one of which is infected, and the other being non-infected?

Some clarification please: 1) The OP indicates that video and audio communication are available between you and all areas. That seems to imply that you can simply pose questions to the crew members and have them respond. Does that mean that the non-infected crew members will act as truth tellers? Would the infected members then act as random answerers? 2) Suppose that a crew member is infected, and then is cured by a serum. Would he know that he was infected last round?

Nice solution. Clear and insightful as always.

Welcome to the den. This solution assumes that we know exactly what X is, so that we can distinguish between X, 2X, 3X, and so on. That is not true. We know that the odd coins are heavier than the normal coins, but we don't know how much heavier. Also, please put your solution in spoiler tags next time. Also, apparently I mistyped the number of coin piles in this puzzle. There should be 9 piles (not 10 piles) of coins total, each pile with 10 coins. 7 piles are normal coins, and 2 piles are fake coins. The remaining parameters are the same. Sorry about that. That correction should make the puzzle a lot easier now.

Some comment

Suppose that you have 10 piles of coins. Each pile has exactly 10 coins. Eight piles consist of normal coins, which weight 100g each, and the remaining two piles consist of fake coins, each of which is heavier than 100 g. All the fake coins have identical (and unknown) weight. You are given a digital scale, which can take any number of coins and return the total weight. Please identify the 2 piles with fake coins in only 2 weighings. EDIT: I apologize for the double post. I have no idea why this puzzle shows up twice as two topics. If any mod sees this, please delete this duplicate topic.

This puzzle has been partially solved by araver. The strategy still isn't as optimal as it could be, so for the sake of completeness I'll clarify the remaining challenge. Given the problem in the OP, find a strategy that has a winning rate that is 75% or higher.

This is excellent. The strategy above is more optimal than mine, which can only win 1/16 times (256 times that of random guessing). Good work.

Yes, I did not ask for the optimal strategy on purpose. You're very sharp. This puzzle is more like an ah-ha type of puzzle. It does not, and should not, require excessive charting or computing. EDIT: I apologize for the double post. Something seems to be wrong with my browser.

Yes, I did not ask for the optimal strategy on purpose. You're very sharp. This puzzle is more like an ah-ha type of puzzle. It does not, and should not, require excessive charting or computing.

The next Greedy strategy tries to win the middle cases (w=3,w=4) and group everyone errors in the losing cases: Depending on z choose: z=0 - Red* z=1 - Blue z=2 - Red z=3 - abstain z=4 - Blue z=5 - Red z=6 - Blue* *-same chances if instead of color, abstain is chosen. This greedy strategy has a 2*(7+35)=84 out of 128 winning cases = 65.625% It wins for B={1,3,4,6} instances. Its not so good compared to 112 out of 128=87.5% for the perfect-Hamming strategy (if we knew the distribution of hats as well), but not far from that either. Depending on z choose: z=0 - Blue z=1 - Red z=2 - abstain z=3 - Blue z=4 - abstain z=5 - Blue z=6 - Red This reverseGreedy strategy has 2*(1+21)+35=79 out of 128 winning cases. Its not as good as the Greedy strategy, but it is good if you think you're in a non-B instance {0,2,5,7}. As a side-effect, it also wins for a particular B-instance (w=3) i.e. when you think you're in a non-B instance but you're actually in a w=3 instance. Step 0. Establish B={1,3,4,6} and assume teams form a circle (i.e. n=3 Hamming instance). Assume A={000,111}. Appoint a leader team as a starting point and a rotation direction: e.g. British, French, Italian. Step 1. Compute the two bits of information you see from other teams based on set B. So if you see a number that is in B mark it as a bit 1, else mark it as bit 0. Step 2. Assuming the two possibilities (that you are either a B-instance or a non-B-instance) as bits for your team you arrive at two unique 3-bit strings a (if you are a nonB-instance) and b (if you are a B-instance). The fact that you established in step 0 a starting point and a rotation direction makes a and b unique. Step 3. If neither a nor b belong to A - ABSTAIN, else go to step 4. Step 4. Exactly one of a or b belongs to A: If a is in A, then choose b (think that you are a B-instance), so play the individual Greedy strategy. If b is in A, then choose a (think that you are a non-B instance), so play individual reverseGreedy strategy. Note that this global strategy is independent of what you are told about your team, and only after arriving in step 4 and choosing an individual strategy you actually take the information about your team into account. Chances of winning depend on the unknown global string w1w2w3 (British, French, Italian) where wi=1 iff the number of hats in team i is in B: -000 - Everybody sees non-B instances, chooses b in step 4, tries to play Greedy and fails. Game is LOST. -001, 010, 100 - One team (in a B instance) sees a=000 in A and plays the Greedy strategy which wins. Other two teams see 1-bit and 2-bit numbers not in A and abstain. Game is WON. -110, 101, 011 One team (in a non-B instance) sees b=111 in A and plays reverseGreedy which wins. Other teams see 1-bit and 2-bit strings not in A and abstain. Game is WON. -111 Everybody sees b=111 in A, so they choose to play reverseGreedy (for the wrong reasons). They usually fail. But the lack of symmetry in reverseGreedy gives you a rather unique global win if everyone is in a particular B-instance (w=3). Only in this case, all three teams play a winning reverseGreedy. In all other cases, at least one team fails and Game is LOST. That lack of symmetry in reverseGreedy makes over-all winning chances harder to compute. First, the individual probability of having a B-instance(1,3,4,6) is easy to compute (and was already computed) as it is the same with winning chances of the Greedy strategy 84/128. Conversely, 44/128 cases for a non-B instance. Also, the chances of a w=3 instance are 35/128. So, global chances (denote t=44/128): Case 1) 000 means non-B instances for everyone = 44/128*44/128*44/128= t^3 Case 2) 001, 010, 100 means as single non-B instance = 3*44/128*44/128*84/128 = 3*t^2*(1-t) Case 3) 110, 101, 011 means as single B instance = 3*44/128*84/128*84/128 = 3*t*(1-t)^2 Case 4) 111 means B instances for everyone = 84/128*84/128*84/128= (1-t)^3. Of which a particular case with global (35/128)^3 probability should be counted as a win (reverseGreedy side-effect). So, global winning is 3*44/128*44/128*84/128 + 3*44/128*84/128*84/128+ (35/128)^3=(1486848+42875)/128^3=1529723/128^3. Roughly 72.94%. EDIT: Tried to make it more readable by two levels of spoilers. Combining 3 teams' strategies in a greedy manner, each team playing the same local (inside-team) strategy is a little tricky. We should use the fact that one knows the exact instance the other teams are in to obtain a global advantage. Therefore each player should look at the global picture, then either choose to abstain or play a team strategy (e.g. Greedy strategy as above). Assuming the third team's point of view for a moment i.e. imagine you see x and y and your own z<=w<=z+1. First, if you play the Greedy strategy as described above you know it's a win for a team iff number of hats is actually 1,3,4,6. So if you see that both x and y are not in the set B={1,3,4,6}, there's no point in abstaining since the others surely cannot get it right on their own. You might get lucky and be in a B-instance yourself, therefore winning the game. This would be Naive-Rule 1. If both x and y are in set B, then you might be spoiling everyone's chances by playing since your set might not be a wining set. This would count as a Naive-Rule 2. However, assuming a symmetrical global strategy, if all see B-instances, they would all abstain and perhaps lose a chance of winning. Then perhaps choosing/appointing a team to take action if all else fails would be better but this does not actually lead to a simple Naive-Rule 3. This starts to looks like a small version of the Hamming-problem. So, instead of choosing a strategy based on the Naive-rules above, you can actually choose a sort of Hamming n=3 strategy. However, besides the individual Greedy strategy above, you will need a mirror strategy for when you're a non-B instance. The following reverseGreedy strategy wins for non-B instances (i.e. when w=0,2,5,7) Returning to the Hamming-style global strategy: Bravo! The insight about the fact that the teams can be abstracted to a solved problem is spot on. Great work! Just some more comments

Suppose you and 11 friends are invited to play a game. The game is as follows: 1) All of the 12 participants are blinded folded and have either a red or blue hat placed on each of their heads. 2) The host then randomly arrange them in a circle in such a way that each participant can only see the 4 neighbors immediately to his/her left and the 4 neighbors immediately to his/her right. 3) The blindfolds are removed, and each participant can look at the hat of his 4*2 = 8 immediate neighbors. 4) Each person must then write down a guess for his/her hat. Each guess must either be 'red' or 'blue', and must be written at the same time. 5) The game host then looks at all the guesses. If they are ALL correct, the 12 participants win. If 1 or more guesses are incorrect, the participants lose. Please assume that the players do not cheat. Any attempt to exchange information through words, utterances, signs, facial expressions, delays in writing their answer, etc. will lead to an automatic loss. If everybody randomly guess their hat, then the chance of winning the game is 1/212 = 1/4096. Fortunately, there are better strategies than that. The players can discuss a strategy before playing the game. Determine a strategy that has a winning rate equal to or greater than 3/64 (that's 192 times better than random guessing).

The quote 'nominees always guess with the odds' is a bit ambiguous and makes it difficult to compute the winning rate of this strategy. Can you clarify? If everyone abstain, that would be considered a loss for the participants.

Thanks for the comments, araver. They are insightful as always. I have another challenging puzzle of this type that you might enjoy. I'll post that puzzle up after my current puzzle 7 Britishmen, 7 Frenchmen, and 7 Italians is solved. That shouldn't take long . Stay tuned.

. And sorry for the accidental reposts, something goofy when I logged in.... Sorry to hear about the ridiculous charts I'd like to note that each participant are put into a different room, so he can not hear that has transpired with his fellow participants.

7 Britishmen, 7 Frenchmen, and 7 Italians are invited to play a cooperative game. The game is as follows: 1) The game host puts each of the 21 participants into a separate room, blindfolds him, and places either a red or blue hat on his head. 2) The host then tells each participant the following: how many red hats are there total among each of the other two races, and how many red hats total among the participant's other 6 countrymen. For instance, if the host is talking to a Frenchmen, he would say to the Frenchmen, "Among the 7 Italians, there are a total of x red hats. Among the 7 Britishmen, there are a total of y red hats. Among the remaining 6 Frenchmen, there are z red hats." 3) Each of the 21 participants is then requested to guess their hat color. Each participant has a choice of 'Red', 'Blue', or 'Abstain'. 4) Everybody wins if at least 1 person correctly guesses his hat color, and no person incorrectly guesses his hat. The choice 'Abstain' is considered neutral, and is neither right or wrong. For example, if 1 person guesses the right color, and the other 20 abstain, then everybody wins. If 1 person guesses correctly, 19 abstain, and 1 guesses incorrectly, then everybody lose. The 21 Europeans above can discuss a strategy before playing the game. Help them determine a strategy that gives as high a winning rate as possible.

That would be here

I agree with araver that probabilistic methods can not beat deterministic methods. With some thoughts, it seems that 4/32 as the winning rate is the best we can do with this situation. It is possible to extend the deterministic ideas to more general cases, but for this case with 5 players, it is not necessary and the puzzle is not as challenging as I intended to be. Puzzle making is quite tough . Let me go back and reconstruct this puzzle.

Great! Now we can show that we have positive expected winnings. The bonus question about the optimal strategy is still open though. I'd like to hear about your N=4 strategy.

Suppose you and 4 friends are invited to play a game. The game is a variation of the hat puzzle with monetary incentive. The game is as follows: 1) You and your 4 friends each pay 10 dollars to participate in the game (50 dollars total). 2) All participant is then blind folded and have either a red or blue hat placed on each of their heads. 3) The host then randomly arrange them in a circle in such a way that each participant can only see the 1 neighbor immediately to his/her left and the 1 neighbor immediately to his/her right. 4) The blindfolds are removed, and each participant can look at the hat of his two immediate neighbors. 5) Each person must then write down a guess for his/her hat. All guesses must either be 'red' or 'blue', and must be written at the same time. 6) The game host then looks at all the guesses. If they are ALL correct, the 5 participants win a sum of 1000 dollars (20 times the money required to play the game). If one or more guesses are incorrect, the participants lose the 50 dollars. 7) Any attempt to cheat ( trying to exchange information through words, utterances, signs, facial expressions, delays in writing their answer, etc.) will lead to disqualification and forfeiture of the 50 dollars. Obviously, if you and your 4 friends each randomly guess, your change of winning is 1/25 = 1/32. Over about 30 such games, your group will shell out 1500 dollars while winning an expected 1000 dollars only. Fortunately, there are better strategies than random guessing. Determine a strategy that will give you and your friends positive expected winnings in the long run. (Bonus) What is the strategy with the highest expected winning?

It is possible to get above 90%