wu :: forums « wu :: forums - generalize the prisoners' problem » Welcome, Guest. Please Login or Register. Sep 23rd, 2018, 5:38pm RIDDLES SITE WRITE MATH! Home Help Search Members Login 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 Notify of replies Send Topic Print
 Author Topic: generalize the prisoners' problem  (Read 2298 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: 13640
 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: 2818
 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: 2818
 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »