[CrackMonkey] A cool problem
Chris J. DiBona
chris at dibona.com
Sat Feb 12 12:59:38 PST 2000
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
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
> 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
More information about the Crackmonkey