Five prisoners are going to take beans from a bag with 100 beans. They will do it one prisoner at a time, and only once each. No communication is allowed between them, but they can count the beans left in the bag. All prisoners who end with the largest and the smallest number of beans will die.
Who is most likely to survive?
Assume:
1. they are all smart people.
2. they will try to survive first and then try to kill more people.
3. they do not need to take out all the 100 beans.
You can assume that if someone will die, they will try to kill everyone else. This adds in an interesting twist, because if the first in a chunk will die, he will try to pick a number of beans to kill as many as possible. For example, one simple possibility is the first player taking all 100 beans, and leaving none for everyone else. This means everyone will die (which is the most people he can kill), but the first player will only choose this if there's no way for him to survive. (He will kill any number of people if it means his own survival.)
If the first player takes more than 20 beans, the second player can save himself by taking a number one less than what the first player took. The first player will die, but not everyone else will die. This is beat by the first possiblility, with everyone dying.
Since this is true, a prisoner will never take more than 2 more beans than the lowest player, and leave more beans than the lowest player took, because then someone else could take a number of beans such that they wouldn't die, nor would they leave fewer beans than the lowest player took, because then that lowest player would not have the fewest number of beans.
So this leaves two cases. A player taking one more bean than the lowest number, or the fourth player taking beans to leave beans equal to the lowest number of beans taken. Both of these would end up with all players getting killed.
Case 1: Taking one more bean: Each player would take beans equal to the lowest number or one more than the lowest number, as taking two more than the lowest number, or less than the lowest number would prevent the person who took the lowest number from dying. Both numbers would die, so everyone would die.
Case 2: Taking beans to leave the lowest number of beans left: This is just a special case, and only works if everyone has taken the lowest number of beans. Instead of taking the same number of beans as everyone else, the fourth prisoner could take beans to leave the lowest beans for the fifth prisoner. (The fifth prisoner won't take less than that, because that would prevent the first three prisoners from dying.) All five prisoners would die in this case as well.
Other than these cases, a prisoner will only take less than or equal to the current lowest total. Because of the foresight of previous prisoners, a prisoner can't take beans to force the remaining prisoners to take fewer beans (and thus prevent him from taking the fewest)
A prisoner will also not take two less than the highest number of beans, because then the next prisoner can take one less than the highest number of beans taken, and prevent himself from being killed. So he has to take the same number of beans as before, or if nobody has taken one more bean than the lowest amount of beans taken, he could take that.
This continues on to the fifth prisoner, who can take any amount he wants, as everyone will die no matter what. So everyone will die no matter what, so either the first prisoner can take all 100 beans to make sure everyone is killed, or he can take some other number 20 or less and everyone will insure that everyone else dies.

Posted by Gamer
on 20051127 15:17:44 