Guess another's present

Question

100 clever men receive presents from the president. Each man gets either a red or blue present, and only knows the color of his own gift.

Then each man must guess a colour of a gift of some man: he must chose a man (besides himself) and a colour, write these down on a piece of paper and give this paper to an organiser. Once all this is done the organiser counts amount of correct guesses out of 100.

The men know all the described procedure in advance and have time to develop a strategy, before receiving any presents. Once they receive the presents, they will be unable to communicate with each other.

Their task is to guarantee maximum amount of correct guesses. Your task is to say 1) what is this maximum amount, 2) what can be a strategy of the men and, the most important: 3) prove that there is no other strategy, which can guaranty a bigger amount.

P.S. "Guarantee" - means that this amount should be achieved independently of luck and what presents are. It can be that all 100 presents are blue, or all red, or a mix, distribution between men also is arbitrary.
P.P.S. It feels like 50 is right answer, it is easy to figure out a strategy to do this, but it is really hard to prove that this is the best result. Note that 1. several men can guess about one present, 2. man can chose who he is guessing about After he got his present.

Seeing the [tag:hat-guessing], I initially thought it had something to do with the Winter Bash ;) — ghosts_in_the_code, Dec 21 '15 at 15:37

score 7 · Answer 1 · answered Dec 21 '15 at 00:09

I can guarantee exactly 50 correct guesses.

Using the Foolowing Strategy:

First the men group themselves into two groups of exatly 50 each.
For convenience we will name those groups A and B.

The next step is for everyone to find themselves into pairs.
Each pair has to consist of one person from group A and one person from group B.

Please note, that these two steps are done before receiving presents.

After receiving the presents the following guesses will be made:

Everyone will guess for the other person in his pair.

Everyone from group A will guess the same color as the present he received.

Everyone from group B will guess the opposite color as the present he received.

Guessing this way will give the following results:

If both people in a pair have the same color the one from group A will have guessed right and the one from group B will have guessed wrong.

If both people in a pair have a different color the one from group A will have guessed wrong and the one from group B will have guessed right.

This way we guarantee exactly one right guess in each pair for 50 pairs.

Why it should not be possible to get more:

Since they aren't allowed to communicate in any way each one would have a chance of exactly 50% to guess right since every person can have one of two states.

Now we can have one person of each pair guess one stated based on his own present and the other person of each pair guess the other state based on his own present.

If we now group them together to pairs then each pair as well can only have one of two possible states.(Those states being "same color" and "different color")

Totally unclear prove. The men could develop different strategy, don't force themselves to work in pairs only and may be get much better number of correct guesses, which they can guarantee. — klm123, Dec 21 '15 at 09:16
Also consider a possibility to decide who you guess about basing on the color of your present. They do have it. — klm123, Dec 21 '15 at 09:20

score 5 · Answer 2 · answered Dec 21 '15 at 14:19

5

Another possible 50% success strategy:

Pick two people, A and B. Divide the people into groups of 25, G1,G2,G3, and G4. Make sure A is in G1 or G2 and B is in G3 or G4.

Everyone in G1 guesses that B has a red present.

Everyone in G2 guesses that B has a blue present.

Everyone in G3 guesses that A has a red present.

Everyone in G4 guesses that A has a blue present.

Everyone in G1 or everyone in G2 will be right (25 right)

Everyone in G3 or everyone in G4 will be right (25 right)

No one has to guess themselves

Therefore we get exactly 50%

answered Dec 21 '15 at 14:19

StephenTG

3,565
1
21
27

I think this may be on the right track. – Matt Cremeens Dec 21 '15 at 20:49
Another way to state what I think you are getting at is section off the group into 25 groups of 4 (label them M1, M2, M3 and M4). M1 guesses M2 to be red and M3 guesses M2 to be blue (that is one guaranteed correct answer). M2 guesses M3 to be red and M4 guesses M3 to be blue (another guaranteed correct answer). Each of the 25 groups of 4 follow the same strategy and you have 25 groups with 2 correct answers, or 50 answers guaranteed to be correct. – Matt Cremeens Dec 21 '15 at 21:10

score 4 · Accepted Answer · answered Dec 21 '15 at 16:28

4

Here is a proof that more than 50 is impossible.

No matter what strategy a player uses, they will be wrong exactly half of the time. Why? Let Alice be a particular player. For each present distribution $P$, define a corresponding distribution $f(P)$, where you change the color of the person that Alice is guessing and leave all other colors the same.

Since $f(P)$ doesn't change Alice's color, it doesn't change her guess, which means that $f(f(P))=P$. In addition, $f$ has no fixed points. Therefore, we can break up the set of all $2^{100}$ distributions into pairs $(P,f(P))$. Alice will be correct for exactly one distribution in each pair, so she is correct half the time.

This means that each person gets 0.5 guesses correct on average, so adding these up, the team gets 50 guesses correct on average. This proves that it is impossible to guarantee getting more than 50 (if they always get 51 or more, then the average would be 51 or more).

Put another way: from Alice's perspective, she is guessing the value of a coin flip she has no information about, so she has to be correct with probability 1/2.

answered Dec 21 '15 at 16:28

Mike Earnest

32,336
6
92
237

Interesting approach, but doesn't the fact that our 100 people develop a strategy makes their guesses correlated (dependent on each other)? And if they are correlated you can not add up them so simply. – klm123 Dec 21 '15 at 18:18
1

You can though! If you have two random variables, then the expected value of their sum is the sum of their expected values, no matter how the variables are correlated. This is a surprising property about expected values that makes a lot of probability problems really cool. – Mike Earnest Dec 21 '15 at 18:32
@MikeEarnest - while you're right about random variables, developing a strategy means that the number of correct guesses isn't necessarily random. In others words, while swapping from $P$ to $f(P)$ won't change Alice's guess about John's color, it might change John's guess about Lucy's color, and thus "replace" Alice's now incorrect answer with a correct one (by John). For the record, I think you might be right but I think the proof is incomplete. – Duncan Dec 21 '15 at 18:58
1

Indeed, you can simply consider all 2^100 cases, collect 1002^100 guesses, exactly 502^100 of those would be correct, which proves that you can't get 51 correct at each separate case. – klm123 Dec 21 '15 at 21:57
Great proof ...But, instead of taking the average across all the possible cases, I am trying to prove in the following way but don't know how to proceed. "Let's say that someone claims that x ( x= any number >50 ) is the guaranteed maximum number of correct guesses.To refute this, I propose the following. Take any sequence, m of presents. Let D(m) be the sequence of guesses that results in x or greater correct guesses. Here is proof that there exists m' sequence of presents such that D(m') has to be <= 100- x number of correct guesses." Can you please tell me how to formulate such a proof ? – Hemant Agarwal Nov 04 '22 at 22:28

score 0 · Answer 4 · answered Dec 21 '15 at 00:11

0

1, the max is 50. 2, they should all guess the same person but half should say blue, the other day red. That would mean that 50 are correct, and 50 are wrong. 3, assuming that there are an even number of red and blue gifts, getting one half correct is the highest available. If there are more red than blue, guessing all one color could result in fewer than 50.

answered Dec 21 '15 at 00:11

rfair404

157
1

6

If they all guess the same person, that person can't guess themself. – f'' Dec 21 '15 at 00:27

score 0 · Answer 5 · answered Dec 21 '15 at 19:29

I think we can get to 98!

We designate two men ahead of time, call them A and B. When guessing begins, one man with a red present (if there is one) will choose person A and make a random guess. Then, another man with a red present chooses the previous man and guesses red. This proceeds in the same fashion with B and the blue presents. When all other guesses are made, A and B choose any man in their chain and guesses the color of that chain, A guesses red, B guesses blue. In the event either A or B is not chosen at all, they choose someone from the other chain and guess THAT color. The only ones that could be wrong would be the men that start each chain, and even then, they have a 50% chance of being right as well!

Matt Cremeens · Answer 6 · 2015-12-21T20:28:11.380

0

I'm thinking you could get at least 99 right provided that the men write their answers down sequentially after so much time has passed. If the men are labeled M1, M2, ..., M100, then if M1 is red, he should guess M2's color and hand it in within, say, 5 seconds. If M1 is blue, then he should let the 5 seconds pass, signifying to the group that he is blue. If M2 is red, he should guess M1's color according to their scheme; otherwise, he lets 5 seconds pass and thereby signifying that he is blue and deferring to M3, and so on. So in this manner only reds will guess until you've reached M100. After you reach M100, those who did not answer yet must be blue and they should answer as such for each other. The only one that could possibly get it wrong would be M1.

edited Dec 21 '15 at 20:28

answered Dec 21 '15 at 19:53

Matt Cremeens

467
3
10

Actually, I'm thinking you could get all 100 with this strategy if the M1 person is someone who is red. So at random, a man with a red present volunteers himself and he is red and thereby M1. No blue will volunteer to go first and everyone else would line up behind him and commence their strategy as outlined above. – Matt Cremeens Dec 21 '15 at 20:00
And I'm going back to 99 being my answer because M1 will have no idea if he is right about M2 or not. – Matt Cremeens Dec 21 '15 at 20:25
It seems hard to distinguish this from any other form of communication. Might as well have anyone with a red gift scratch their nose twice, or shout out "I HAVE A RED BOX!" This assumes they can even see each other after receiving gifts. Imagine they are all locked in their own padded, solitary confinement chambers after strategizing. – Matt Dec 21 '15 at 20:27
@Matt perhaps, but the puzzle didn't specify this and there is no obvious signal being given; they all just need to pay attention to the order they are in and who is turning in their paper and who is not. – Matt Cremeens Dec 21 '15 at 20:30
What would you call the delay (or lack of delay) if not a signal? – Matt Dec 21 '15 at 20:34
I would say this violates the rule of "they will be unable to communicate ". Besides, if you were able to see each other to know how long they take to answer, couldn't you just look at the box they are holding? – Trenin Dec 22 '15 at 12:49

Guess another's present

6 Answers6

Linked