Another prisoners and hats problem General forum
73 replies. Last post: 20170625
Reply to this topic Return to forum
Carroll at 20170619
From a friend at facebook: "Email I just got from Peter Winkler:
100 prisoners will be fitted with red or blue hats according to fair coinflips. Then the lights are turned on; each prisoner sees every other hat color and must write down a guess for his own. If a majority (at least 51) get their own hat color right, all the prisoners will be freed.
As usual the prisoners can’t communicate once the hats are placed, but have time to strategize beforehand. Can they achieve a 90% probability of being freed? How about 95%?" 100 prisoners will be fitted with red or blue hats according to fair coinflips. Then the lights are turned on; each prisoner sees every other hat color and must write down a guess for his own. If a majority (at least 51) get their own hat color right, all the prisoners will be freed.
***I thought I got a way but it is not getting the chance of success over 95% so any idea from fellow at LG welcome!

richyfourtytwo at 20170619
Yep, I get 92.04. I made that calculation very quickly, so had no great confidence, but if you get the same it’s probably correct. :)
In the 5050 case all 100 would guess incorrectly with my strategy. In the 1000 and 0100 cases all would get it right.

alihv at 20170619
I got a little improvement over the simple scheme but I have no way of measuring it for 100 people. I’ve made some calculations for 20 instead.
Here’s the simple voting stats for comparison:
863820 escapes out of 1048576 (82.380295%)
popcount 0: 1 escapes out of 1 (100.000000%)
popcount 1: 20 escapes out of 20 (100.000000%)
popcount 2: 190 escapes out of 190 (100.000000%)
popcount 3: 1140 escapes out of 1140 (100.000000%)
popcount 4: 4845 escapes out of 4845 (100.000000%)
popcount 5: 15504 escapes out of 15504 (100.000000%)
popcount 6: 38760 escapes out of 38760 (100.000000%)
popcount 7: 77520 escapes out of 77520 (100.000000%)
popcount 8: 125970 escapes out of 125970 (100.000000%)
popcount 9: 167960 escapes out of 167960 (100.000000%)
popcount 10: 0 escapes out of 184756 (0.000000%)Here’s my algorithm:
883174 escapes out of 1048576 (84.226036%)
popcount 0: 1 escapes out of 1 (100.000000%)
popcount 1: 20 escapes out of 20 (100.000000%)
popcount 2: 187 escapes out of 190 (98.421053%)
popcount 3: 1074 escapes out of 1140 (94.210526%)
popcount 4: 4040 escapes out of 4845 (83.384933%)
popcount 5: 13901 escapes out of 15504 (89.660733%)
popcount 6: 37009 escapes out of 38760 (95.482456%)
popcount 7: 53376 escapes out of 77520 (68.854489%)
popcount 8: 71741 escapes out of 125970 (56.950861%)
popcount 9: 167860 escapes out of 167960 (99.940462%)
popcount 10: 184756 escapes out of 184756 (100.000000%)Hint: the prisoners don’t have to behave the same way.

magicnonno at 20170619
Maybe I am not getting the terms of the problem right, but if no communication is allowed after the lights are turned on, and if I cannot see what the others write down, then I think it can be proven that the chance of getting my color right is exactly 50%, no matter what my “strategy” is. Therefore the probability of 51 or more correct guesses is 0.460205.

michael at 20170619
If the guess must be instant after turning on the lights I agree with 92,04%. But there doesn’t seem to be a time indication, so they could write down their guess let’s say after 1 hour, 1 day, 5 days, ...?
With that setup, I’m convinced there are strategies that everyone knows their hat color. Or 100% certainty of being freed.

Tasmanian Devil at 20170619
Despite the success when the number of blue and red hats are different, the simple strategy mentioned is a complete failure when there equally many blue and red hats. In this case, every single prisoner will guess the wrong color. One could perhaps imagine a mixed strategy in which a prisoner will guess the least numerous color when they differ by 1 with a certain probability (or a certain portion of the prisoners could be instructed in advance to do this). However, this will affect the cases when the number of read and blue hats differ by 2. Since these cases are almost twice as common as the ones with equally many red and blue hats, it seems difficult to obtain an overall advantage in this way (and that is before we have considered the effects on the other cases if we make further adjustments in order to compensate). The only elements I can imagine in a mixed strategy are: Pick the most numerous color, pick the least numerous color, pick red, pick blue. But I don’t see how to improve on the trivial strategy, and I am curious how alihv found an improvement.
Although the prisoners may count the hats that they can see, they are not allowed to communicate with each other. Therefore, time is not an issue.
It is true that each prisoner has a 50% chance of getting their own color right, from their own perspective. Nevertheless, guessing the color that is most numerous among the 99 hats that are visible is a strategy that works perfectly well for the purpose whenever the number of blue and red hats are different (assuming an even number of prisoners). This is possible because the events of guessing correctly using this scheme are not independent.

Tasmanian Devil at 20170619
Somehow the three section have come in the opposite order here (I wrote them, then cut them to check that I had not missed any recent comments, then pasted).

alihv at 20170619
magicnonno, the probability of a person getting his color correctly is indeed 50%. However, an optimal strategy could make it so that when the prisoners escape, exactly 51 of 100 is correct, but when they fail, then 100 of 100 are wrong.
Now let us denote the probability of successful escape by p. The chance of getting it right for a single person is 0.51p = 0.50, therefore p is about 0.98. I believe that’s the upper bound on the success rate.

alihv at 20170619
> or a certain portion of the prisoners could be instructed in advance to do this
Yeah, perfect. Now when you’ve instructed everybody what to do if they see a 5049 split, imagine that you see a 5148 split. If you’re in the minority, then each of the 51 majority guys will see a 5049 split so they know what to do. More importantly, you know what they will do, so you know how many points they will score.

Carroll at 20170619
alihv, could you please explain your strategy in English?
what they do when they see 48r/51b, when they see 49r/50b, other cases...
Tasmanian Devil, I searched this way, throwing a biased coin when they see 49/50 to avoid being all wrong in case of 50/50 at the cost of being more wrong on 49/51, but it does not work well...
The simple algorithm of announcing the majority fails in the most probable case of the Gaussian that is 7.96%, for the 50/50 case... Seeing 49/50 in the 49/51 case only happens half of 7.82%.

Tobias Lang at 20170619
@Carroll: what happens with: say majority if it is 51+, else 58 people r determinated 2 say blue, 42 red?

Carroll at 20170620
Hard to answer to such non sentences when English is not your language ...
In case of majority algorithm for the case 42r/58b, red people see 41r and a majority of 58b so they write “blue” and are wrong. Blue people see 42r and a majority of 57b and write “blue” and are right...
So out of the 100 prisoners who write “blue”, 58 are right and they are freed.

alihv at 20170620
> alihv, could you please explain your strategy in English?
OK. Every prisoner gets assigned a number 1100.
If you see 50\49 split: if your number is between 1 and 51, join the minority, else join the majority.
(I call the 151 the Mensheviks and 52100 the Bolsheviks :))If you see N\99N split (N > 50, recursive on N):
if you’re minority, then each majority guy sees an N1\100N split. Simulate the strategy assuming you’re the minority. Now you know what those guys will do if you’re the minority, let’s say they score P points. If they win by themselves (P > 51), join the majority. If they can’t be helped (51 – P > 99 – N), join the majority. Otherwise count the number of minority guys with the number lower than yours, let this number be K. If K < 51 – P, join the minority. If K >= 51 – P, those K guys will take care of the minority case without you so join the majority.I’ve figured out how to simulate it for 100 but I didn’t do it yet.

Carroll at 20170620
I don’t understand how the rank can help, even in the 50/50 case:
Suppose out of the 50 reds, 25 are numbered 125 and 25 are numbered 76100, similarly for the 50 blue, 25 are numbered 2650 and 25 are numbered 5175: 25r25b25b25r.
They all see a 50\49 split so the 125r select minority red, the 2650b select minority blue, so we have 50 prisoners selecting right color, but for the ones numbered from 51 to 100 they will all chose majority so wrong color:
they don’t reach 51 good predictions and are not saved.

Tasmanian Devil at 20170620
Carroll, 51 prisoners “join the minority” (which I interpret as “pick the least numerous color”) and are correct, not 50. But I found it difficult to follow the 51/49 case. What exactly do you do when you see 51/48? There is an “otherwise” in the text, and it is not clear to me which “if” it belongs to.

alihv at 20170620
Tasmanian Devil is right, the 51th prisoner picks minority.
the intention was a cascade of checks, “otherwise” meant “in case none of the above produced an answer”.
Maybe this will help?
if (P > 51) { pick majority }
else if (51 – P > 100 – N) { pick majority }
else if (K < 51 – P) { pick minority }
else { pick majority } 
alihv at 20170620
Oops, the forum did some strange things to formatting. Anyway, I hope it’s clear...

Martyn Hamer at 20170620
If the prisoners are allowed to see what each other has written down then they can guarantee 50 correct guesses. They pair up, the prisoner on the left writes down their partner’s hat colour and the prisoner on the right copies it. The prisoners on the right all guess correctly and it’s virtually certain that at least one of the other 50 guesses will be correct.
This is probably cheating though...

Martyn Hamer at 20170620
Or how about this. The prisoners are told beforehand to count the number of red hats they see. If it’s odd, go to the left of the room. If it’s right, go to the right of the room. I think this will result in 2 groups of people each with the same colour hat regardless of the split.

Martyn Hamer at 20170620
It does say in the question that the prisoners can strategize before the hats are placed. My first solution may be pushing it but I don’t see an issue with the second one.

Tasmanian Devil at 20170620
It also says, no communication after the hats are placed. There are a number of ways they could solve the problem if they were allowed to signal each other. For example, they could form pairs and just show each other what they had by moving to one particular side of the room, wink with the right or the left eye, and so on.

Carroll at 20170620
Is there a way to write a formula for what we want to optimize, that is the probability that at least 1+n/2 prisoners guess their hat?
Do you think this probability is highest when the average number of prisoners guessing right goes just above 51? Any link between this probability and expectation?
If PGuess(i) is the probability with an algorithm that i prisoners guessed their hats:
P = product (i=0 to 50) (1PGuess(i)) (not 0 guessed right and not 1 guessed right and ... not 50 guessed right)
E = sum (i=0 to 100)(i*PGuess(i))

Carroll at 20170621
I will give you my current best strategy which gives a 92.197% equal to 1C(100,49)/2^100
Each prisoner announces the color of the majority if majority is bigger (strictly) than 50.
In case he see a 50\49 split, he announces the color of the minority.
He is right in case of a 50\50 split, and in case of n\100n with n>51. He is wrong in half the cases 51\49 and 49\51 when he sees 50\49 or 49\50 which amounts to only C(100,49) instead of C(100,50) for the naive majority strategy.

alihv at 20170621
> He is wrong in half the cases
In all the cases of 51\49 split the prisoners fail to escape, and that is C(100,49)+C(100,51)=2*C(100,49) cases. Or are you counting something else? 
magicnonno at 20170621
So, at the end of the day, did anyone come up with an algorithm that results in more than 92.04% probability to escape?
At this point I tend to believe it is impossible, but I would be happy to be proved wrong.

Carroll at 20170622
From Johan Wästelund:
A group of an even number of people can choose to either “play safe”, by half of them guessing that their number of blue hats is even and the other half guessing it’s odd, or “gamble”, by letting all of them guess on the same parity.
Here is a strategy that achieves 31/32:
Start by letting the first two people gamble. If they win (and everyone else will see whether they do without any illegal communication), then the remaining 98 play safe, while if they lose, the next 4 will gamble. In the latter case, if those 4 win, again all remaining play safe, while if they lose, the next 8 will gamble, and so on.
With this strategy, we achieve winning probability 3/4 with 6 people, 7/8 with 14, 15/16 with 30, and 31/32 with 62. Then we can let the last 38 play safe regardless.
We can improve to 125/128 = 97.65625% by starting from the first four people playing the “not 22”strategy which loses with probability 3/8, and then halving the losing probability four times by groups of the next 6, 12, 24 and 48 people.He then said "I can actually improve that to 1129480068741774213 / 1152921504606846976 = 97.96677954%"
I’m not sure how it works but I’ll try to program it.

ypercube ★ at 20170622
If other prisoners can see what the first 2 gambled, isn’t that a form of communication?
I thought this was not an option.

Tasmanian Devil at 20170622
I don’t think the other 98 can see if the first two are correct without communication.

Tasmanian Devil at 20170622
On second thought, they can see if the first two are right when only considering each other.

Tasmanian Devil at 20170622
It’s interesting how close Wästelund’s strategy comes to the upper bound that alihv mentioned earlier. In general, if there are n prisoners in total with n even, no strategy can give a success probability higher than n/(n+2). I was thinking of running through all possible strategies for n=4 (that is, assigning a guess for each player for each of the 2^(n1) possible combinations that he can see) to see if it was possible to improve on 5/8. Fortunately, I didn’t, because the optimal success probability must be an integer divided by 2^n (the integer being the number of successes among all 2^n combinations of red/blue hats). So we actually have an upper bound of [(n/(n+2)) * 2^n] / (2^n) where [x] means floor(x). (I am assuming that each player can have a fixed guess for each combination and does not need to introduce any randomness. This way of thinking of a strategy overrides what I wrote earlier about possible elements in a strategy, by the way.) For n = 4 and 6, this gives 5/8 and 3/4 respectively, which we have already attained in the discussion above. For n = 8, our bounds are 3/4 <= P <= 51/64, and for n = 10, we have 13/16=832/1024 <= P <= 853/1024. Can we tighten these bounds?

Carroll at 20170622
Can you explain Wäslund’s algo?
Starting with this sentence:
"Start by letting the first two people gamble. If they win (and everyone else will see whether they do without any illegal communication), then the remaining 98 play safe"
If they gamble and are right (p=1/2) then next 98 prisoners (who play safe assuming even probability of blue on the 98 prisoners) must get at least 49 good guesses out of 98 (51%), this gives 25.5% and i don’t see how in the case they are wrong this will bump up the probability to 31/32 ?

Tasmanian Devil at 20170622
The safe strategy means that any set of 2k players can always guarantee k right and k wrong guesses if this is satisfactory. So if the first two players win, the remaining 98 players play safe and get 51 right answers. If the first two players are wrong, the remaining group raises the stakes by letting four players gamble. If the four win, they have eliminated the bad start of the first two players. Otherwise, the group raises the stakes again by letting eight players gamble. The probability of failure for the whole group is halved for every time they can raise the stakes. It’s like playing odd or even numbers in roulette and doubling the bet for every time you lose until you win, except that you don’t care how much you can lose, you just want to maximize the probability of ending with a profit.
Wästelund or Wäslund’s strategy is probvably optimal when the total number of prisoners is of the form 2^k2, as the probability of success in these cases is equal to the upper bound.

alihv at 20170622
Thanks for bringing this in, this is awesome! I understand the strategy but not your question. I’m going to explain the strategy.
A prisoner from a “gambling” team counts the blue hats of his team, if the number is odd, he bets that his hat is blue, otherwise red. So if the number of blue hats in a gambling team is even, the entire team scores, otherwise none of them score.
A “safe” team consists of two equal parts. The first part does exactly the same as if they were on the gambling team – these guys don’t even need to care which kind of team they’re in. The second part bets on the opposite color. A safe team always achieves exactly half the score.
Since the expectancy of the prisoners' score is exactly 50, we want to achieve escapes as tight as possible and the failures as total as possible. The algorithm is going to achieve in every case either an escape with at most 1 point too many or a total failure (score = 0).
For 4 prisoners: always vote majority. There are C(4,2)=6 total failures and the rest works with either 3 or 4 points.
Now if we have an algorithm for a particular even N, we’re going to build algorithms for 2 N + 2 and 2 N + 4. The first N prisoners follow the algorithm.
If they fail: the rest N + 2 or N + 4 gamble. If they fail, the whole 2 N + 2 (+ 4) fail completely. If they win, we get N + 2 = (2 N + 2) / 2 + 1 – the exact amount of points we need – or N + 4 = (2 N + 4) / 2 + 1 + 1, so 1 point more than we need.
If the first N prisoners succeed: they bring us either N/2 + 1 points (exactly what we need) or N/2 + 2 (one point extra). The rest plays safe, bringing us N/2 + 1 (resp. N / 2 + 2) points for a total of at most N+3 (resp. N+4). We need (2N+2)/2+1 = N+2 (resp. (2N+4)/2+1=N+3) points to win, so it’s at most 1 point extra.
Now we just go for N = 100 via 4 > 10 > 22 > 48 > 100.

richyfourtytwo at 20170622
Nice. The strategy is basically identical to the ‘failsafe’ roulette system of always doubling if you lost.

Carroll at 20170622
Awesome!
Yes sorry for miss writing his name, he is Johan Wästlund: https://wastlund.blogspot.fr/2017/06/13532385396179numberwhichisitsown.html

Tasmanian Devil at 20170623
I also tried to improve on the algorithm by recursively finding F(N, k), the highest possible probability for N prisoners to get k correct answers, but so far I “only” got to 97.915856769...% for F(100, 51). :)

Tasmanian Devil at 20170623
The program actually found improvements in both the smaller cases I asked for earlier: F(8, 5) >= 49/64 and F(10, 6) >= 209/256 = 836/1024.

Carroll at 20170623
What is the size of the first group of prisoners you start from in your algorithm?
If it is in python you can use the Fractions package to get an exact figure, or send me the algo I can code it in python...

Tasmanian Devil at 20170623
My algorithm considers a number of different approaches, including groups of 14 players (1 player could announce beforehand that he will pick red, and the others can see if he is right). It chooses the best one, but I don’t know which of the approaches are contributing and which don’t.

Carroll at 20170623
In your recursive formula, when a subset s of N gambles (or try to get max probability of having k good guesses) and fails , how many good guesses do you take into account for the next step of (Ns)?
Or if you care to give your recursion?

Tasmanian Devil at 20170623
for N = 1 to 100
for k = 0 to 100
if 2*k <= N then F[N][k] = 1 {play safe}
elseif k > N then F[N][k] = 0 {impossible to get more right answers than prisoners}
elseif k = N then F[N][k] = 0.5 {gambling to get all correct}
else
F[N][k] = (F[N1][k1] + F[N1][k]) / 2 {one player could “gamble”, and the other N1 could optimize accordingly}
x = (F[N2][k2] + F[N2][k]) / 2 {two players could gamble, and the other N2 could optimize accordingly}
if x > F[N][k] then F[N][k] = x {update if impovement}
if F[N2][k1] > F[N][k] then F[N][k] = F[N2][k1] {update if letting two prisoners play safe is an improvement}
if N > 3 then
{try letting three players play according to different strategies}
x = (F[N3][k3] + F[N3][k]) / 2 {let all three gamble}
if x > F[N][k] then F[N][k] = x {update if improvement}
x = (F[N3][k2] + F[N3][k1]) / 2 {let two of them play safe; the third picks a preselected color}
if x > F[N][k] then F[N][k] = x {update if improvement}
x = (F[N3][k3] + 3 * F[N3][k1]) / 4 {the three players maximize the chance of getting 2 right}
if x > F[N][k] then F[N][k] = x {update if improvement}
x = (3 * F[N3][k – 2] + F[N3][k]) / 4 {opposite of last strategy}
if x > F[N][k] then F[N][k] = x {update if improvement}
endif
if (N > 4) and (k > 3) then
{let four players guess the most numerous color among them, or the opposite strategy}
x = (F[N4][k4] + 4 * F[N4][k3] + 3 * F[N4][k]) / 8
if x > F[N][k] then F[N][k] = x
x = (3 * F[N4][k4] + 4 * F[N4][k1] + F[N4][k]) / 8
if x > F[N][k] then F[N][k] = x
endif
{Then same (most/least numerous color) for 6 and 8 players – details left out}
for i = 1 to k
x = (F[Ni][ki] + F[Ni][k]) / 2 {let any number of prisoners gamble, then play accordingly}
if x > F[N][k] then F[N][k] = x
next i
for j = 2 to N
if jN and jk then
x = F[N/j][k/j] {partition the prisoners into blocks of j people who always “gamble” together}
if x > F[N][k] then F[N][k] = x
next j
for i 0 = ceiling(k/2) to floor((N1)/2)
x = (1+F[N2*i][ki]) / 2 {play safe with i players if that is enough, otherwise gamble}
if x > F[N][k] then F[N][k] = x
next i
endif
next k
next N
If there are errors, then it is possible that they appeared when I typed here, and that they are not in the actual code.
It is possible that there exist strategies for only 4 players that could lead to further improvements. If I have calculated correctly, then if we could attain distributions of 010024, 010105, 420100 and 501100 for 0, 1, 2, 3 and 4 correct answers, then all other distributions would lie in the convex hull of the ones we have found, and they would give improvements for F^{10}^{6} and F^{100}^{51}. Alas, I did not find any examples of these after running a few thousand simulations.

Carroll at 20170623
Thanks Tas,
I have a difference for the line:
elseif k = N then F[N][k] = 0.5 {gambling to get all correct}
I have :
elseif k = N then F[N][k] = 1/2^N {gambling to get all correct}
does that matter?

Tasmanian Devil at 20170623
I believe that is not correct. You may not perform as many as N halvings. My recursion should pick up the earlier ones.

Tasmanian Devil at 20170623
Correction: they can gamble as one group and succeed with probability 0.5.

Tasmanian Devil at 20170623
They can achieve this by agreeing to assume that there is an even number of red hats, for example.

Carroll at 20170623
They can gamble to achieve [N/2] : F(N,[N/2]) with probability 1, but not to achieve N good guesses out of N as in F(N,N) with probability 1/2...
Other question, what do you get for F(7,6) ? (I had to go to greater subsets than subset of size 4 to get something different of 0)

Tasmanian Devil at 20170623
The probability of an even number of red hats is always 0.5, regardless of whether N is even or odd.

Carroll at 20170623
I’m wrong again, there are more ways to have an even number of red hats (0 to 100, step 2) than an odd number but the whole parity only depends on the color of one’s hat which is random with even chances...

Tasmanian Devil at 20170623
I found the N = 4 strategies I was looking for. Details below. Incorporating these does not change F(7, 6) or F(8, 5), but F(10, 6) is improved to 53/64 = 848/1024 while F(100, 51) is improved to 0.97969390216... or 97.969390216..%
I did of course not figure out these strategies myself; I just ran the simulations a bit longer.
Distribution a_0 – a_1 – a_2 – a_3 – a_4 means: Among the 2^4=16 different ways to give the four prisoners hats, there are a_0 cases in which they get 0 right answers, a_1 cases in which they get 1 right answer, and so on.
Strategy for distribution 501100: Prisoner 1 picks blue if he sees exactly one red hat; otherwise he picks red. Prisoners 2 and 3 pick red if they see a red hat on the other one in this pair and exactly one red and one blue hat on prisoners 1 and 4; otherwise they pick blue. Prisoner 4 picks blue if he sees a blue hat on prisoner 1 and at least one blue hat on prisoners 2 and 3; otherwise he picks red. Inverting this of course gives distribution 010105.
Strategy for distribution 010024: Prisoner 1 picks red if he sees exactly one red hat; otherwise he picks blue. Prisoner 2 picks blue if he sees a red hat on prisoner 3 and at least one red hat on prisoners 1 and 4; otherwise he picks red. Prisoner 3 picks blue if he sees a red hat on prisoner 2 and exactly one red and one blue hat on prisoners 1 and 4; otherwise he picks red. Prisoner 4 picks blue if he sees red hats on both prisoners 1 and 2, or if prisoners 2 and 3 have the same color and prisoner 1 has the other color; otherwise he picks red.

Carroll at 20170624
Johan Wästlund added:
"The construction that gives 97.967% is based on “gambling” sets of various sizes. The first two people “gamble” by synchronizing their guesses so that both are right or both are wrong. The others can see their hats, and adjust their strategies according to whether the first two win or fail. If they win, the rest “play safe”. If they lose, then the next 3 will gamble. If those 3 win, then in the next turn 1 will gamble, while if they lose, 6 will gamble, and so on. There seems to be no simple pattern to the number of people to gamble in each situation. Instead, these are computed by “dynamic optimization”, considering for all k and n, the problem of achieving at least k correct guesses with n people.
This strategy is quite good, given that 50/51 is an upper bound, but it is in fact not optimal. Among other things, there is a scheme that gets 4 out of 5 correct with probability 5/8, and if one incorporates this into the recursion, the winning probability (for 51, 100) increases by a smidgeon."

Carroll at 20170624
Johan also invented Solitaire Random Hex style=“webkittaphighlightcolor: transparent; webkittextsizeadjust: 100%;”>Let’s play Hex like that. On an N by N hex board, you repeatedly point at a set of unoccupied cells, and those cells then get a color by one fair coin flip (all of them get the same color) . What probability can you achieve of getting a lefttoright crossing of your color?
It’s not too hard, but quite nice!"

magicnonno at 20170624
All these strategies that assume prisoners know if other prisoners got it write or wrong, are violating the main premise of the problem that no communication is allowed. They should not be considered valid solutions. I still think nobody has yet found a valid solution that gives more than 92.04% probability.

Tasmanian Devil at 20170624
If the strategy is agreed upon in advance, then everybody outside of any given group can tell how many in the group are right, if the group members only consider each other’s hats.

ypercube ★ at 20170624
@magicnonno I thought the same at first but I hadn’t read carefully. The strategies are valid solutions.

Carroll at 20170624
Johan Wästlund wrote:
"Interesting! I had missed the distribution 501100 ! I did include 60082, and 420100 can be achieved by first gambling one.
I also included (for N=5) the distribution 12000200, and for N=6 the distribution 250020361 (and their reverses).
But I hadn’t looked systematically even at N=4. Indeed the winning probability for (100,51) increases slightly when 501100 is included.
I now have 1156660494839725322061/1180591620717411303424"
Can anyone explain how you include different distributions into the recursive algo, how you test them, and why 010105 which just saves 6 prisoners is interesting?

Tasmanian Devil at 20170624
Good, we’re one the same wavlength! :) All distributions x_0 – x_1 – x_2 – x_3 – x_4 for N = 4 must satisfy x_0 + x_1 + x_2 + x_3 + x_4 = 16 and 2 x_0 + x_1 = x_3 + 2 x_4. So you can generate all 5tuples of nonnegative integers that satisfy these; there are 177 of them if I remember correctly. But for our purpose of using them as coefficients in the recursion, we don’t need all of them. If a tuple is in the convex hull of some others, then it is redundant. The distributions I considered are, as I mentioned earlier, tuples that are vertices of the convex hull.

Tasmanian Devil at 20170624
I did not include 12000200 and 250020361, which probably is the reason why he got even higher than I did. Should I take a look at the vertices of the convex hull for N = 5 and 6?
"Can anyone explain how you include different distributions into the recursive algo"? As you saw, I just checked each one if it gave an improvement – does that answer the question?

Tasmanian Devil at 20170625
It seems that all potential distributions for N=5 are in the convex hull of 12000200, 16000016, 0802400, 01600160, 02000012, 00161600, 0024080, 4202600, 5012600, 6002420, 6002501, 0026024, 0026105, 0224006 and 1025006.

Tasmanian Devil at 20170625
For N=6, the vertices of the convex hull are, if my calculations are correct:
00064000
480001600
320000032
032000320
003203200
004800016
242000380
250100380
240040360
250003360
260000362
250011370
038000224
038001025
036040024
036300025
236000026
037110025
120004300
020204200
021014200
022004020
022004101
004300201
004202200
004210210
024000220
104100220
Please note that I have not proved that these are attainable. But if they are, they should be sufficient to cover N=5 and N=6.