wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> generalize the prisoners' problem
        
(Message started by: pandasbox on Jul 4^th, 2013, 9:38pm)

Title: generalize the prisoners' problem
Post by pandasbox on Jul 4^th, 2013, 9:38pm

The original problem is 10 prisoners with any distribution of either white or black hats in a line with each prisoner looking at all the prisoners in front of them. (Ie, how you would expect to line up at a supermarket.) No prisoner is able to see their own hat colour. The prisoners begin guessing their own hats starting from the back of the line, announcing only their guess for the warden and the other prisoners to hear. Prisoners who guess wrong will die the next day.

A related problem is N+1 different hat colours distributed for N prisoners, with each hat colour appearing only once. No prisoner may repeat another guess, and each prisoner can only say one of the N+1 guesses. If you haven't solved this I encourage you to find the solution to this problem as well.

I want to generalize this problem to N+M colours of hats for M prisoners, with each coloured hat able to appear any number of times. What is the maximum number of prisoners we can save?

Title: Re: generalize the prisoners' problem
Post by towr on Jul 5^th, 2013, 5:21am

on 07/04/13 at 21:38:28, pandasbox wrote:

A related problem is N+1 different hat colours distributed for N prisoners, with each hat colour appearing only once. No prisoner may repeat another guess, and each prisoner can only say one of the N+1 guesses. If you haven't solved this I encourage you to find the solution to this problem as well.

Well, each prisoner has the choice of two hats, so if we number all the hats and say the highest number one is white, and the lowest numbered one black, then perhaps we have reduced it to the older version?

Title: Re: generalize the prisoners' problem
Post by rmsgrey on Jul 5^th, 2013, 5:36am

And for the k-colours version, assuming the possible colours are known in advance and each prisoner can recognise each colour without comparing it to similarly coloured hats, you simply need an agreed numbering of the colours from 0 to k-1, then the back prisoner sums the hats in front of him modulo k and announces the corresponding colour.

It's pretty much the same as the 2-colour version, except that instead of parity you track k-arity

Title: Re: generalize the prisoners' problem
Post by rmsgrey on Jul 5^th, 2013, 5:41am

on 07/05/13 at 05:21:43, towr wrote:

Each prisoner except the one at the back has a choice of three hats before anything is said - his own, the spare, and the guy at the back's. The guy at the back can eliminate one of those three, but it's not immediately obvious he can do so in a way that lets everyone else know which of the remaining two is theirs...