[araver]

A small scientific base was established on a planet. Scientific missions were scheduled where five people were on the base at a given time, while one was left in cryogenic stasis aboard the ship orbiting the planet.

The first team that discovered the planet has suffered an infection from an alien parasitic life-form that was able to control the persons it infected. Incident video logs had shown that an infected host did not show any external symptoms and that the infection was transmitted only by direct skin contact.

Since then, contamination protocols were in place in the base and a bio-contamination alert would automatically awake the person onboard the orbiting ship and give him full-control over base operations. A serum that cures the infection without killing the host was developed. A vaccine is not available, but personal medical scanners can detect the infection. Filters that detect (but cannot cure) the infection were placed on the outer doors.

You have been awaken by a contamination alert and discover that:

A) There are still five lifesigns in the base, each lifesign is in a separate area of the base. All areas of the base have stockpiles of the serum and personal medical scanners.

B) The log from the base has been partially deleted but the recovered log shows that there were two separate filter alerts at two outer doors. The alerts were almost simultaneous which suggests that only two infected persons have entered the base.

C) The automatic lock-down protocols have engaged before any two persons could have come into contact.

D) You still have control over the automatic doors sealing the areas and you can create a corridor between any two areas by remotely opening and closing the doors.

E) You have control over the air ventilation system and are able to induce short-term sleeping gas in any area of the base you choose to. Any person in that area will become unconscious in less than 10 seconds.

F) Video and audio communications are intact and bidirectional with all areas of the base.

You know that any non-infected person would be able to scan and disinfect another unconscious person while an infected person will most likely lie about the scan and infect the unconscious person. You can assume that in order to avoid detection, everybody will follow your orders, in order to be let out of the base and possibly infect a larger population.

Can you come up with a strategy that cleans everybody on the base? If so, what is the minimal number of doors you need to open?

Please use spoilers for your strategies!

P.S. While writing the background story for this puzzle, I figured that such an unlikely contamination incident can be analysed beforehand and handled in the "Guide for Scientists Stranded on a Far Away Planet".

If that particular thought has crossed your mind, please assume the above scenario is taken from the final exam before being allowed to become a "Scientist (Potentially Stranded) on a Far Away Planet". And that any form of cheating / exploiting weak points in the scenario might be frowned upon and lead to the denial of your application. And that this is not a Kobayashi Maru scenario, no need to Kirk your way through it

I will however answer any questions you might have regarding what can and what cannot be done in the scenario.

[araver]

It's pretty safe to say that you can't trust two people together. There might be a better way, but I'd

1. Gas everyone except person #1.

2. Have person #1 deliver serum to the central hub.

3. Have person #1 return to his room.

4. Gas everyone except person #2.

5. Have person #2 deliver serum to the central hub.

...

...

...

After the fifth person delivers his serum, have him inject himself with one from every pile.

...

32(?). Have person #5 return to his room.

33. Gas everyone except person #1.

34. Have person #1 enter the central hub and inject himself with with serum from every pile.

35. Have person #1 return to his room.

36. Gas everyone except person #2.

...

...

...

It's a bit lengthy, but no two people will ever come into contact with each other. Further, they'll all have taken legitimate serum.

While this might not be the best way, it at least leads us to a worthwhile conclusion.

I like the quarantine-type solution yet it has one small flaw: you cannot be sure that an infected person actually injects himself with something. (low quality video and all).

Instead of knocking one crew member unconscious you left them both conscious, had them suit up in space gear, leaving one forearm exposed. You tell member 1 & member 2 to inject each other with the cure while in front of a camera with the hand inside the space suit. If someone tries to use the other hand then you know they are infected and can quarantine both of them for the time being. You then have member 3 & member 4 perform the same procedure, with the same action taken if one tries anything funny. This leaves member 5, who judging from the actions of the other members, you can deduce whether he is infected or not. He would be able to cure both teams if they failed the test and he could be cured by members who passed the test.

If everything goes better than expected it would be possible for only 3 doors to be opened, at most only 4 doors opening would be needed.

Same flaw as in another strategy above: you cannot trust the serum from a room where an infected person was in as it might have already been tampered with. And think of an extreme case of tampering: it might actually contain blood samples from infected people.

1) Non-infected people will not refuse a serum they know it's been tampered it if you pair-up infected people.

2) If you pair an infected with a non-infected, you either give each other serum from the other's room (in which case you cure the infected and potentially infect the other one due to previous tampering) or give each serum from his own room (therefore not curing the infected at all).

3) Non-paired member can still be infected.

Edited December 20, 2010 by araver

[araver]

Well, if that's the case, then here's a strategy,

The key point of this strategy is that we reduce the puzzle into a previously where we need to determine the position of 2 random answerers from a group of 4 (2 random answerers + 2 truth tellers). It is known that we can narrow the possibilities into 2 configurations. Having a 5th crew member will then allow us to narrow these 2 configuration down into a single possibility.

Some general concepts are as follows. Let the non-infected members be called truth tellers, and let the infected members be called random answerers. Let the crew members be called A, B, C, D, and E. We'll let E be called a place holder. Within the group A, B, C, and D, we can determine the status of any member using another member. For instance, suppose that we want to assess the status of A using B. We then simply gas E and tell A to come and disinfect E if necessary. That essentially copies A's status onto E. We then gas E again and tell B to come, scan E, and tell us the results. If B is a truth teller, he'll tell us the true status of A. If B is random answerer, then his answer could be anything*. Note that we are not changing the status of A, B, C, or D.

The steps goes as follows

1) At the beginning, let A come and scan E first, and report the results. If E is already infected before A comes in, then we will have 3 truth tellers and 1 random answerer among A, B, C, and D. This is a trivial situation, as we know we can readily narrow down the single random answerer with The non-trivial situation is where we have two random answerers among A, B, C, and D.

2) It has been shown that given two random answerers in a group of 4, we can only narrow the possibilities down to 2 possible configurations, which are mirror images of one another. One possibility will state that A is non-infected, and the other combination will state that A is infected. If we encounter this situation, then we'll know that E was non-infected.

3) Simply go back and see what A reported on the first scan on E at the beginning. If A reported that E was non-infected, then A is non-infected (truth teller) as well. If A reported infected (in order to come and infect E), then we know that A is infected. We now know the infect/non-infected status all crew members.

* Note: this solution is non-optimal. This is because random answerers aren't completely random. The key fact here is that when an infected person (random answerer) is asked about a non-infected person (truth teller), he will tell a lie. I only used that fact once in this solution, because the more general framework with the completely random answerers is already solved. Solving for an optimal solution may require something along the following line of .

I admit, while creating the problem I was thinking of building on the same previous problems. Therefore your solution is very similar to what I had in mind.

I do not know if a different type of strategy exists (different i.e. exploits a different aspect of the problem).

As I got carried away with writing the setting for the problem as a contamination scenario and forgot to check for loopholes, I also have to credit Jobe17 for finding an alternative solution.

[bushindo]

I admit, while creating the problem I was thinking of building on the same previous problems. Therefore your solution is very similar to what I had in mind.

I do not know if a different type of strategy exists (different i.e. exploits a different aspect of the problem).

As I got carried away with writing the setting for the problem as a contamination scenario and forgot to check for loopholes, I also have to credit Jobe17 for finding an alternative solution.

Just read Jobe17's solution. Wish I thought of that. Thanks for the superbly constructed puzzle. I really enjoy it. It was devilishly challenging/fun to work through.