[CrackMonkey] A cool problem

[Chris J. DiBona]

Two answers:

If A is the number of adversaries:

Answer 1: If A > N

N should just accept their fate and pop themselves. 

Answer 2: If A , N

Revolt! Overtake your oppressors better to die on your feet than on your
knees.

  Chris


--
Linux Community Evangelist, VA Linux Systems            http://www.valinux.com
President, Silicon Valley Linux Users Group               http://www.svlug.org
Grant Chair, Linux International.                            http://www.li.org
Co-editor, Open Sources	                                 http://www.dibona.com

On Sun, 13 Feb 2000, Seth David Schoen wrote:

> ... posed by my girlfriend, who heard it from some grad student friends at
> Berkeley:
> 
> n people are captured by an adversary and told that, after this scenario
> has been explained to them, they may mutally agree on a strategy (with the
> adversary listening to all their discussions) and then use it to try to
> save as many people as possible.
> 
> The people will be lined up in a row, sorted by height, so that the first
> person can see everyone else, the second person can see everyone else but
> the first person, the third person can see everyone else but the first
> and second people, etc.
> 
> Each person will be wearing either a red or blue hat and (of course!)
> cannot see what color hat he or she is wearing.
> 
> The people will be asked, one after another, in the order they were lined
> up, "What color hat are you wearing?"  (The first person is asked, and
> answers; then the second person is asked, and answers; then the third
> person is asked, and answers, and so on.)
> 
> Each person must answer promptly (no manipulation of latency allowed).
> Each person must say either "red" or "blue", and may not say anything
> else at any time.  Nobody is allowed to decline to answer.
> 
> Once everyone has answered, everyone who answered correctly is released
> and everyone who answered incorrectly is killed.
> 
> The people are also told that, after they have conferred on their
> strategy, the adversary will choose their respective hat colors so as to
> maximize the number of people who will be killed, given what can be deduced
> from what they have said about their strategy.  (This is to say that their
> hat colors will be chosen adversarially with respect to their strategy.)
> 
> Now the people are allowed to deliberate about their strategy, knowing
> that their deliberations are overheard.
> 
> By guessing randomly, they could obviously save everyone with probability
> 1/(2^n), but they would expect to save only n/2 people, and they would
> not be guaranteed to save anyone.
> 
> That doesn't sound like a great idea.  A better strategy would guarantee
> that some number of people would be saved.
> 
> How many people can they definitely save?  How?  How many people can they
> possibly save that way?
> 
> -- 
> Seth David Schoen <schoen at loyalty.org>  | And do not say, I will study when I
> Temp.  http://www.loyalty.org/~schoen/  | have leisure; for perhaps you will
> down:  http://www.loyalty.org/   (CAF)  | not have leisure.  -- Pirke Avot 2:5
> 
> 
> _______________________________________________
> CrackMonkey: Non-sequitur arguments and ad-hominem personal attacks
> http://crackmonkey.org/mailman/listinfo/crackmonkey
>