How many scientists can survive?
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.
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.
The scientist in the rear states the sum of all 99 visible numbers, $S_{99}$. He or she will die. The second to last scientist is hopefully clever enough to understand why the prior scientist clearly picked a faulty number. This scientist can now can sum the 98 visible numbers, $S_{98}$, to uniquely determine his or her own number, $S_{99} - S_{98}$.
This idea is repeated, saving all the remaining scientists.
All but one survive.
Edit: Unfortunately, I forgot that $\oplus$ is only guaranteed to keep us within the number of bits, but we could still get higher. Instead, let's deal with modular arithmetic.
Suppose we have prisoners $N_1,\ldots,N_n$, where their numbers are $n_1,n_2,\ldots,n_n$ (ie $n_i$ is the number of the scientist). For my purposes, suppose that we draw from the range $0, \ldots, n$ instead of $1, \ldots, n+1$ (it's trivial to convert from one range to the other). Also, let's define the order of the prisoners such that $N_i$ can see all $N_j$ such that $i>j$. Further, define the operator $\%$ such that $a\mathbin{\%}b = c$, where $c \equiv a \mod b$ and $c \in \{0,\ldots,b-1\}$. Okay.
Scientist $N_n$ computes $A_n=(\sum_{i=0}^{n-1} n_i)\mathbin{\%} n$ and says that.
Scientist $N_{n-1}$ computes $(A_n - (\sum_{i=0}^{n-2} n_i))\mathbin{\%} n = n_{n-1}$ and says that.
Scientist $N_j$ computes $(A_n - (\sum_{i=j+1}^{n-1} n_i) - (\sum_{i=0}^{i-1} n_i))\mathbin{\%} n = n_j$
And so each Scientist extracts their number. This results in a minimum of $98$ scientists living, since $99$ will figure out their numbers, but one might say the number said by $N_n$. Note that there is a chance, albeit small, that all $100$ scientists live.
The OP says that there is a way to save $99$ scientists. This would require $N_n$ to somehow encode the $2$ numbers he cannot see into just one of those $2$ numbers, so that $N_{n-1}$ can figure out his number. I am not sure how to do this...