Author 
Topic: generalize the prisoners' problem (Read 2293 times) 

pandasbox
Newbie
Everything's gonna be alright.
Gender:
Posts: 3


generalize the prisoners' problem
« on: Jul 4^{th}, 2013, 9:38pm » 
Quote Modify

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?

« Last Edit: Jul 4^{th}, 2013, 9:44pm by pandasbox » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13610


Re: generalize the prisoners' problem
« Reply #1 on: Jul 5^{th}, 2013, 5:21am » 
Quote Modify

on Jul 4^{th}, 2013, 9:38pm, 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?


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



rmsgrey
Uberpuzzler
Gender:
Posts: 2813


Re: generalize the prisoners' problem
« Reply #2 on: Jul 5^{th}, 2013, 5:36am » 
Quote Modify

And for the kcolours 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 k1, 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 2colour version, except that instead of parity you track karity


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2813


Re: generalize the prisoners' problem
« Reply #3 on: Jul 5^{th}, 2013, 5:41am » 
Quote Modify

on Jul 5^{th}, 2013, 5:21am, towr wrote: 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? 
 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...


IP Logged 



