[Douglas]

Hello all -

In a lab for my general chemistry students, I have them mix "contaminated" solutions to see if they can work out who the original contaminators are. Trouble is, I have as much difficulty as they do working out the correct answer. I am posting here to see if is an algorithm to working backwards. 

First let me explain the procedure. Each student in the class with obtain a numbered test tube. They then proceed to mix their solution with another student's. We do this all together with everyone mixing (if there is an odd number of students, I participate). There are three mixings, no one can mix with the same person twice, and each mixing is done when everyone is done with the previous mixing.

What I've attached is the data from two classes. The pink boxes will indicate the solutions that are contaminated after the third mix. (By the way, I simply make a certain number of the test tubes as 0.001% phenolphthalein, and have everyone add NaOH to their tube after the third mixing to see if they are contaminated.) When I work the data forward from what I know to be the original contaminators, the data results are correct. Still, I get stuck after eliminating the non-contaminated (and those that they mix with) solutions as not being the original contaminator.

Could you please look at these two class's data and see if you can work out which the original contaminator(s) is/are? Then, could you share with me how you got your answer so I can see if there is a logical algorithm to solving these (and therefore any) data sets (I assume there is). I'll post the answer of which the original contaminator(s) are upon request (some people may not want to know the answer.)

Thank you!

[Yggdrasil]

I looked through the first data set and came to some interesting conclusions.

Well, first off, because there are more than 8 contaminated samples after 3 rounds, you know that there are two or more who began with the contaminant.  My first step was to list the samples which were known to be contaminated and look through their mixing histories.  I noted which samples had mixed with a sample which is was not contaminated at the end (samples 2, 7, 13, and 18).  These samples cannot be the origin of contamination.  Of these, two (#2 and #13) had not mixed with a contaminated sample until the final round.  Therefore #2 definitely got contaminated by #6 and #13 definitely got contaminated by #14. 

Next, I looked at all the possible contaminators of #6.  This shows that our case zero (an origin of contamination) must be among 6, 8, 9, or 14.  Interestingly enough, when we trace the possible contaminators of #14, we get the same set of four samples.  Even more interestingly, if you trace the histories of #6, 8, 9, and 14, assuming each one is the case zero in turn, they account for the same eight cases (2, 6, 7, 8, 9, 13, 14, 18).  So, one of # 6, 8, 9, 14 must be the case zero (although I don't think you can tell which one). 

Since that case zero accounts for eight of the observed 12 cases, I next looked at the remaining four (#3, 4, 11, 16).  Interestingly, if you trace the histories of each, they end up mixing only with members of their own group.  So again, you can narrow down the case zero to a group of four, but you cannot tell which of the four was the original case zero.

So, the interesting part of this experiment is acutally a social science result.  It appears that the class consists of at least one "clique" who prefer to interact with eachother -- for example, the group of #3, 4, 11 and 16 who interacted exclusively.  Furthermore, there were enough mutual "friends" among #6, 8, 9, and 14 to make it impossible to tell who is the case zero.

[Yggdrasil]

For data set two, you can narrow one case zero down to a pair of samples (which upon further thought, is as narrow as you can make it), but the other narrows down to a group of four again.  I'll leave the answers out in case someone wants to try this one themselves.

[Borek]

Not looking as other posts, so I can be repeating what others posted.

Start with not contaminated samples (NCS) after three mixings. Each one lets you name three original NCS - cross them out everywhere. Only not crossed samples could be contaminated. For example in the first set 5, 15, 2, 12 and 1 are NCS (among others). Sample number 2 was mixed with 12, 5 and 14 - only of those could be contaminated. And so on.

IMHO some data sets will have no unique solution.

--------

OK, after reading Yggdrasil posts I see we have came to the same final conclusion

I think my approach - with removing first all clean samples - speeds up finding the final solution. But I am known to be occasionally wrong

[Donaldson Tan]

With regards to data 1 (picture1.png) ...

Since that case zero accounts for eight of the observed 12 cases, I next looked at the remaining four (#3, 4, 11, 16).  Interestingly, if you trace the histories of each, they end up mixing only with members of their own group.  So again, you can narrow down the case zero to a group of four, but you cannot tell which of the four was the original case zero.

In data set 1, the set (11,16,4,3) are always found together but not necessary in the same order. Yggdrasil is most probably right that the students corresponding to beakers 3,4,11 & 16 hang out together exclusively. At least one in this set of beakers are contaminated.

Next, I looked at all the possible contaminators of #6.  This shows that our case zero (an origin of contamination) must be among 6, 8, 9, or 14.  Interestingly enough, when we trace the possible contaminators of #14, we get the same set of four samples.  Even more interestingly, if you trace the histories of #6, 8, 9, and 14, assuming each one is the case zero in turn, they account for the same eight cases (2, 6, 7, 8, 9, 13, 14, 18).  So, one of # 6, 8, 9, 14 must be the case zero (although I don't think you can tell which one).

I disagree with Yggdrasil's (underlined) conclusion. In fact, I reckon all the beakers (6,8,9,14) are definitely contaiminated. By elimination, beakers 1,2,5,7,10,12,13,15,17,18,19,20 are definitely clean. The data from columns 2,7,13,18 are such that that 3 beakers are clean and 1 beaker is contaminated. They clearly identify that beakers 6,8,9,14 are contaminated.

[Yggdrasil]

I disagree with Yggdrasil's (underlined) conclusion. In fact, I reckon all the beakers (6,8,9,14) are definitely contaiminated. By elimination, beakers 1,2,5,7,10,12,13,15,17,18,19,20 are definitely clean. The data from columns 2,7,13,18 are such that that 3 beakers are clean and 1 beaker is contaminated. They clearly identify that beakers 6,8,9,14 are contaminated.

Assume that #6 begins out contaminated and no one else is contaminated.  #6 will directly contaminate #9, #14, and # 13.  Since #9 becomes contaminated after round 1, it will directly contaminate #8, and # 7 in the next two rounds.  Since #14 and #8 become contaminated in round 2 (by # 6 and #9, respectively), they will contaminate #2 and #18 in round 3.  The net result is that sample #6 will directly and indirectly contaminate eight samples (#2, 6, 7, 8, 9, 13, 14, 18).  These eight samples account for all of the contaminated samples outside of the (#3, 4, 11, 16) clade.  Therefore, the assumption that #6 is the only contaminated sample among (#6, 8 , 9, 14) is consistent with the observed data.  The same goes with the other three.  So, IMHO, there is no need to assume that all of (#6, 8 , 9, 14) were contaminated prior to round 1.  I think all we can definitively say is that at least one of (#6, 8 , 9, 14) was contaminated prior to round 1.

[Donaldson Tan]

With regards to data 1 (picture1.png) ...

By elimination, beakers 1,2,5,7,10,12,13,15,17,18,19,20 are definitely clean.

This is the clean list, from elimination. The clean list is obtained from columns in which the final mixture is not contaminated.

The data from columns 2,7,13,18 are such that that 3 beakers are clean and 1 beaker is contaminated.

The final mixture in column 2 at the 3rd mix is contaminated. In column 2, #7 is mixed with #17 first, followed by #18, then #9. According to the elimination list, #2, #12, #5 are clean, so #14 must be contaminated.

The final mixture in column 7 at the 3rd mix is contaminated. In column 7, #2 is mixed with #12 first, followed by #5, then #14. According to the elimination list, #7, #17, #18 are clean, so #9 must be contaminated.

The final mixture in column 18 at the 3rd mix is contaminated. In column 18, #18 is mixed with #20 first, followed by #7, then #8. According to the elimination list, #18, #20, #7 are clean, so #8 must be contaminated.

The final mixture in column 13 at the 3rd mix is contaminated. In column 13, #13 is mixed with #10 first, followed by #17, then #6. According to the elimination list, #13, #10, #17 are clean, so #6 must be contaminated.

[Yggdrasil]

True, #14 must have been contaminated when it mixed with #2, but that does not mean that #14 began as a contaminated sample.  #14 could have been clean to begin with, but it could have gotten contaminated prior to mixing with #2 (e.g. in the example I posted below, #6 contaminates #14 in round 2, prior to #14 contaminating #2 in round 3).

[technologist]

Minimum four  -  6, 8, 9, 14 are the Original Contaminators. Algo will be simple.