Initially I simplified the problem to one prisoner. The best way to reduce uncertainty was to split the bottles into two sets with 500 bottles each; the prisoner drinks from one, if he dies the poisonous wine is there, otherwise it’s in one of the leftover 500 bottles.
Then I added in a second prisoner. The problem doesn’t give me enough time to wait for the first prisoner to die, to know which set had the poisonous wine; so I had to have the second prisoner drinking at the same time as the first, from a partially overlapping set. This means splitting the bottles into four sets instead - “both drink”, “#1 drinks it”, “#2 drinks it”, “neither drinks it”.
Extending this reasoning further to 10 prisoners, I’d have 2¹⁰=1024 sets. That’s enough to uniquely identify which bottle has poison. Then the binary part is just about keeping track of who drinks what.
Did ya need the hint?
No, I only saw it after I solved the problem.
my reasoning / thought process
Initially I simplified the problem to one prisoner. The best way to reduce uncertainty was to split the bottles into two sets with 500 bottles each; the prisoner drinks from one, if he dies the poisonous wine is there, otherwise it’s in one of the leftover 500 bottles.
Then I added in a second prisoner. The problem doesn’t give me enough time to wait for the first prisoner to die, to know which set had the poisonous wine; so I had to have the second prisoner drinking at the same time as the first, from a partially overlapping set. This means splitting the bottles into four sets instead - “both drink”, “#1 drinks it”, “#2 drinks it”, “neither drinks it”.
Extending this reasoning further to 10 prisoners, I’d have 2¹⁰=1024 sets. That’s enough to uniquely identify which bottle has poison. Then the binary part is just about keeping track of who drinks what.