14 replies to this topic

[bushindo]

i believe i can do it with 13.

Spoiler for tastes good

as before, label the bottles 1-500 in binary and assign 9 prisoners each binary bit for drinking.
then with the four extra prisoners, prisoner 1x drinks the bottles prisoners 1, 3, 5, 7, and 9 have drinken from.
(the bottles with any odd bits set.)
prisoner 2x drinks the bottles prisoners 2,3,6,7 have drinken form.
prisoner 3x drinks the bottles prisoners 4,5,6,7 have drinken from.
prisioner 4x drink the bottles prisoners 8,9 have drinken from.

in this way, the four extra prisoners act as a a parity check of the 9 drinking prisoners.
as an example... let's say the acomplice is prisoner 7.
we get a result of prisoners 1, 3, and 7 dieing. this tells us that bottle 2^6 +2^2 +1 = 69 is likely poisoned.
however, only prisoner 1x and 2x die. therefore 7 was the accomplice
let's say the acomplice was 4x. let's say 3,5, and 7 die. this tells us that 2^2 +2^4 +2^6 = 84 is likely poisoned.
prisoner 1x, 2x, 3x, and of course 4x dies. since all 4 of them had no drinks in common, you know one of the extras was the accomplice. therefore the 84th bottle was poisoned.

Question regarding this approach

Spoiler for example

The solution seems to add 4 prisoners, where
prisoner 1x drinks the bottles prisoners 1, 3, 5, 7, and 9 have drinken from.
prisoner 2x drinks the bottles prisoners 2,3,6,7 have drinken form.
prisoner 3x drinks the bottles prisoners 4,5,6,7 have drinken from.
prisioner 4x drink the bottles prisoners 8,9 have drinken from.

So, suppose that prisoner 7 and prisoner 8's allotted drinks include the poison, and they both die. From the scheme above, the prisoners 1x, 2x, 3x, and 4x will die as well.

Suppose prisoner 7 and prisoner 8 have the poisoned wine among their drinks, this scheme seems like it can not distinguish between the cases where the the accomplice is among the remaining non-parity-check prisoners (i.e., prisoner 1, prisoner 2, and so on).

[phil1882]

hmm, you're right defiantly need to rethink it. my method would only really work if two poison drinkings = not poisoned, 3 = poisoned and so on...

[bonanova]

Spoiler for maybe

I never did any ECC work, I only knew a few who made a living doing it.
Did some reading without understanding much, but I think I'd put the
extra four men on bits 1 2 4 and 8.

Next you'll ask how to use that extra info.
And I'll leave that to another solver.

Maybe I'll learn how this stuff works from the answer.

[phil1882]

okay once more...

Spoiler for complex parity check

prisoner 1x drinks from the bottle if bits 1 2 4 5 7 9 result in odd by xoring them together.
2x drinks if bits 1 3 4 6 7 result in odd by xor.
3x 2 3 4 8 9
4x 5 6 7 8 9
so, if prisoners 1 and 8 die, all four extras die.
let's say 2 also dies but is the false poison.
1x 2x 1 3x 2 3 4 4x 5 6 7 8 9
1 1 1 1 1 0 0 1 0 0 0 1 0 = 1 = dies, 0 = live
if you xor the same bits for each prisoner, you see that 1x is wrong, and 3x is wrong.
1 +4 = 5, the 5th bit is 2. therefore 2 is the poisoner.
if 5 was the false poisoner, you have prisoner 1x and prisoner 4x wrong. 1+8 = 9, with the 9th bit being 5.

[bushindo]

okay once more...

Spoiler for complex parity check

prisoner 1x drinks from the bottle if bits 1 2 4 5 7 9 result in odd by xoring them together.
2x drinks if bits 1 3 4 6 7 result in odd by xor.
3x 2 3 4 8 9
4x 5 6 7 8 9
so, if prisoners 1 and 8 die, all four extras die.
let's say 2 also dies but is the false poison.
1x 2x 1 3x 2 3 4 4x 5 6 7 8 9
1 1 1 1 1 0 0 1 0 0 0 1 0 = 1 = dies, 0 = live
if you xor the same bits for each prisoner, you see that 1x is wrong, and 3x is wrong.
1 +4 = 5, the 5th bit is 2. therefore 2 is the poisoner.
if 5 was the false poisoner, you have prisoner 1x and prisoner 4x wrong. 1+8 = 9, with the 9th bit being 5.

Congratulations, you got it. Great solve.