emptiness

]

Seems no-one responded to the simpler problem either. I guess the solution is to produce programming related problems instead of logic/maths related ones.

Well, here's the answer: There's 8 possible arrangements of hats. Assuming true random distribution, just by writing down the possibilities we see that: If you see 2 hats of the same colour, the chances are that yours is the other colour (3/8 instead of 1/8). So upon seeing two hats of one colour, you should guess the other colour - and if you don't, you should pass. This gives the team a 3/4 chance of success, since in every arrangement someone sees two hats of the same colour. The key is that you're actively betting against the two "all hats the same" possibilities.

There's a clear counter to this strategy, though - just give everyone the same colour hats. However, we can alter the above strategy to involve a uniform random element to prevent this. Call our people X, Y and Z and write a hattage as a 3-tuple with 0 and 1 as the colours. Then the strategy above is just betting against the two opposite hattages (0, 0, 0) and (1, 1, 1). You can just arbitrarily pick a hattage and its opposite to produce a new strategy, so for example picking (0, 1, 1) and (1, 0, 0) we find that the strategies are as follows:

X: If I see two of one colour, I pick that colour.
Y: If X has 0 and Z has 1, I pick 0. If X has 1 and Z has 0, I pick 1.
Z: If X has 0 and Y has 1, I pick 0. If X has 1 and Y has 0, I pick 1.

The possible hattages are:

(0, 0, 0): X wins, Y, Z pass.
(0, 0, 1): Y wins, X, Z pass.
(0, 1, 0): Z wins, X, Y pass.
(0, 1, 1): All three lose.
(1, 0, 0): All three lose.
(1, 0, 1): Z wins, X, Y pass.
(1, 1, 0): Y wins, X, Z pass.
(1, 1, 1): X wins, Y, Z pass.

Thus, once again we have a 3/4 chance of winning! Thus if the tablers secretly agree on a random hattage and its opposite before they are given hats, they will win more often than you'd expect.

This kind of strategy can be extended to higher numbers of people but since no-one was really bothered by the 3 person case, I won't detail the higher numbers here. It's available on the interweb anyway.

I'll try to come up with some interesting computational problem for my next one.

Re: Prisoners' Dilemma

[Jul. 23rd, 2008|04:22 pm]

[

Tags

]

So still no solutions.

It occurred to me that I don't have a proof that the following is optimal (though I'm pretty sure it is, as it stores useful data of length n into blocks of length n, in the sense that it allows every prisoner to infer the previous box by looking at any box). It's optimal for small numbers, anyway.

( Gory details )

The integration rule tells us that this is less than the integral from n/2 to n of 1/i, which basic integration tells us is ln(n) - ln(n/2) = ln 2, which is about 0.7. In other words, using this strategy, our prisoners can win just under a third of times they normally would, and by the arbitrary rules, survive.

It turns out that this is too much of a hassle for the warden, especially since his apparently mathematically minded victims aren't dying, so he's now picked a new problem (for which answers can be found online, as this also is not an original problem). He groups the prisoners into tables of 3, and places black or white hats on their heads. They have long peaks, so prisoners can't see their own hat colour. The challenge is that the prisoners around the table must either guess their hat colour or pass.

If they any prisoner guesses incorrectly, the warden will not feed any of them. If at least one guesses correctly and the rest guess correctly or pass, they get fed. If they all pass, the hats are re-picked randomly and they can have another go. Servings are reduced, so the prisoners will die if they don't eat strictly more than half of all mealtimes. Can they survive? If so, does the warden have a tactic to defeat this survival by picking hats in a nasty way?

Re: Prisoners Dilemma

[Jul. 14th, 2008|12:23 pm]

[

Tags

]

OK, since no-one even replied to that prisoner's dilemma, I guess it's time to produce some clues. We'll name the prisoners P1 through Pn and boxes B1 through Bn. We'll also, to avoid complications, assume the warden is going to arrange the boxes purely at random (so we don't need to cope with the warden just putting P1 in B2 and P2 in B1 for the 2 prisoner case, for example).¹

How do two prisoners play our game? If they both pick randomly, their joint chance of success is 1/4. However, if P1 picks B1 and P2 picks B2, they're either both correct or both incorrect, each with a 1/2 chance. This must be optimal or there'd be some one-prisoner strategy which is better than just picking one box.

What does this tell us?

The prisoners each need to pick different strategies.
The prisoners could do with knowing each other's strategies.

( 3 prisoner strategy with big hints )

¹ You can get around any strategy the warden produces by simply numbering the prisoners randomly after the box order is chosen, so that the warden doesn't know the prisoners' chosen ordering. (It doesn't have to be the same numbering as the warden used to call them in.)

Prisoners' Dilemma

[Jul. 7th, 2008|11:25 pm]

[

Tags

]

OK, so I keep seeing other people post intriguing puzzles, and there's at least one I have that I guess most people who'll read this haven't seen. I know there is a solution.

So, there's a bunch of prisoners (a few hundred), each with a unique name¹. They have a sadistic warden who is in charge of feeding them. The warden is somewhat lazy and wishes to cut costs, so he challenges the prisoners to a puzzle before they can be fed.

For each of the 3 alotted mealtimes, he will put each prisoner's name into a box, then shuffle the boxes, placing them at random along the back wall of the mess hall. The prisoners will then individually and randomly be called into the hall and allowed to nominate a box for the warden to open and read the contents. Each prisoner may continue to nominate boxes until either the warden reads his name or he has nominated half or more of the boxes. He will then be led out into the yard, with no contact with the yet-to-enter prisoners. The warden closes all of the boxes and calls in the next prisoner - every prisoner is presented with the exact same box arrangement.

Clearly if the prisoner touches the boxes in any way, leaves any notes behind, or attempts any form of communication whatsoever with his yet-to-enter comrades after he's entered the hall, the warden will have them shot.

Only if every prisoner finds his or her name will any of them be given meal tickets. If any one prisoner fails to find their own name, no prisoner will get a ticket. On the plus side, the warden is offering to give two tickets each if they do succeed. The prisoners are a hardy bunch and only need to eat once every few days on average to survive. Meal tickets can be hoarded and redeemed at any time, and the prisoners generally have a few spares lying around as they're used for trade.

The prisoners' job is to either come up with a strategy (the warden promises not to listen to their plans, but of course can try to predict them) which can keep them alive, or demonstrate to the prison authorities that the warden is a sadistic bastard - in which case they'll be able to get a new warden (who'll probably give them another sadistic game next week).

Obviously if you know the answer offhand, don't post it immediately. Some people may want to think about it. :)

¹ Also, they can't change their names. Thankyou, Sticky.

Misunderstandings that've resulted in edits: Prisoners need to win as a group, not just individually. Meal tickets are completely transferrable and the prisoners need only ensure that the tickets stay afloat on average. Boxes are not removed from the mess hall even if a prisoner finds his name.