Skip to main content
Puzzling

Return to Answer

Commonmark migration
Source Link
Community Bot
Community Bot
  • 1

Combining the answer of @Collett89 and the comments of @user2357112, I get:

##45 prisoners used, 33 died##

45 prisoners used, 33 died

#The first day#

The first day

On the first day, have 40 prisoners drink from 525 bottles each, with each prisoner shifting by 25 bottles. In other words, prisoner 0 drinks from 0..524, prisoner 1 drinks from 25..549, etc, with the range wrapping around after 999 (so prisoner 20 drinks from 500..999 and 0..24). There are two cases that result.

#The second day, case 1#

The second day, case 1

Most of the time, there will be 2 groups of 25 bottles that are suspect, with poison A in one group and poison B in the other group. Depending on where the two bottles were located, between 2 and 20 prisoners died. So at least 20 prisoners survived and can be reused. To find the two specific bottles requires 10 prisoners. It takes 5 prisoners to find each bottle.

To find the one poison bottle in a group of 25, you have 5 prisoners drink from all of the bottles in the other group (some of the survivors will have already done this). Then each of the 5 prisoners drinks from bottles that have a particular bit is set in the binary representation of the bottle. So, prisoner 0 drinks from bottles where bit 0 is set (1, 3, 5, 7, ... 25). Prisoner 1 drinks from bottles where bit 1 is set (2, 3, 6, 7, 10, 11, ... 23). At the end, the dead prisoners make up the bits of the bottle number. So if prisoners 0, 2, and 3 died, the bottle number would be 01101 or 13. To avoid the worst case of 4 prisoners dying, number the bottles such that the bottles with 4 bits are skipped (i.e. don't use 15, 23, 27, 29, 30, 31). At worst, 3 prisoners die per bottle found.

Final result, case 1: 40 prisoners used, 26 died

#The second day, case 2#

The second day, case 2

The other possibility is that both poisoned bottles will be in the same group of 25 bottles. This means 21 prisoners will have died on the first day. Now, we do the same sort of thing as on the first day. We need 24 prisoners, and each will drink from 13 bottles, shifted by one. This will kill between 0 and 12 prisoners.

Final result, case 2: 45 prisoners used, 33 died

By the way, I tried with other numbers such as 32 prisoners dividing the bottles into groups of 32. But 40/25 was the best split given that the worst case scenario was to find both poison bottles in the same group.

Combining the answer of @Collett89 and the comments of @user2357112, I get:

##45 prisoners used, 33 died##

#The first day#

On the first day, have 40 prisoners drink from 525 bottles each, with each prisoner shifting by 25 bottles. In other words, prisoner 0 drinks from 0..524, prisoner 1 drinks from 25..549, etc, with the range wrapping around after 999 (so prisoner 20 drinks from 500..999 and 0..24). There are two cases that result.

#The second day, case 1#

Most of the time, there will be 2 groups of 25 bottles that are suspect, with poison A in one group and poison B in the other group. Depending on where the two bottles were located, between 2 and 20 prisoners died. So at least 20 prisoners survived and can be reused. To find the two specific bottles requires 10 prisoners. It takes 5 prisoners to find each bottle.

To find the one poison bottle in a group of 25, you have 5 prisoners drink from all of the bottles in the other group (some of the survivors will have already done this). Then each of the 5 prisoners drinks from bottles that have a particular bit is set in the binary representation of the bottle. So, prisoner 0 drinks from bottles where bit 0 is set (1, 3, 5, 7, ... 25). Prisoner 1 drinks from bottles where bit 1 is set (2, 3, 6, 7, 10, 11, ... 23). At the end, the dead prisoners make up the bits of the bottle number. So if prisoners 0, 2, and 3 died, the bottle number would be 01101 or 13. To avoid the worst case of 4 prisoners dying, number the bottles such that the bottles with 4 bits are skipped (i.e. don't use 15, 23, 27, 29, 30, 31). At worst, 3 prisoners die per bottle found.

Final result, case 1: 40 prisoners used, 26 died

#The second day, case 2#

The other possibility is that both poisoned bottles will be in the same group of 25 bottles. This means 21 prisoners will have died on the first day. Now, we do the same sort of thing as on the first day. We need 24 prisoners, and each will drink from 13 bottles, shifted by one. This will kill between 0 and 12 prisoners.

Final result, case 2: 45 prisoners used, 33 died

By the way, I tried with other numbers such as 32 prisoners dividing the bottles into groups of 32. But 40/25 was the best split given that the worst case scenario was to find both poison bottles in the same group.

Combining the answer of @Collett89 and the comments of @user2357112, I get:

45 prisoners used, 33 died

The first day

On the first day, have 40 prisoners drink from 525 bottles each, with each prisoner shifting by 25 bottles. In other words, prisoner 0 drinks from 0..524, prisoner 1 drinks from 25..549, etc, with the range wrapping around after 999 (so prisoner 20 drinks from 500..999 and 0..24). There are two cases that result.

The second day, case 1

Most of the time, there will be 2 groups of 25 bottles that are suspect, with poison A in one group and poison B in the other group. Depending on where the two bottles were located, between 2 and 20 prisoners died. So at least 20 prisoners survived and can be reused. To find the two specific bottles requires 10 prisoners. It takes 5 prisoners to find each bottle.

To find the one poison bottle in a group of 25, you have 5 prisoners drink from all of the bottles in the other group (some of the survivors will have already done this). Then each of the 5 prisoners drinks from bottles that have a particular bit is set in the binary representation of the bottle. So, prisoner 0 drinks from bottles where bit 0 is set (1, 3, 5, 7, ... 25). Prisoner 1 drinks from bottles where bit 1 is set (2, 3, 6, 7, 10, 11, ... 23). At the end, the dead prisoners make up the bits of the bottle number. So if prisoners 0, 2, and 3 died, the bottle number would be 01101 or 13. To avoid the worst case of 4 prisoners dying, number the bottles such that the bottles with 4 bits are skipped (i.e. don't use 15, 23, 27, 29, 30, 31). At worst, 3 prisoners die per bottle found.

Final result, case 1: 40 prisoners used, 26 died

The second day, case 2

The other possibility is that both poisoned bottles will be in the same group of 25 bottles. This means 21 prisoners will have died on the first day. Now, we do the same sort of thing as on the first day. We need 24 prisoners, and each will drink from 13 bottles, shifted by one. This will kill between 0 and 12 prisoners.

Final result, case 2: 45 prisoners used, 33 died

By the way, I tried with other numbers such as 32 prisoners dividing the bottles into groups of 32. But 40/25 was the best split given that the worst case scenario was to find both poison bottles in the same group.

Source Link
JS1
JS1
  • 18.3k
  • 3
  • 54
  • 106

Combining the answer of @Collett89 and the comments of @user2357112, I get:

##45 prisoners used, 33 died##

#The first day#

On the first day, have 40 prisoners drink from 525 bottles each, with each prisoner shifting by 25 bottles. In other words, prisoner 0 drinks from 0..524, prisoner 1 drinks from 25..549, etc, with the range wrapping around after 999 (so prisoner 20 drinks from 500..999 and 0..24). There are two cases that result.

#The second day, case 1#

Most of the time, there will be 2 groups of 25 bottles that are suspect, with poison A in one group and poison B in the other group. Depending on where the two bottles were located, between 2 and 20 prisoners died. So at least 20 prisoners survived and can be reused. To find the two specific bottles requires 10 prisoners. It takes 5 prisoners to find each bottle.

To find the one poison bottle in a group of 25, you have 5 prisoners drink from all of the bottles in the other group (some of the survivors will have already done this). Then each of the 5 prisoners drinks from bottles that have a particular bit is set in the binary representation of the bottle. So, prisoner 0 drinks from bottles where bit 0 is set (1, 3, 5, 7, ... 25). Prisoner 1 drinks from bottles where bit 1 is set (2, 3, 6, 7, 10, 11, ... 23). At the end, the dead prisoners make up the bits of the bottle number. So if prisoners 0, 2, and 3 died, the bottle number would be 01101 or 13. To avoid the worst case of 4 prisoners dying, number the bottles such that the bottles with 4 bits are skipped (i.e. don't use 15, 23, 27, 29, 30, 31). At worst, 3 prisoners die per bottle found.

Final result, case 1: 40 prisoners used, 26 died

#The second day, case 2#

The other possibility is that both poisoned bottles will be in the same group of 25 bottles. This means 21 prisoners will have died on the first day. Now, we do the same sort of thing as on the first day. We need 24 prisoners, and each will drink from 13 bottles, shifted by one. This will kill between 0 and 12 prisoners.

Final result, case 2: 45 prisoners used, 33 died

By the way, I tried with other numbers such as 32 prisoners dividing the bottles into groups of 32. But 40/25 was the best split given that the worst case scenario was to find both poison bottles in the same group.