Yesterday the aliens took 100 scientists from Earth as prisoners. They want to test how smart the humans are.
The aliens made 101 headbands, numbered from 1 to 101. On the contest day, they throw away one of the headbands, and then from the remaining headbands randomly put one on each of the scientists. Then they line up the scientists in a queue in such a way that each person can see the numbers written on the headbands of the people who stand in front of him, but can't see his/her own number, nor the number of the scientists behind him.
Then the aliens will force the scientists to guess their numbers, and after everybody finished saying a number, they will kill those who said a number different from what is written on their headbands. Note that each scientist can only say one number in the range 1-101, and no one can say a number that has already been said. Each scientist can independently choose when to speak their guess; there is no pre-set order on when they have to speak. As you are very smart, the scientists asked you to find a way to save the most of them. Find this way, and then prove it.
Best Answer
You can save 99.5 scientists.
Imagine that the 101st headband was left on the ground behind the first scientist, making a line of 101 headbands.
The strategy is that everyone should assume that the headbands are laid out in an even permutation of the numbers {1, 2, ..., 101}. Each scientist will always have a choice of two headbands: one results in an even permutation and one results in an odd permutation. They always make the choice which results in an even permutation.
If the headbands are actually in an even permutation (half the time), everyone guesses correctly. (More formal inductive proof below.)
If the headbands are actually in an odd permutation then the first scientist is dead. But the other scientists are still saved: they will end up naming a permutation which is correct except for the switch of the first scientist's headband with the one on the ground.
Proof that everyone guesses correctly if the headbands are actually in an even permutation:
Consider the first scientist. He can see 99 headbands, so he knows there are only two possible arrangements. These arrangements are related by a single swap (swapping his headband for the one left on the ground), so one of them is an even permutation and the other is odd. His strategy is to say the number which corresponds to the even permutation, and we're assuming here that it actually is an even permutation, so his guess is correct.
Now consider the nth scientist. We can assume for induction that the first (n-1) scientists have guessed correctly, and he can see a further (100-n) headbands. So he knows a total of 99 numbers. This means that, again, there are only two possible arrangements, and the two arrangements are related by a single swap (swapping his headband for the one on the ground). So precisely one of these arrangements is an even permutation, and this is the one that the nth scientist will guess. This means that the nth scientist has also guessed correctly, since we know that the actual arrangement is the even permutation.