#51 · Tasmanian Devil
23 Jun 2017
In last line, should be: F(10, 6) and F(100, 51)
Public forum discussion.
23 Jun 2017
In last line, should be: F(10, 6) and F(100, 51)
23 Jun 2017
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?
23 Jun 2017
I believe that is not correct. You may not perform as many as N halvings. My recursion should pick up the earlier ones.
23 Jun 2017
Correction: they can gamble as one group and succeed with probability 0.5.
23 Jun 2017
They can achieve this by agreeing to assume that there is an even number of red hats, for example.
23 Jun 2017
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)
23 Jun 2017
Hum no I get your point!
23 Jun 2017
... but it is even in 51 cases and odd in 50 cases, so if N even ([N/2]+1)/N
23 Jun 2017
I get 33/64 = 0.515625 for F(7, 6).
23 Jun 2017
The probability of an even number of red hats is always 0.5, regardless of whether N is even or odd.
23 Jun 2017
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...
23 Jun 2017
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 5-0-1-10-0: 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 0-10-1-0-5.
Strategy for distribution 0-10-0-2-4: 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.
24 Jun 2017
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."
24 Jun 2017
Johan also invented "Solitaire Random Hex":
"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 left-to-right crossing of your color?
It's not too hard, but quite nice!"
24 Jun 2017
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.
24 Jun 2017
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.
24 Jun 2017
@magicnonno I thought the same at first but I hadn't read carefully. The strategies are valid solutions.
24 Jun 2017
Johan Wästlund wrote:
"Interesting! I had missed the distribution 5-0-1-10-0 ! I did include 6-0-0-8-2, and 4-2-0-10-0 can be achieved by first gambling one.
I also included (for N=5) the distribution 12-0-0-0-20-0, and for N=6 the distribution 25-0-0-2-0-36-1 (and their reverses).
But I hadn't looked systematically even at N=4. Indeed the winning probability for (100,51) increases slightly when 5-0-1-10-0 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 0-10-1-0-5 which just saves 6 prisoners is interesting?
24 Jun 2017
And btw 1156660494839725322061/1180591620717411303424 =0.9797295479 !
24 Jun 2017
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 5-tuples 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.
24 Jun 2017
I did not include 12-0-0-0-20-0 and 25-0-0-2-0-36-1, 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?
25 Jun 2017
It seems that all potential distributions for N=5 are in the convex hull of 12-0-0-0-20-0, 16-0-0-0-0-16, 0-8-0-24-0-0, 0-16-0-0-16-0, 0-20-0-0-0-12, 0-0-16-16-0-0, 0-0-24-0-8-0, 4-2-0-26-0-0, 5-0-1-26-0-0, 6-0-0-24-2-0, 6-0-0-25-0-1, 0-0-26-0-2-4, 0-0-26-1-0-5, 0-2-24-0-0-6 and 1-0-25-0-0-6.
25 Jun 2017
For N=6, the vertices of the convex hull are, if my calculations are correct:
0-0-0-64-0-0-0
48-0-0-0-16-0-0
32-0-0-0-0-0-32
0-32-0-0-0-32-0
0-0-32-0-32-0-0
0-0-48-0-0-0-16
24-2-0-0-0-38-0
25-0-1-0-0-38-0
24-0-0-4-0-36-0
25-0-0-0-3-36-0
26-0-0-0-0-36-2
25-0-0-1-1-37-0
0-38-0-0-0-2-24
0-38-0-0-1-0-25
0-36-0-4-0-0-24
0-36-3-0-0-0-25
2-36-0-0-0-0-26
0-37-1-1-0-0-25
1-20-0-0-43-0-0
0-20-2-0-42-0-0
0-21-0-1-42-0-0
0-22-0-0-40-2-0
0-22-0-0-41-0-1
0-0-43-0-0-20-1
0-0-42-0-2-20-0
0-0-42-1-0-21-0
0-2-40-0-0-22-0
1-0-41-0-0-22-0
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.