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

[bushindo]

He would need an excuse. Saying that the scan is positive and the unconscious needs to be cured is one such excuse.

Odds are the infected one will manage to infect the other without you figuring it out. It's not 100% certain but it's the worst case scenario you can expect (as I imagine that once the second is infected he will not say he was touched by the other).

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 .

Edited December 20, 2010 by bushindo

[Guest]

Everyone takes the syrum to be safe! since nobody can die from it. ;-) doors opened? 0

[araver]

Everyone takes the syrum to be safe! since nobody can die from it. ;-) doors opened? 0

It is not that simple as infected people can lie and are smart enough not to inject themselves.

Edited December 19, 2010 by araver

[Guest]

Ask 2 people to come out, tell them to pretend to be gassed, have another 2 come out with the serum, disinfect themselves, each other, then ONLY scan the 2 on the ground(all the while reminding them not to make any skin contact with each other). Then you tell the 2 on the ground to scan themselves and the others. If all read clean, they are either all infected now or the two on the ground are the ones infected. In any case, you gas them all. Then you send the last person into the corridor. He/she then scans everyone. 3 scenarios should arise now; 1: all are infected, disinfect all, 2: the first 2 are infected, disinfect them, 3: he/she says none are infected, gas him/her as well and you go disinfect all.

One more scenario is possible, but if this happens, my entire solution is dissolved. The last possibility is that the last person is already infected, claims the unconscious are all infected, and then touches everyone, regardless of infected or not, and infects them.

I'd like any feedback on my solution, especially if it's about something I can/cannot do. Thanks.

[Guest]

It is not that simple as infected people can lie and are smart enough not to inject themselves.

all videos are working so you can see who doesn't take it

[araver]

all videos are working so you can see who doesn't take it

No amount of video evidence alone is convincing enough as a basis. E.g. since you weren't around from the beginning, anyone of them could have hidden a ball and inject the serum into the ball instead of themselves.

And please

don't ask them to get naked before taking the serum either

Think that they could have tempered with the serum before you have awaken fully, so they'll just inject a worthless liquid instead of the serum.

Edited December 19, 2010 by araver

[araver]

Ask 2 people to come out, tell them to pretend to be gassed, have another 2 come out with the serum, disinfect themselves, each other, then ONLY scan the 2 on the ground(all the while reminding them not to make any skin contact with each other). Then you tell the 2 on the ground to scan themselves and the others. If all read clean, they are either all infected now or the two on the ground are the ones infected. In any case, you gas them all. Then you send the last person into the corridor. He/she then scans everyone. 3 scenarios should arise now; 1: all are infected, disinfect all, 2: the first 2 are infected, disinfect them, 3: he/she says none are infected, gas him/her as well and you go disinfect all.

One more scenario is possible, but if this happens, my entire solution is dissolved. The last possibility is that the last person is already infected, claims the unconscious are all infected, and then touches everyone, regardless of infected or not, and infects them.

I'd like any feedback on my solution, especially if it's about something I can/cannot do. Thanks.

A general comment, you cannot go down on the station.

Some comments on your proposed solution:

It's a nice strategy, but:

1) As in another comment I made above, you cannot trust the serum from an area that has an infected person since that serum might be tampered with beforehand. However since 3 areas where not touched by the infected, you can trust the serum from 3 of the 5 areas.

2) If the last person is infected, he will grab the opportunity and infect all the others. As you said yourself, I cannot refute his claim that all others are infected, nor prevent him from "disinfecting" them. Also, if I let an infected person in the same area with all the others unconscious, it's game over for me.

[Guest]

Question: Are the 5 areas connected to a central hub, or are they connected to each other in a ring-like structure?

[araver]

Question: Are the 5 areas connected to a central hub, or are they connected to each other in a ring-like structure?

You can safely assume enough corridors are available to connect each pair of areas (a pentagon with all diagonals).

I did not think of a central hub location (as a 6th area), but you're allowed to use one if you need (although this makes the scenario even less likely in practice).

[Guest]

assuming the two infected ones know who the other is you could gas all exept one. tell them to give give evryone syrum from their own rooms without even scaning them (make sure they do not touch anyone) then once they are back in their room gas them and have another person do the same. then just to make sure you didnt pick the two infected ones have a third person go and do it so no matter what one uninfected trustworthy person will have uninfected evryone

NOTE:tell evryone they are the first to be woken up and that no one has been injected yet

please comment and tell me if i missed anything

[araver]

assuming the two infected ones know who the other is you could gas all exept one. tell them to give give evryone syrum from their own rooms without even scaning them (make sure they do not touch anyone) then once they are back in their room gas them and have another person do the same. then just to make sure you didnt pick the two infected ones have a third person go and do it so no matter what one uninfected trustworthy person will have uninfected evryone

NOTE:tell evryone they are the first to be woken up and that no one has been injected yet

please comment and tell me if i missed anything

Comments:

I like the bit about lying them about who is the first to be woken up / no one has been injected yet.

The flaw in your strategy is that you cannot make sure they do not touch anyone. All you have is a lousy video connection and no ability to see 360 degrees. So if the first one is infected, he may give the right serum + infect them at the same time without you knowing for sure. Which means the second and third person waking up would also be infected / infect the others also.

And I did not get the part with the two infected ones knowing which is the other infected one ... where does that come into play?

[Guest]

I'm doing this as I type, so bear with me.

Gas 2 rooms and connect each one to another room, having the conscious one scan and cure if infected. This leaves a few possible scenarios:

1. both gassed rooms had infected people, so the base is cured.

2. one gassed room had an infected person and the other one went into his room

3. one gas room had an infected, and the other one went into the other gassed room

4. one gas room had an infected, and the other one was the last room

5. one conscious room had an infected, and the other one was in the last room

These situations end with the following possibilities:

1. all clear

2&3. 2 infected through one connected hallway

4. one infected

5. 3 infected, 2 connected and one separate from the others

In all cases there is at least one person who is not infected. Have the conscious people return to their original rooms and have the last person enter one of the gassed rooms and scan.

Thus, we can get the following situations:

1. all clear

2&3a. goes into the infected room; clears it

2&3b. goes into the clean room

4. infects the room he enters

5a. goes into the infected room

5b. goes into the clean room; infects it

With the following endings:

1. clear

2a. 1 infected

2b. 2 infected

3. 2 infected

4a. 3 infected

4b. 4 infected

I just noted that whatever happens, an infected person will always say that another is clean.

Also, in doing this I realize that assigning numbers to the rooms would have made the process of describing this much easier, so I will start this now: Starting from the isolated person and going clockwise around the (what I assume) pentagonal figure, it's 1-5. Thus, in the first step, 5 went to 2 and 4 went to 3, and 2 and 3 were gassed. Hopefully you can still follow what I'm saying.

Now have 1 return to his room, and once again have 5 scan 2. Depending on what he says, you can determine what situation we have (I hope)

If he says "clean," then it's either an infected person lying, or a clean person telling the truth. With a diagram (such as the one I drew that I have no idea how to put in here) one can see that it must be situation 1, 2a, 2b, or 4a.

If he says "infected," then it's a clean person telling the truth, and it's 3 or 4b. If that's the case, then you can just gas all the other rooms and have him go around cleaning everyone else.

Thus we're left with the former problem. Hm... Have 1 once again sweep, this time 2 AND 3, and if one of them is reported as "infected," then he's clean and have him clean the station as before. If he reports all clean, then you know that room 4 is the only clean one, and he can clean the rest of the station.

Now, I know that this solution can undoubtedly be cleaned up, as I didn't incorporate my assumption with the infected people until halfway through, and I also realize that that assumption may be wrong, although currently I can't think of a reason why that might be so.

[Guest]

Note: if i say 1st i mean the first man sent in at the beginning here 2nd is second guy etc

Pick any random room and gas it, and then send 1 person from a different room to check the guy in it but do nothing regardless, then another guy to do the same (from a different room) and then another guy again to do it, but each time having only the gassed guy and the one there to check it in there at once. After this do it again, in reverse order. So the guy you sent in last go in again, then the 2nd guy, then the first guy.

After this you will have either

1 All clean - therefore they are all clean as only 2 people are infected and the infected ones cant have infected anyone else other than the gassed one and since you checked in reverse order if the infected guy was the first one then the other not infecteds would have seen infection if 2nd guy then first guy and 3rd guy would have seen it, it 3rd guy then 2nd and 1st would have. therefore one clean person would see it. Then gas all other rooms and send one of these guys to cure them.

2 one person says Infected at any point, then that guy is clean and gas everywhere else and have him check/cure them.

Then the base is cleared.

I have based this on that no infected person would say infected regardless of the actual result of the scan, and that any infected person would take an opportunity to infect an unconscious guy - otherwise this doesnt work.

[bushindo]

Some clarification please:

1) The OP indicates that video and audio communication are available between you and all areas. That seems to imply that you can simply pose questions to the crew members and have them respond. Does that mean that the non-infected crew members will act as truth tellers? Would the infected members then act as random answerers?

2) Suppose that a crew member is infected, and then is cured by a serum. Would he know that he was infected last round?

Edited December 20, 2010 by bushindo

[araver]

Some clarification please:

1) The OP indicates that video and audio communication are available between you and all areas. That seems to imply that you can simply pose questions to the crew members and have them respond. Does that mean that the non-infected crew members will act as truth tellers? Would the infected members then act as random answerers?

2) Suppose that a crew member is infected, and then is cured by a serum. Would he know that he was infected last round?

1) Yes

- Non-infected crew members act as truth-tellers.

- Infected members don't act random, they choose their responses adaptively to suit their interest (i.e. may try to act as truth-tellers - stick with their lies)

And a bonus clarification: they don't really know which of them is infected.

2) No. Infection may work as temporary subtle mind-control.

[araver]

Note: if i say 1st i mean the first man sent in at the beginning here 2nd is second guy etc

Pick any random room and gas it, and then send 1 person from a different room to check the guy in it but do nothing regardless, then another guy to do the same (from a different room) and then another guy again to do it, but each time having only the gassed guy and the one there to check it in there at once. After this do it again, in reverse order. So the guy you sent in last go in again, then the 2nd guy, then the first guy.

After this you will have either

1 All clean - therefore they are all clean as only 2 people are infected and the infected ones cant have infected anyone else other than the gassed one and since you checked in reverse order if the infected guy was the first one then the other not infecteds would have seen infection if 2nd guy then first guy and 3rd guy would have seen it, it 3rd guy then 2nd and 1st would have. therefore one clean person would see it. Then gas all other rooms and send one of these guys to cure them.

2 one person says Infected at any point, then that guy is clean and gas everywhere else and have him check/cure them.

Then the base is cleared.

I have based this on that no infected person would say infected regardless of the actual result of the scan, and that any infected person would take an opportunity to infect an unconscious guy - otherwise this doesnt work.

A clarification: an infected person can scan and report whatever suits him best (i.e. he can either lie or tell the truth).

But an infected person indeed jumps on the opportunity to infect an unconscious person (this is their only deterministic flaw).

Comments:

The steps in your strategy are like this:

2 checks/scans 1 

3 checks 1

4 checks 1

4 checks 1

3 checks 1

2 checks 1

Assume 2 and 1 are infected, 3 and 4 are clean. You get the following responses:

2 checks 1 says "Infected" (Truth)

3 checks 1 says "Infected" (Truth)

4 checks 1 says "Infected" (Truth)

4 checks 1 says "Infected" (Truth)

3 checks 1 says "Infected" (Truth)

2 checks 1 says "Infected" (Truth)

Assume 2 is infected, 1, 3 and 4 are clean at the beginning.

2 checks 1 says "Infected" (Lie, but gets to infect)

3 checks 1 says "Infected" (Truth)

4 checks 1 says "Infected" (Truth)

4 checks 1 says "Infected" (Truth)

3 checks 1 says "Infected" (Truth)

2 checks 1 says "Infected" (Truth)

That kills the "one person says Infected at any point, then that guy is clean" hypothesis, don't you think?

[araver]

I'm doing this as I type, so bear with me.

Gas 2 rooms and connect each one to another room, having the conscious one scan and cure if infected. This leaves a few possible scenarios:

1. both gassed rooms had infected people, so the base is cured.

2. one gassed room had an infected person and the other one went into his room

3. one gas room had an infected, and the other one went into the other gassed room

4. one gas room had an infected, and the other one was the last room

5. one conscious room had an infected, and the other one was in the last room

These situations end with the following possibilities:

1. all clear

2&3. 2 infected through one connected hallway

4. one infected

5. 3 infected, 2 connected and one separate from the others

In all cases there is at least one person who is not infected. Have the conscious people return to their original rooms and have the last person enter one of the gassed rooms and scan.

Thus, we can get the following situations:

1. all clear

2&3a. goes into the infected room; clears it

2&3b. goes into the clean room

4. infects the room he enters

5a. goes into the infected room

5b. goes into the clean room; infects it

With the following endings:

1. clear

2a. 1 infected

2b. 2 infected

3. 2 infected

4a. 3 infected

4b. 4 infected

I just noted that whatever happens, an infected person will always say that another is clean.

Also, in doing this I realize that assigning numbers to the rooms would have made the process of describing this much easier, so I will start this now: Starting from the isolated person and going clockwise around the (what I assume) pentagonal figure, it's 1-5. Thus, in the first step, 5 went to 2 and 4 went to 3, and 2 and 3 were gassed. Hopefully you can still follow what I'm saying.

Now have 1 return to his room, and once again have 5 scan 2. Depending on what he says, you can determine what situation we have (I hope)

If he says "clean," then it's either an infected person lying, or a clean person telling the truth. With a diagram (such as the one I drew that I have no idea how to put in here) one can see that it must be situation 1, 2a, 2b, or 4a.

If he says "infected," then it's a clean person telling the truth, and it's 3 or 4b. If that's the case, then you can just gas all the other rooms and have him go around cleaning everyone else.

Thus we're left with the former problem. Hm... Have 1 once again sweep, this time 2 AND 3, and if one of them is reported as "infected," then he's clean and have him clean the station as before. If he reports all clean, then you know that room 4 is the only clean one, and he can clean the rest of the station.

Now, I know that this solution can undoubtedly be cleaned up, as I didn't incorporate my assumption with the infected people until halfway through, and I also realize that that assumption may be wrong, although currently I can't think of a reason why that might be so.

Clarification: An infected person will not always say that another is clean. Each infected person acts as an independent agent of infection. You must not assume he has a greedy strategy that always protects the others he infects (he might sacrifice one and say they're infected when they are infected) and he can also choose to frame someone who is not infected or not to frame him in order to alleviate suspicions on him.

You are partially right, it's harder to read in the beginning

You are right about the five scenarios that arise from 2 disjoint pairs of conscious/inconscious scan+disinfect. However, I don't really follow what happens after you put "the last person enter one of the gassed rooms and scan". Which room in your 1,2,3,4,5 rotation? Can you elaborate(taking into account the clarification above)?

[araver]

To make your strategies easier to explain you can use the following base diagram:

Alternatively, if you want a neutral / central location, you can assume one as well

[Guest]

I believe sending 2, 3, 4, and 5 to scan an unconscious 1 separately and in order will eventually result in an infection of 1, and if everyone says he checks out clean you can assume 4 and 5 to be infected(along with 1, now) and you can send 2 and 3 to disperse the serum. in a more complicated scenario, say 5 says he's infected, but 5 is also infected and so giving him the serum will do nothing. then go back and have 4, 3, and 2 scan 1. if 4 was the other infected, 3 will confirm that 1 is infected. if 3 is the infected 2 will confirm, and if 5 and 1 were the original infected then 4's scan will say so. now, if they all say he's clean then 2 must also be infected as he would be the last one and could lie. then you could assume 3 and 4 are the two clean ones, and have them dispense the serum.

I am starting to second guess my solution now, as I am starting to see how:

an infected could lie saying one of them was infected when he wasn't and now there are 3 where you might have thought you found one.

I shall sleep on this one and return later.

[Guest]

Without anyone contacting anyone else, send 4 of them one at a time to the door leading outside. There is a scanner connected to this door that will detect who is infected and who is clean. When a person reaches the scanner, it will set off an alarm if they are infected. Of the 4 people sent to the scanner, 1 or 2 will set off the alarm. Here are the possibilities for the two infected:

p1, p2 (2 doors)

p1, p3 (3 doors)

p1, p4 (4 doors)

p1, p5 (4 doors)

p2, p3 (3 doors)

p2, p4 (4 doors)

p2, p5 (4 doors)

p3, p4 (4 doors)

p3, p5 (4 doors)

p4, p5 (3 doors)

Once you have found out who the two infected individuals are, gas their rooms and send one of the non-infected persons to inject them with the serum from their own room.

Min doors opened: 4

Max doors opened: 6

Avg doors opened: 5.5

Risk of spreading infection: 0.0%

[araver]

Without anyone contacting anyone else, send 4 of them one at a time to the door leading outside. There is a scanner connected to this door that will detect who is infected and who is clean. When a person reaches the scanner, it will set off an alarm if they are infected. Of the 4 people sent to the scanner, 1 or 2 will set off the alarm. Here are the possibilities for the two infected:

p1, p2 (2 doors)

p1, p3 (3 doors)

p1, p4 (4 doors)

p1, p5 (4 doors)

p2, p3 (3 doors)

p2, p4 (4 doors)

p2, p5 (4 doors)

p3, p4 (4 doors)

p3, p5 (4 doors)

p4, p5 (3 doors)

Once you have found out who the two infected individuals are, gas their rooms and send one of the non-infected persons to inject them with the serum from their own room.

Min doors opened: 4

Max doors opened: 6

Avg doors opened: 5.5

Risk of spreading infection: 0.0%

Indeed you found a loophole.

I forgot about using the outdoor filter alarm

It is not what I intended with the puzzle, but I need to think on an alternate setting that would allow for a full indoor solution.

[bushindo]

More clarification:

Suppose that an infected member is in a room with a non-infected unconscious member, presumably he would need an excuse to touch the unconscious person. What would the infected member say about the result of his scan?

What happens when you connect two conscious crewmember together, one of which is infected, and the other being non-infected?

[araver]

More clarification:

Suppose that an infected member is in a room with a non-infected unconscious member, presumably he would need an excuse to touch the unconscious person. What would the infected member say about the result of his scan?

He would need an excuse. Saying that the scan is positive and the unconscious needs to be cured is one such excuse.

What happens when you connect two conscious crewmember together, one of which is infected, and the other being non-infected?

Odds are the infected one will manage to infect the other without you figuring it out. It's not 100% certain but it's the worst case scenario you can expect (as I imagine that once the second is infected he will not say he was touched by the other).

[Molly Mae]

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.

[Guest]

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.

Edited December 20, 2010 by willbrownsf