Author |
Topic: generalize the prisoners' problem (Read 2454 times) |
|
pandasbox
Newbie
Everything's gonna be alright.
Gender: 
Posts: 3
|
 |
generalize the prisoners' problem
« on: Jul 4th, 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 4th, 2013, 9:44pm by pandasbox » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: generalize the prisoners' problem
« Reply #1 on: Jul 5th, 2013, 5:21am » |
Quote Modify
|
on Jul 4th, 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: 2872
|
|
Re: generalize the prisoners' problem
« Reply #2 on: Jul 5th, 2013, 5:36am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: generalize the prisoners' problem
« Reply #3 on: Jul 5th, 2013, 5:41am » |
Quote Modify
|
on Jul 5th, 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print