45
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • 9
    $\begingroup$ The scientist at the very back of the queque can see 99 numbers, that one should speak first , naming 1 of the 2 numbers he can't see with a 50% chance of saving themselves. After that the next to last scientist can see 98 numbers and knows they can't say the number chosen by the first scientist, so he also can choose from only 2 options. Continuing the process to the front of the queque each scientist will have a 50% chance of survival. This method would expect to save half of them, (but might possibly save none of them) I can't see how they could do any better. $\endgroup$ – WW1 Apr 20 '15 at 3:58
  • 14
    $\begingroup$ must the number said by a scientist be a number between $1$ and $101$? $\endgroup$ – Jorge Fernández-Hidalgo Apr 20 '15 at 5:21
  • 23
    $\begingroup$ I would contest that this is a much better fit for Puzzling.SE. $\endgroup$ – apnorton Apr 20 '15 at 18:08
  • 7
    $\begingroup$ This question should stay here. It's an interesting math problem. (In my limited experience, too many of the puzzles on puzzling.SE rely on lateral thinking.) $\endgroup$ – Samuel Apr 20 '15 at 22:31
  • 6
    $\begingroup$ This looks like a clear cut example of what belongs on the puzzling SE. Whether a problem belongs there has nothing to do with whether it's 'lateral' thinking or not, there are plenty of math questions there too. I also want to point out to OP that they have yet to update the problem statement with the requirement that the scientists can only say numbers from 1 to 101. Imo, it's unreasonable to say the scientists can't say numbers larger than 101 on the basis that scientists can apparently process video encodings in binary per @Gamamal's comments.... $\endgroup$ – Shaz Apr 21 '15 at 17:06
52
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Nice! All scientists after the first one are saved due to two wrongs making a right! $\endgroup$ – Samuel Apr 20 '15 at 16:32
  • 3
    $\begingroup$ I do not understand this solution. Would you mind expanding on the "by induction part" and everything? $\endgroup$ – Ant Apr 20 '15 at 16:59
  • 2
    $\begingroup$ This seems to assume that the erring scientists are killed instantly (and thus the others learn whether their predecessors were correct). The problem statemetnt says otherwise. $\endgroup$ – Hagen von Eitzen Apr 20 '15 at 21:11
  • 10
    $\begingroup$ @HagenvonEitzen: No. If the first scientist is wrong, then the remaining scientists will assume he was right, and base their calculations off that. But they are also using the incorrect assumption that the permutation is even, and these two wrongs miraculously cancel out. $\endgroup$ – Samuel Apr 20 '15 at 21:16
  • 7
    $\begingroup$ @HagenvonEitzen: the point is that collectively the scientists will all deduce the same permutation, and that permutation is correct except that it might have the back two headbands the wrong way around. That's the only mistake they can make. And 99 of the scientists aren't affected by that mistake. They don't need to know whether the scientists behind them were right, they only need to know what they said. Hearing that leaves them with two headbands to choose from (theirs, and one of the back two), and except for the first scientist they'll all choose their own. $\endgroup$ – Steve Jessop Apr 20 '15 at 21:26
40
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 7
    $\begingroup$ Ok, although if you can say any number the problemas males no sense, just give a number which produces a vídeo explaining what everyone mudt say when processed by a computer. $\endgroup$ – Jorge Fernández-Hidalgo Apr 20 '15 at 6:02
  • 80
    $\begingroup$ New solution: One scientist begins to recite the digits of $\pi$. This filibuster is maintained until the space marines arrive. $\endgroup$ – suneater Apr 20 '15 at 6:25
  • 7
    $\begingroup$ @zahbaz Thanks for your solution. but I don't think that the scientists are able to say any number they want(though the question didn't say anything about it). Suppose that the number assigned to first scientist is a, second is b, third is c and so on, The last person could just say this number: a0b0c0d0... . so everybody (except the last person) would know his number. $\endgroup$ – lino Apr 20 '15 at 7:20
  • 14
    $\begingroup$ Since $S_{99}-S_{98}$ is between 1 and 101, this solution also works if the scientists are only allowed to say a number between 1 and 101: simply compute all sums modulo 100 (taking the representative in $[1,101]$). Of course the scientists have to be able to elaborate their strategy beforehand, but that seems necessary for any solution as the current one. $\endgroup$ – Benoît Kloeckner Apr 20 '15 at 8:29
  • 6
    $\begingroup$ But if the scientist are mathematicians, this solution will almost surely not work: it involves using and adding numbers greater than $3$, so errors are bound to occur. $\endgroup$ – Benoît Kloeckner Apr 20 '15 at 8:31
9
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ This sounds really cool. I have little familiarity with this math, so unfortunately, I can't fully appreciate it. I wonder though, could this method potentially kill a second scientist? The scientists are not allowed to repeat a number. So say this method encodes the number as 77, then the scientist with headband 77 is doomed as well. Does it save 98 people then? Less? $\endgroup$ – suneater Apr 20 '15 at 7:43
  • $\begingroup$ @zahbaz oh, I forgot about that. Hmm. It would save at least 98 people. $\endgroup$ – Justin Apr 20 '15 at 7:54
  • 4
    $\begingroup$ Quincunx: When someone needs to say the number that the first scientist said, then what? He has to say something else, which messes up the calculation for everyone else. $\endgroup$ – Samuel Apr 20 '15 at 9:52
  • $\begingroup$ @Samuel Well apparently the question meant something different than what I thought. I thought that repeating an already said number would result in the death of the repeat sayer; that was how I interpreted the question at the time of this answer $\endgroup$ – Justin Apr 20 '15 at 17:37
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Why the downvote? $\endgroup$ – Hagen von Eitzen Apr 20 '15 at 21:16
  • $\begingroup$ I didn't downvote, but it may be because you saved such a small number of scientists compared with the other answers (and since you argued that 76 is optimal, there clearly must be something wrong with your reasoning). $\endgroup$ – Brilliand Apr 21 '15 at 21:45
  • $\begingroup$ @Brilliand Except implicitly by submitting my attempt in the first place, I didn't say $76$ was optimal (it is merely the best choice for my type of approach). And at the time of my writing the better solutions were almost all flawed. But I agree that this answer is now very inferior. I guess I shall still keep it alive for its different approach $\endgroup$ – Hagen von Eitzen Apr 26 '15 at 17:56
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ It's not specified in the question, but the scientists should only be allowed to say a number between 1 and 101, or else the problem is trivial. See the comments to zahbaz's answer. $\endgroup$ – Samuel Apr 20 '15 at 17:50
  • $\begingroup$ Yes, I agree: scientists should ony be able to guess integers between 1 and 101. $\endgroup$ – Marconius Apr 21 '15 at 19:26
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.