[CrackMonkey] Think I figgered it out

[Mr. Bad]

>>>>> "JH" == Joey Hess <joey at kitenet.net> writes:

    >> He can calculate the parity of those behind him from their
    >> responses.

    JH> How, exactly?

We give each color a value: red=0, blue=1. Then, for any set of hats,
we sum up the values. If the sum is even, then the parity is even
(zero). If the sum is odd, the parity is odd (1).

Since the mechanism I described will make sure that EVERYONE gets
saved (except the poor sap who is tallest), person X will know that
all the answers of people behind him were correct. So he can count on
those responses to calculate his parity.

We can assume that it wouldn't be hard for each person to do the sum in
their head. However, it looks like it would be tough to calculate if
there are 3 x 10^14 people behind you. But it's not! You can just keep
a running total in your head, and then as each person answers, toggle
it if they say "blue," or leave it if they say "red."

Of course, if anyone fucks up their mental calculation, everyone
afterwards is hosed.

Hey, so, here's a little python program that kind of simulates the
situation, in order to make it more plain. It's not very elegant, but
it gets the point across. Note that calc_parity will give an implicit
0 parity for null arrays.

---8<---
#!/usr/bin/py

import whrandom # For making up hats

# Note: these calculations are done by the "victims"

def calc_parity(array):
    sum = 0
    for i in array:
        sum = sum + i
    return (sum % 2)   
       
def give_response(prev_responses, hats_ahead):

    if (len(prev_responses) == 0):
        # I am the first! I will die!
        return calc_parity(hats_ahead)
    else: 
        total_parity = prev_responses[0]
        before_parity = calc_parity(prev_responses[1:])
        after_parity = calc_parity(hats_ahead)

        my_hat = total_parity ^ (before_parity ^ after_parity)

        return my_hat

# calculations done by the aggressors

NUM_VICTIMS = 10 # or whatever
victim_hat = [None] * NUM_VICTIMS # Forgot how to do an empty list!

for j in range(NUM_VICTIMS):
    victim_hat[j] = whrandom.randint(0,1)

# vicious aggressors make sure the first guy dies

victim_hat[0] = not calc_parity(victim_hat[1:])

print victim_hat

responses = [None] * NUM_VICTIMS

for k in range(NUM_VICTIMS):
    responses[k] = give_response(responses[:k], victim_hat[k+1:])

print responses

for l in range(NUM_VICTIMS):

    if (responses[l] == victim_hat[l]):
        print "Prisoner ", l, " lives!"
    else:
        print "Prisoner ", l, " dies!"        
---8<---

Now, I challenge someone to figure out a way to save that first guy,
if you KNOW that the aggressors will maximize the casualties. In other
words, can you use their forced aggression against them?

~Mr. Bad

-- 
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
		     Mr. Bad <mr.bad at pigdog.org>
	 Pigdog Journal | http://pigdog.org/ |  RoR - Alucard
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~