How many scientists can survive?

Question

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.

Answer 1

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.

Answer 2

Before the first person talks the second person has three potential options $a<b<c$ We will find a way so that the first person makes the second person have the correct answer (Of course the first person knows the three options the second person can have which are a,b or c. What we will do is that if the second person has $a$ he says $b$, if the second person has $b$ he says $c$ and if the second person has $c$ he says $a$. If person $1$ does this he can save person $2$, person $3$ can then do this to save person $4$ and so on. I don't think this is optimal but it may help. This method would save half the people when $n$ is even and slightly less than half when $n$ is odd.

Answer 3

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.

Answer 4

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...

Answer 5

We can save $m$ scientists with $m$ to be determined below - and probably more. The numbers of the first $m$ scientists are known to the back $100-m$ scientists. Hence they all know the $101-m$ numbers distributed among them and the waste bin. They compute a permutation of these $101-m$ numbers and anounce the first $100-m$ these in the order thus obtained. This allows them to convey $\log_2((100-m)!)$ bits of extra information to the front $m$ persons encoded in the permutation. Now each of the front $m$ scientists need only choose between two possible numbers, the only two numbers not yet heard and not seen by her. To make a decision, she extracts one bit from the extra information. In order to achieve that all $m$ can extract one bit, we need $$ 2^m\le (100-m)!$$ This holds if we let $m=76$.

The permutation of $25$ numbers that the $24$ back scientists compute from looking at the first $m$ scientists can be considered random, hence has one fixed point on average and $\frac{24}{25}$ of this are scientists being saved. Thus

76 scientists guaranteed to be saved

76.96 scientists saved on average

Answer 6

99 Scientists Saved

The first scientist can deduce two possibilities for his number. If he makes a random guess, then the second scientist learns nothing and she will then also have a survival probability of only 50%. So clearly this will not work.

If, however, the first scientist sacrifices himself by somehow encoding the two possible numbers as a single number then all others will be able to deduce their numbers, so $99$ scientists will survive. One way of doing this for two numbers $x \ne y$ such that $$ 1 \le x,y \le 101 $$ is for the first scientist to announce the product, $p$, of $10000+x$ and $10000+y$ which can be expanded as $$ p = (1000+x)(1000+y) = 100000000 + 10000(x+y) + xy. $$ The $10000$ is large enough that $xy < 10000$ unless $x$ and $y$ are the pair $100$ and $101$, which is easily dealt with as a special case. In all other cases, the other scientists can recover the two numbers via the two equations: $$ x + y = \lfloor \frac{p}{10000} \rfloor - 10000 $$ $$ xy = r $$ where $r$ is the remainder of $p$ modulo $10000$.

For example, if the first scientist announces the product $100801311$ the two equations are $ x + y = 80 $ and $ xy = 1311 $ which are readily solved to give $23$ and $57$.

---

Simpler encoding

Or one could encode the two numbers as a concatenation of either number followed by the other number written as a three digit number (with leading zeroes if necessary), e.g. $23057$ or $57023$ in the example above.

Answer 7

At Least 97 Scientists can be Saved

Assumptions - Additional Rules:

• scientists can only guess integers between 1 and 101
• if a scientist says a number that has already been said, all scientists are killed

---

First Scientist

Can see $99$ other numbers, so can deduce his two possible numbers $x$ and $y$. Announces a value $q=r+1$ where $r$ is the remainder of $x+y$ when divided by $101$. Hence $1 \le q \le 101$.

Any Middle Scientist Assuming all previous middle scientists have guessed correctly, she has knowledge of 98 correct numbers (the first scientist is unlikely to be correct). So she has to choose between three numbers: $a,b,c$. She must be able to find a pair, say $a,b$, such that $$ a+b+1 \equiv q \quad (\textrm{mod} \quad 101)$$ since two of her possible numbers must be the same as the first scientist's.

Assume there is another such pair, say $a,c$. Then $$ a+b+1 \equiv a+c+1 \quad (\textrm{mod} \quad 101) \quad \textrm{so} \quad b \equiv c \quad (\textrm{mod} \quad 101)$$ leading to $b=c$. So the assumption was false and there cannot be another distinct pair.

Since her number cannot be the same as either of the first scientist's possibilities (which are $a,b$), she is able to deduce her number ($c$).

What then if that number was already said?

Then the number must have been the one announced by the first scientist.

This unlucky middle scientist says the number of the last scientist (which cannot have been announced yet). Since all subsequent middle scientists are able to see the last scientist, each knows when this case has occurred and hence the actual number of this middle scientist. So then all other middle scientists can now assume that all prior middle guesses were correct, so are able to deduce their numbers. None can be blocked from saying their numbers.

Last Scientist

Can deduce his number by the same reasoning as for the middle scientists. If it has already been announced, he announces either of the two numbers that nobody has yet announced.

---

Possible Outcomes

First Scientist: survives only if the aliens removed the number $100$.

Middle Scientists: all survive if the aliens removed $100$, if the first scientist has $100$ (so says the number removed), or if he says the number of the last scientist. Otherwise, exactly one dies.

Last Scientist: survives only if the first scientist has $100$ (needs all middle scientists to survive) or if aliens removed $100$.