Emperor, wines, and accomplice- with a nod to meciless emperor

[bushindo]

This is a variant of ujjagrawal's excellent puzzle

Suppose that like ujjagrawal's puzzle, an assassin infiltrates a king's cellar and poisons 1 of the king's 500 wine bottles. Upon being detected and cornered, the assassin takes a suicide pill and dies.

Anyone who consumes even the most minute amount of the poisoned wine will die between 12 and 24 hours. Consumers of the poisoned wine exhibit no other symptom besides death, and the poison can not be detected by any other means.

The emperor decides to use some prisoners to taste the wine in order to determine the poisoned bottle. There is one catch, however. It is known that the assassin has precisely one accomplice among the prisoners. The accomplice has access to the same poison that the deceased assassin used to envenom one of the king's bottle. If the accomplice is chosen as one of the tasters, he will surreptitiously consume the poison regardless of which bottle he is given to drink in the hope of corrupting the deduction process.

The emperor does not know which of his prisoners is the assassin's accomplice. The emperor is intrigued by this logical puzzle, and he figures that he can simply use some extra prisoners to compensate for this unknown unreliable taster. What is the minimum number of prisoners (and the tasting procedure) that he would need to use in order to correctly find the poisoned bottle among the 500 bottles within 24 hours?

[jim]

You can do it with 18. In place of each prisoner in the solution to the previous problem, use a pair. It counts as dying only if both prisoners die--otherwise it counts as survival. Now do as before. It may be possible to do with less than 18, but i would not no how.

[phaze]

In any circumstance will the accomplice not take poison to pevert the decision making process?

Edited July 27, 2012 by phaze

[TheChad08]

You can do it with 18. In place of each prisoner in the solution to the previous problem, use a pair. It counts as dying only if both prisoners die--otherwise it counts as survival. Now do as before. It may be possible to do with less than 18, but i would not no how.

So he will drink the poison no matter what?

[bushindo]

You can do it with 18. In place of each prisoner in the solution to the previous problem, use a pair. It counts as dying only if both prisoners die--otherwise it counts as survival. Now do as before. It may be possible to do with less than 18, but i would not no how.

That's a good start. It is possible to require a few prisoners less than that though.

In any circumstance will the accomplice not take poison to pevert the decision making process?

If selected as a taster, the accomplice will definitely commit suicide by drinking his own supply of poison. However, keep in mind that the emperor has many prisoners, and in the random selection procedure it is very possible that the accomplice is not chosen as a taster.

[phaze]

The maximum required to be used is 19 the minimum could be as low as 11 tasters try different glasses in pairs if both die you know that one was accomplace if this happens on the first attempt you no longer need to test in pairs but still need to figure out which set of glasses contained the poison.

Edit:

If you can however re-use trusted surviving prisnors it could be as low as 10 (depending on prisnors luck)

Edited July 27, 2012 by phaze

[bushindo]

The maximum required to be used is 19 the minimum could be as low as 11 tasters try different glasses in pairs if both die you know that one was accomplace if this happens on the first attempt you no longer need to test in pairs but still need to figure out which set of glasses contained the poison.

Edit:

If you can however re-use trusted surviving prisnors it could be as low as 10 (depending on prisnors luck)

I'll just note that the intent of the puzzle is that all prisoners have to sample the wine at the same time. Since the deadline is 24 hours and the poison will take effect randomly between 12 and 24 hours after consumption, it is not possible to wait and see the effects of one wave of wine drinking before applying another.

[bonanova]

Four extra prisoners can correct a single faulty bit for up to 2048 bottles.

So long as they're hamming it up a bit as they drink.

[bushindo]

Four extra prisoners can correct a single faulty bit for up to 2048 bottles.

So long as they're hamming it up a bit as they drink.

All correct there, except for one detail

9 + 4 = 13 prisoners won't be enough to correct a faulty bit up to 2048 bottles. You will need more prisoners for that many bottle.

The emperor would also like to request more details on this drinking scheme for the sake of completeness. You see, back in college the emperor majored in Political Science, which does not require any course in Computer Science, so concrete details on how to go about doing it would be very much appreciated.

[phil1882]

i believe i can do it with 13.

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.

[bushindo]

i believe i can do it with 13.

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

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]

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...

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...

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.