Return to Answer

This gives a solution using 60 servants for 1024 wines.Represent the wines using 10-bit binary numbers. Name the bits from A-J. Group the adjacent bits.

 AB--CD--EF--GH--IJ 

What is the value of AB for poisons? Give follg sets of wines to 4 different people.

 AB=00; AB=01; AB=10; AB=11 

If only one of them die, AB is completely resolved! If not, we get partial information. Do similar tests on remaining 4 groups.

 00--0(0|1)--11--(0|1)1--1(1|0) 

Consider CD & GH. If we know if set DG=00 died, we can link them. Since we dont know which test would be required, we run all 4-tests:

 CG=00; CH=00; DG=00; DH=00 

Similarly for GH and JK. If GJ=00 didnt die, the poisons will be:

 00--00--11--01--11 00--01--11--11--10 

Total # of tests/people needed: 5*4 + C(5,2)*4 = 60

PS: If you use groups of 3 (rather than 2), it doesn't improve. If you use groups of 4 or more, it worsens.

This gives a solution using 60 servants for 1024 wines.Represent the wines using 10-bit binary numbers. Name the bits from A-J. Group the adjacent bits.

 AB--CD--EF--GH--IJ 

What is the value of AB for poisons? Give follg sets of wines to 4 different people.

 AB=00; AB=01; AB=10; AB=11 

If only one of them die, AB is completely resolved! If not, we get partial information. Do similar tests on remaining 4 groups.

 00--0(0|1)--11--(0|1)1--1(0|1) 

Consider CD & GH. If we know if set DG=00 died, we can link them. Since we dont know which test would be required, we run all 4-tests:

 CG=00; CH=00; DG=00; DH=00 

Similarly for GH and JK. If GJ=00 didnt die, the poisons will be:

 00--00--11--01--11 00--01--11--11--10 

Total # of tests/people needed: 5*4 + C(5,2)*4 = 60

PS: If you use groups of 3 (rather than 2), it doesn't improve. If you use groups of 4 or more, it worsens.

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

This gives a solution using 60 servants for 1024 wines.Represent the wines using 10-bit binary numbers. Name the bits from A-J. Group the adjacent bits.

 AB--CD--EF--GH--IJ 

What is the value of AB for poisons? Give follg sets of wines to 4 different people.

 AB=00; AB=01; AB=10; AB=11 

If only one of them die, AB is completely resolved! If not, we get partial information. Do similar tests on remaining 4 groups.

 00--0(0|1)--11--(0|1)1--1(1|0) 

Consider CD & GH. If we know if set DG=00 died, we can link them. Since we dont know which test would be required, we run all 4-tests:

 CG=00; CH=00; DG=00; DH=00 

Similarly for GH and JK. If GJ=00 didnt die, the poisons will be:

 00--00--11--01--11 00--01--11--11--10 

Total # of tests/people needed: 5*4 + C(5,2)*4 = 60

PS: If you use groups of 3 (rather than 2), it doesn't improve. If you use groups of 4 or more, it worsens.

Here is a solution that is a bit simple to understand. It works with 64 servants in case of 1024 wines.

Let's say you have 64 servants. Divide them into two groups A,B (32 each). Connect every servant of group A with every other servant of group B using one line for each. Don't connect servants within a single group. This creates 1024 lines.

For every two users (x,y) connected with a line, give them a distinct wine.

The dead prisoners will tell u which two wines are poisoned.

In the best case, u will have 3 deaths; worst case 4 deaths.

This solution is not optimal; also grows a bit rapidly with number of wines.

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx