I got a few C++ questions, then a question on sorting algorithms then a brainteaser. The brainteaser went as follows: Three people are given hats. Each hat is either red or blue, chosen at random. Each person can see the other 2 hats, but not their own. They each must simultaneously either guess their own hat's color, or pass. No communication is allowed, although they can agree on a strategy ahead of time. What strategy will give them the best chances of at least one person guessing right, and nobody guessing wrong? 12 Answers If the 2 hats you see are the same, guess the opposite color, otherwise pass. If all 3 players use this rule, it works 75% of the time. It fails only when all the hats are the same color. You might want to start by listing all the possibilities. One person can assume there is an odd number of blue hats, another person can assume there is an even. By counting the number of blue hats amount the other two people each person arrives at a unique prediction for the color of there own hat. Sine the number of blue hats must be either even or odd, one of the guesses must be right. Yes, but the other one will be wrong. The question says that all the people who talk must give the correct color. The others can pass. However, if one answers wrong, they loose, so your strategy wouldn't work S. Show More Responses Here's a strategy: each member passes to the left if they see the same color (assume they are standing in a triangle) and to the right if they see different colors. If the first person sees two blue hats, and the second sees a red and a blue, the first will know their hat is red. If all hats are the same color, after one pass to the left, the second person will know their hat is the same as the third person. At most this will require two passes. I'm confused by the answers. We know the following: State: 1. There are three people 2. Each person is given one - and only one - hat 3. The colour will be either red or blue - completely random 4. No communication is allowed. 5. Each person can see the other two hats - but not their own. Behaviour: Each must simultaneously either guess their color or pass. Proposed Strategy: I see no rule against each individual passing his/her hat in a uniform direction - either left or right. This way, no communication has taken place and you now know the colour of your hat. It can obviously be considered as a form of communication after the start of the game. Just assume that every person can do one and only one action and that is pass or say a color. Also, that single action has to be done at the same time as the action or the two others, that is, there is only one pass. The strategy can be simple: Each person can see the color of the other two hats, so the strategy before the game could be, in the second vote the person should mention the color of the third persons hat. Assuming he tells the truth. So the first person can just tell any color, now only two people are left, the 2nd person will the tell the color of third persons hat, and the third person would repeat it. This will ensure every time that at least one answer is correct. Your answers are all horrible. Yeah, they really all are. The answer I posted is the correct one. It's actually on the internet if you google that problem, and it's really well explained. I mean the question is stated in an understandable manner. I really don't get all the ridiculous answers that are posted. two colors and allow the number of players to be of the form 2k − 1, where k 2, then we can devise a strategy for winning that—perhaps surprisingly—results in increasing probability of a win as the parameter k get large. Even better, this probability of winning approaches unity as k ! 1 ! In fact, we’ll show how to devise a strategy whose probability of a win is Prob(win) = 1 − 2 ^ (2k−k−1)/ 2 ^ (2k−1) . Note that if k = 2 (three players), this sets the probability of winning at 1 − 2 8 = 3 4 . The reason for this somewhat forced constraint on the number of people is that it allows a strategy based on the so-called Hamming codes, which we now briefly describe. We let F be the binary field, i.e., the field with two elements (0 and 1). All vector spaces shall be over the field F. Let k be a fixed positive integer ( 2) and let W be a fixed vector space of dimension k over F. Therefore we see that W contains exactly 2k − 1 nonzero vectors; we label these vectors w1,w2, . . . ,w2k−1. Now set n = 2k − 1 and let V = Fn: 1 2 V = {(a1, a2, . . . , an) | all ai 2 F}. The tautological map is the surjective linear transformation : V ! W defined by (a1, a2, . . . , an) = Xn i=1 aiwi 2 W. Since this is surjective, the kernel H (null space) has dimension dimH = dim V − dimW = n−k = 2k−1−k. We call H the (2k − 1, 2k − k − 1)-Hamming code; note that if k = 3, then H has dimension 4; when k = 4, then H has dimension 11. The only result that we need concerning the Hamming codes is the following. We define the “unit vectors” e1, e2, . . . , en 2 V by setting ei = (0, 0, . . . , 0, 1, 0, . . . , 0), where there is a “1” in the i-th position and 0s elsewhere. For convenience, set e0 = 0 2 V . Lemma. Let H be the (2k − 1, 2k − k − 1)- Hamming code. Then V = [n i=0 (ei + H) (disjoint union), where we set e0 = 0. Proof. Note first that if i 6= j, 1 i, j n, then (ei + H) \ (ej + H) = ;. For otherwise, it would happen that ei+ej 2 H; since (ei+ej) = wi + wj 6= 0 (set w0 = 0 2 W), this assertion follows. Therefore, S (ei + H) has cardinality (n + 1) · |H| = 2k(22k−k−1) = 22k−1 = |V |, and the result follows. Now assume that k 2 is fixed and that we have n = 2k − 1 members on the team. Label these people 1, 2, . . . , n. In preparation for the “hat trial,” we shall agree on the following strategy. First of all, let us represent the colors “black” and “white” by the elements 0 and 1 of F, respectively. Therefore, the random placing of hats on the team members’ heads is tantamount to the specification of a random vector v = (a1, a2, . . . , an) 2 V where person i has been given a hat with color ai. Note that it may or may not be the case that v 2 H (in fact it usually won’t be—this is an easy calculation). Therefore, if the distribution vector describing the placement of hats is given by the vector v = (a1, a2, . . . , an) 2 V, then person i can only infer that the distribution vector is of the form v = (a1, a2, . . . , ai−1, 0, ai+1, . . . , an) + biei = vi + biei, for some bi 2 F, and where the vector vi is defined above by what person i sees. In terms of the above notation, here’s the strategy: (a) If vi + biei 62 H for either choice of bi 2 F, then player i shall pass; (b) If vi + biei 2 H, then player i shall guess that his hat color is 1 + bi. We proceed to prove that the above is a welldefined strategy and is, in fact, a winning strategy for all hat distributions v such that v 62 H. First of all, the well-definedness issue stems from (b), above; namely we must show that we cannot have vi +biei 2 H for both choices of bi 2 F. Indeed, were this to happen then we would have ei = vi + vi + ei 2 H. Since (ei) = wi 6= 0 we have a contradiction. Therefore the strategy is well-defined. Next we show that if v 62 H, then the above strategy result in a win, i.e., at least one person will guess his hat color correctly and no one will guess incorrectly. Thus, assuming that v 62 H, we have, by the above lemma that v+ej 2 H for some unique index j, 1 j n. Therefore, we see immediately that person j will necessarily correctly guess his hat color. We contend that everyone else must pass. To see this, fix i 6= j 3 and write v = vi + aiei. For person i to do anything but pass, it must happen that vi+biei 2 H for some bi 2 F. Were this the case, then since v = vi+aiei, and since vi+aiei+ej = v+ej 2 H, we infer that (ai+bi)ei+ej = (vi+biei)+(vi+aiei+ej) 2 H. Since ((ai + bi)ei + ej) = (ai + bi)wi + wj 6= 0 this contradiction proves the result. We could be content to stop here as we’ve already shown that the above strategy results in a win with probability at least 1 − |H| |V | = 1 − 2−k. However, this is the exact probability as it’s clear that when v 2 H, then everyone guesses wrong. What about just telling the colour of hat of next person in cycle. Like A will tell of b , b of c and c of a. It guarantees atleast one will be correct Come on, the most important rule is they must response together! You miss that |