Hat problem

[tj86430]

I believe that something like Joaz's solution can work (although I've not checked that solution in detail).

There is a simpler approach that gets 75%.

Big clue:

Nominate someone to be dummy.

Ok, got it now:

Ignore one player altogether (he doesn't guess, and no one is interested in his hat

The remaining three will do as follows:
- if you see two hats of different color, don't guess
- if you see two hats of same color, guess the other color

[rhubarb]

Big clue:

Nominate someone to be dummy.

Ok, got it now:

Ignore one player altogether (he doesn't guess, and no one is interested in his hat

The remaining three will do as follows:
- if you see two hats of different color, don't guess
- if you see two hats of same color, guess the other color

In the spirit of the puzzle, an amendment:

Ignore one player altogether (he doesn't guess, and no one is interested in his hat During deliberation, before hat distribution, shoot one player.

[palapiku]

Nicely done!
Turns out i misinterpreted the bridge hint after all.

I interpreted it to mean that the 4 players separate into partnerships, each with its own strategy. This gives two 12/16 solutions, which are completely different from tj86430's. In particular, nobody is left out - everyone has a potential to make a guess.

The fact that there are several 12/16 solutions suggests that it could be possible to do even better... I suppose the next step is to prove that that is impossible.

[yoyoma]

Go version of the hint:
There are 4 kibitzers: 1 guest, and 3 registered [1d] players.

[tj86430]

Perhaps it would be nice to hide the previous message, since the hint is still hidden.

[Joaz Banbeck]

...Ignore one player altogether (he doesn't guess, and no one is interested in his hat

The remaining three will do as follows:
- if you see two hats of different color, don't guess
- if you see two hats of same color, guess the other color

That solution is:

-> loses 1 of 1
-> wins 3, loses 1
-> wins 2 of 2
-> wins 4 of 4
-> wins 3, loses 1
-> loses 1 of 1

...and gets 12 of 16.

[yoyoma]

Joaz, your solution gives the same 75% rate, and it's more complicated. So tj's answer seems better.

[Joaz Banbeck]

Joaz, your solution gives the same 75% rate,...

MINE WORKS???



I was just choosing guesses to create an example. I wasn't trying to solve the problem, just trying to show the format of a solution.

[drmwc]

Nicely done!
Turns out i misinterpreted the bridge hint after all.

I interpreted it to mean that the 4 players separate into partnerships, each with its own strategy. This gives two 12/16 solutions, which are completely different from tj86430's. In particular, nobody is left out - everyone has a potential to make a guess.

The fact that there are several 12/16 solutions suggests that it could be possible to do even better... I suppose the next step is to prove that that is impossible.

I don't know if I should use a spoiler, but people may be grunching the thread...

Proving 75% is optimal sounds like quite an intersting problem. I have no idea how one could go about it other than brute force and ignorance.

The set of possible deterministic solutions is presumably finite, which makes brute force and ignorance plausible. However, random strategies could be used. I don't see off-hand how they can improve things, but they do have the annoying feature of making the solution space infinite, So some general nonsense result may be needed to cope with this.

Brute force and ignorance can get you an awfully long way in maths...

[lightvector]

Solution and attempted proof of optimality:

Any individual player, conditional on that player making a guess, can be correct at most 50% of the time. So, intuitively, how is it that we can do better than 50%?

Simple: imagine we've already decided on player 1's strategy and we're now trying to choose player 2's strategy. If we can arrange it so that player 2's wrong guesses coincide with player 1's wrong guesses, whereas player 2's correct guesses happen at times that player 1 wouldn't have attempted to guess, we can increase the number of outcomes where at least one correct guess happens, without increasing at all the number of outcomes where an incorrect guess happens. As long as we can do this efficiently enough with each subsequent player, it's not hard to see why in theory we might be able to beat 50%.

There are several other classic puzzles with the same concept as this one. In all of them, the key is to choose strategies for the players that cause wrong guesses to be as densely concentrated as possible and correct guesses to be as disjoint as possible. The "bridge" strategy is very effective at this - in the cases that anyone guesses wrongly, 3 people all do so, whereas in the cases that anyone guesses correctly, there is only 1 person doing so. This results in there being 3 hat combinations guessed correctly for every 1 hat combination guessed wrongly, and since this strategy also always has someone guess, the winning percentage is precisely 3:1 = 75%.

A little bit of thought along these lines reveals that since at most 4 players can guess wrongly at once, an immediate upper bound for the best possible winning percentage for any strategy is 4:1 = 80%.

For this specific problem, there is also an interesting geometric visualization. Take all of the hat combinations to be vertices of a graph where there is an edge between two vertices if they differ in exactly one hat. In the 3-person case, this graph is simply a cube. In the 4-person case, it's a hypercube.

Saying that someone will guess a particular color for their own hat when they see a certain combination of other hats is equivalent to choosing a single edge in the graph and marking one of the vertices for that edge as "wrong" and the other as "correct". The choice of edge corresponds to the the choice of person and combination that they see, while the choice of which vertex to mark wrong/correct corresponds to color of hat we want that person to guess in that case. The goal is to maximize the number of vertices marked "correct" at least once and marked "wrong" zero times.

Visualizing it like this, it's now easy to see that 75% is optimal. In general, we will consign some number of vertices to be marked "wrong", and then by choosing all outgoing edges, we can cause all adjacent vertices to them to be marked "correct". And it's clear for any fixed choice of vertices that we'd like to be the "wrong"-marked ones, doing this is the best we can do. Now, if we choose any 4 vertices to be marked "wrong" in such a way that all other vertices are adjacent to at least one of them, we get one of the 75% solutions, because we are correct on all but 4 out of 16 vertices. We can only potentially do better by initially choosing fewer vertices to be "wrong", but if we choose 3 or fewer vertices, then since each vertex has only 4 outgoing edges, we can make at most 12 vertices "correct", which is again only 75%.

Therefore, 75% is optimal.

[Joaz Banbeck]

I just added the above post to the 'best of L19' thread.

[mitsun]

MINE WORKS???

Joaz, sorry to burst your bubble, but your "solution" scores 1/16

[cyclops]

4 bridge players are at a table. The tournament director offers them the following proposition:
.........bullets........more bullets.............

After too many casualties the next tournament director is a nicer guy. He offers the following proposition. If at least one guess is right and no guess is wrong they get €100 otherwise they pay a fine. The tournament director prepares the set of 4 hats that will be distributed randomly over the players. All other rules are the same as before. ( to be sure: no one gets shot What fine makes this a fair proposition? Does it make a difference if dummy is excluded from the experiment and only a set of 3 hats is prepared?

I have no idea of the answer but in the second case I include my trivial observation:

The tournament director of course chooses hats of the same color to defeat the solution of original problem. oops, but then the players anticipate on that