wu :: forums
wu :: forums - generalize the prisoners' problem

Welcome, Guest. Please Login or Register.
Sep 23rd, 2018, 5:38pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: ThudnBlunder, Grimbal, towr, Eigenray, Icarus, william wu, SMQ)
   generalize the prisoners' problem
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: generalize the prisoners' problem  (Read 2298 times)
pandasbox
Newbie
*




Everything's gonna be alright.

   


Gender: female
Posts: 3
generalize the prisoners' problem  
« on: Jul 4th, 2013, 9:38pm »
Quote Quote Modify 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: male
Posts: 13640
Re: generalize the prisoners' problem  
« Reply #1 on: Jul 5th, 2013, 5:21am »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: generalize the prisoners' problem  
« Reply #2 on: Jul 5th, 2013, 5:36am »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: generalize the prisoners' problem  
« Reply #3 on: Jul 5th, 2013, 5:41am »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board