Correct answer is 8


#1

Hear me out.
The minimum number of prisoners that we can use is 10, no doubts about that. Out of these 10, how many will be killed in the worst case?
For each number from 0 - 1023, we can assign a bottle based on the binary representation of the corresponding number. If there’s a ‘1’ in the i-th place then the i-th prisoner gets the bottle.
Now, we need not choose the numbers 0-999 as mentioned in the official solution. Let us choose such 1000 numbers that the maximum number of set bits is minimum, say k bits. This way no matter which bottle is poisoned, at most k prisoners will die.
C(10, 0) + C(10, 1) + C(10, 2) + … + C(10, k) >= 1000
For k = 8, this holds true.

Another way to look at this - out of 1024 possible combinations, only 10 are lethal to 9 prisoners and 1 is lethal to all 10 prisoners. 1024 - 10 - 1 = 1013 which is more than what we need.

Correct me if I’m wrong.


#2

Yup good point . The numbers 511 767 895 959 991 1007 1015 1019 1021 1022 are the only cases where all 9 prisoner will be killed . We can code these numbers to other like 511 can be coded to 1001 and so on . So final answer would be 8 then .